結果
問題 | No.393 2本の竹 |
ユーザー |
![]() |
提出日時 | 2020-04-27 18:52:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 142 ms / 1,000 ms |
コード長 | 2,278 bytes |
コンパイル時間 | 1,796 ms |
コンパイル使用メモリ | 174,800 KB |
実行使用メモリ | 24,460 KB |
最終ジャッジ日時 | 2024-11-22 03:18:40 |
合計ジャッジ時間 | 3,192 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
//#include <tourist> #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> p; const int INF = 1e9; const ll LINF = ll(1e18); const int MOD = 1000000007; const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0}; const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; #define yes cout << "Yes" << endl #define YES cout << "YES" << endl #define no cout << "No" << endl #define NO cout << "NO" << endl #define rep(i, n) for (int i = 0; i < n; i++) #define ALL(v) v.begin(), v.end() #define debug(v) \ cout << #v << ":"; \ for (auto x : v) \ { \ cout << x << ' '; \ } \ cout << endl; template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } //cout<<fixed<<setprecision(15);有効数字15桁 //-std=c++14 //-std=gnu++17 ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } int main() { cin.tie(0); ios::sync_with_stdio(false); int d; cin >> d; vector<int> ans(d); rep(k, d) { int d1, d2; cin >> d1 >> d2; int n; cin >> n; vector<int> a(n); rep(j, n) { cin >> a[j]; } sort(ALL(a)); vector<vector<int>> dp(n + 1, vector<int>(d1 + 1, -1)); dp[0][0] = 0; int sum = 0; int anst = 0; rep(i, n) { rep(j, d1 + 1) { if (dp[i][j] >= 0) { chmax(anst, dp[i][j]); int j2 = sum - j; //現在のd2の使用 if (j + a[i] <= d1) dp[i + 1][j + a[i]] = max(dp[i][j] + 1, dp[i + 1][j + a[i]]); //n1に入るならいれる if (j2 + a[i] <= d2) dp[i + 1][j] = max(dp[i][j] + 1, dp[i + 1][j]); } } sum += a[i]; } rep(i,d1+1)chmax(anst,dp[n][i]); ans[k] = anst; } rep(i, d) cout << ans[i] << "\n"; }