結果
問題 |
No.1606 Stuffed Animals Keeper
|
ユーザー |
![]() |
提出日時 | 2023-05-02 11:34:43 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 3,000 ms |
コード長 | 1,581 bytes |
コンパイル時間 | 3,914 ms |
コンパイル使用メモリ | 144,200 KB |
実行使用メモリ | 35,968 KB |
最終ジャッジ日時 | 2024-11-21 03:00:04 |
合計ジャッジ時間 | 4,479 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; int main() { int N; cin >> N; int A[N]; for (int i = 0; i < N; ++i) { cin >> A[i]; } int zero_cnt = 0; int one_cnt = 0; int cnt = 0; int div_cnt = 0; vector<int> swap_cnt; vector<int> div_size; for (int i = 0; i < N; ++i) { int a = A[i]; if (a == 2) { if (cnt > 0) { swap_cnt.push_back(one_cnt); div_size.push_back(cnt); div_cnt++; cnt = 0; one_cnt = 0; } } else { cnt++; if (a == 1) { one_cnt++; } else { zero_cnt++; } } } if (cnt > 0) { div_cnt++; swap_cnt.push_back(one_cnt); div_size.push_back(cnt); } vector<vector<int>> dp(div_cnt + 1, vector<int>(N + 1, INT_MAX)); dp[0][0] = 0; int ans = dp[0][zero_cnt]; for (int i = 1; i <= div_cnt; ++i) { int size = div_size[i - 1]; int sc = swap_cnt[i - 1]; dp[i] = dp[i - 1]; // fprintf(stderr, "i: %d, size: %d, sc: %d\n", i, size, sc); for (int len = 0; len < zero_cnt; ++len) { if (dp[i - 1][len] == INT_MAX) continue; int n_size = len + size; int n_sc = dp[i - 1][len] + sc; dp[i][n_size] = min(dp[i][n_size], n_sc); } ans = min(ans, dp[i][zero_cnt]); } if (ans == INT_MAX) { cout << -1 << endl; } else { cout << ans << endl; } return 0; }