結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
|
提出日時 | 2015-05-03 18:44:07 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 669 bytes |
コンパイル時間 | 1,415 ms |
コンパイル使用メモリ | 160,612 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-10 12:54:42 |
合計ジャッジ時間 | 2,363 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long Int; #define REP(i,n) for(int (i)=0;(i)<(int)(n);++(i)) int dp[10010]; int main() { int T, N; cin >> T >> N; vector<int> c, v; REP(i, N) { int x; cin >> x; c.push_back(x); } REP(i, N) { int x; cin >> x; v.push_back(x); } REP(i, N) { int x = v[i] / 2; while (x > 0) { v.push_back(x); c.push_back(c[i]); x /= 2; } } const int inf = 999999999; REP(i, T + 1) dp[i] = -inf; dp[0] = 0; REP(i, v.size()) { for (int t = T - c[i]; t >= 0; t--) { if (dp[t + c[i]] < dp[t] + v[i]) { dp[t + c[i]] = dp[t] + v[i]; } } } cout << *max_element(dp, dp + T + 1) << endl; }