結果
問題 | No.393 2本の竹 |
ユーザー |
|
提出日時 | 2021-05-01 15:13:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 1,000 ms |
コード長 | 924 bytes |
コンパイル時間 | 1,927 ms |
コンパイル使用メモリ | 200,020 KB |
最終ジャッジ日時 | 2025-01-21 05:12:28 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; void solve() { int n1, n2, m; cin >> n1 >> n2 >> m; vector<int> a(m); for (int i = 0; i < m; i++) cin >> a[i]; sort(a.begin(), a.end()); vector<int> dp1(n1+1), dp2(n2+1); dp1[0] = dp2[0] = true; int tot = 0; int ret = 0; for (int i = 0; i < m; i++) { tot += a[i]; if (tot > n1 + n2) break; bool ck = false; for (int j = n1; j > 0; j--) if (j - a[i] >= 0) dp1[j] |= dp1[j - a[i]]; for (int j = n2; j > 0; j--) if (j - a[i] >= 0) dp2[j] |= dp2[j - a[i]]; for (int j = 0; j <= n1; j++) { if (dp1[j] && 0 <= tot-j && tot-j <= n2 && dp2[tot-j]) { ck = true; break; } } if (ck) ++ret; else break; } cout << ret << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { solve(); } return 0; }