結果
問題 | No.393 2本の竹 |
ユーザー |
![]() |
提出日時 | 2016-07-14 19:48:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 1,000 ms |
コード長 | 1,749 bytes |
コンパイル時間 | 1,046 ms |
コンパイル使用メモリ | 103,820 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 09:26:29 |
合計ジャッジ時間 | 2,389 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> //#include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> //#include<list> #include<queue> #include<deque> #include<algorithm> //#include<numeric> #include<utility> //#include<memory> #include<functional> #include<cassert> #include<set> #include<stack> #include<random> const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, -1, 0, 1}; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vll; typedef pair<int, int> pii; const int MAX = 100100; bool dp[MAX]; // [0, upper) のものをすべて提供しても大丈夫か bool isOK(int N1, int N2, const vi& A, int upper) { if (upper == 0) return true; int sum = 0; for (int i = 0; i < upper; i++) sum += A[i]; if (sum > N1+N2) return false; memset(dp, false, sizeof(dp)); dp[0] = true; for (int i = 0; i < upper; i++) { for (int j = MAX-1; j >= 0; j--) { if (dp[j]) { if (j+A[i] <= N1) dp[j+A[i]] = true; } } } for (int i = MAX-1; i >= 0; i--) { if (dp[i] && sum-i <= N2) return true; } return false; } void solve() { int N1, N2; cin >> N1 >> N2; if (N1 > N2) swap(N1, N2); int m; cin >> m; vector<int> A(m); for (int i = 0; i < m; i++) cin >> A[i]; sort(A.begin(), A.end()); for (int i = m; i >= 0; i--) { if (isOK(N1, N2, A, i)) { cout << i << endl; return; } } } int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; while (T--) { solve(); } return 0; }