結果
問題 | No.393 2本の竹 |
ユーザー |
|
提出日時 | 2021-05-01 15:22:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 46 ms / 1,000 ms |
コード長 | 772 bytes |
コンパイル時間 | 1,986 ms |
コンパイル使用メモリ | 200,200 KB |
最終ジャッジ日時 | 2025-01-21 05:12:51 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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<bool> dp(n1); dp[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 >= a[i]; j--) if (dp[j - a[i]]) dp[j] = true; for (int j = 0; j <= n1; j++) { if (dp[j] && n2 >= 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; }