結果
問題 | No.1606 Stuffed Animals Keeper |
ユーザー |
![]() |
提出日時 | 2021-07-16 21:53:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 3,000 ms |
コード長 | 1,823 bytes |
コンパイル時間 | 2,057 ms |
コンパイル使用メモリ | 195,184 KB |
最終ジャッジ日時 | 2025-01-23 01:44:39 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
/*-------------- | /| | /| | /| * |/ | | ------ *| | | | / \| | |\ | | | |\ |\ | | | \ | | | | \ |\ | | | \ | | \ / \ |V | | \ \__/| ----- \ |*/#include <bits/stdc++.h>using namespace std;#define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"#define print(x) emilia_mata_tenshi(#x, begin(x), end(x))template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {cerr << "\e[1;33m" << s << " = [";while(l != r) {cerr << *l;cerr << (++l == r ? ']' : ',');}cerr << "\e[0m\n";}#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);using ll = int64_t;using ull = uint64_t;using ld = long double;using uint = uint32_t;const double EPS = 1e-8;const int INF = 0x3F3F3F3F;const ll LINF = 4611686018427387903;const int MOD = 1e9+7;/*--------------------------------------------------------------------------------------*/signed main() { EmiliaMyWifeint n;cin >> n;vector<int> arr(n);for(int i = 0; i < n; i++)cin >> arr[i];int tot = 0;for(int i = 0; i < n; i++)if(arr[i] == 1)tot++;vector<int> can(tot + 1, INF);can[0] = 0;for(int i = 0, c = 0, b = 0; i <= n; i++) {if(i == n || arr[i] == 2) {int cost = c - b;for(int j = tot; j >= c; j--)can[j] = min(can[j], can[j - c] + cost);c = 0;b = 0;}elsec++, b += arr[i] == 1;}if(can[tot] == INF)cout << "-1\n";elsecout << can[tot] << '\n';}