結果
問題 | 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;}