結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
|
提出日時 | 2014-10-09 23:52:20 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 943 bytes |
コンパイル時間 | 921 ms |
コンパイル使用メモリ | 67,796 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-10 12:47:06 |
合計ジャッジ時間 | 2,027 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include <iostream>#include <vector>#include <set>#include <queue>#include <algorithm>#include <cstring>#include <cstdio>#include <fstream>#include <sstream>using namespace std;typedef long long ll;int T, N;int c[20], v[20];int dp[20][10010];bool done[20][10010];int solve(int k, int t){if(k >= N){return 0;}if(done[k][t]){return dp[k][t];}int V = v[k];int C = c[k];int add = 0;int rest = t;int res = solve(k + 1, t);for(;V > 0 && rest >= C;){rest -= C;add += V;res = max(res, solve(k + 1, rest) + add);V /= 2;}done[k][t] = true;return dp[k][t] = res;}int main(){cin >> T >> N;for(int i=0;i<N;i++)cin >> c[i];for(int i=0;i<N;i++)cin >> v[i];cout << solve(0, T) << endl;return 0;}