結果
問題 | No.393 2本の竹 |
ユーザー |
|
提出日時 | 2024-11-11 22:20:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 1,000 ms |
コード長 | 1,905 bytes |
コンパイル時間 | 3,565 ms |
コンパイル使用メモリ | 191,764 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-11 22:20:23 |
合計ジャッジ時間 | 4,043 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/hash_policy.hpp>#define Add(x, y) (x + y >= mod) ? (x + y - mod) : (x + y)#define lowbit(x) x & (-x)#define pi pair<ll, ll>#define pii pair<ll, pair<ll, ll>>#define iip pair<pair<ll, ll>, ll>#define ppii pair<pair<ll, ll>, pair<ll, ll>>#define ls(k) k << 1#define rs(k) k << 1 | 1#define fi first#define se second#define full(l, r, x) for(auto it = l; it != r; ++it) (*it) = x#define Full(a) memset(a, 0, sizeof(a))#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);#define For(i, l, r) for(register int i = l; i <= r; ++i)#define _For(i, l, r) for(register int i = r; i >= l; --i)using namespace std;using namespace __gnu_pbds;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const int N = 65, M = 1e5 + 10;inline ll read(){ll x = 0, f = 1;char c = getchar();while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}inline void write(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9)write(x / 10);putchar(x % 10 + '0');}int T, n1, n2, m, k, sum, ans;int a[N];bool dp[M];inline void solve(){ans = sum = 0;n1 = read(), n2 = read(), m = read();for(int i = 1; i <= m; ++i)a[i] = read();sort(a + 1, a + m + 1);k = max(n1, n2);for(int i = 1; i <= k; ++i)dp[i] = 0;for(int i = 1; i <= m; ++i){for(int j = k - a[i]; j >= 0; --j)dp[j + a[i]] |= dp[j];sum += a[i];for(int j = 0; j <= n1; ++j)if(dp[j] && sum - j <= n2)ans = max(ans, i);}write(ans);putchar('\n');}bool End;int main(){dp[0] = 1;T = read();while(T--)solve();cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";return 0;}