結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
|
提出日時 | 2015-02-04 02:54:15 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 957 bytes |
コンパイル時間 | 674 ms |
コンパイル使用メモリ | 65,256 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-23 07:22:33 |
合計ジャッジ時間 | 1,706 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 WA * 1 |
ソースコード
#include <iostream>#include <cstdio>#include <vector>#include <algorithm>#include <utility>using namespace std;int main() {int t, n;cin >> t >> n;vector<int> c(n, 0); // timevector<int> v(n, 0); // satisfactionfor (int i = 0; i < n; i++) {cin >> c[i];}for (int i = 0; i < n; i++) {cin >> v[i];}vector< vector<int> > memo(n + 1, vector<int>(t + 1, -1));memo[0][0] = 0;for (int i = 0; i < n; i++) {for (int j = t - 1; j >= 0; j--) {if (memo[i][j] != -1) {memo[i+1][j] = memo[i][j];int point = v[i];int add = 0;for (int k = 1; point > 0; k++, point /= 2) {int now = j + k * c[i];if (now <= t) {add += point;if (memo[i+1][now] < memo[i][j] + add) {memo[i+1][now] = memo[i][j] + add;} else {break;}}}}}}int ans = 0;for (int i = t; i >= 0; i--) {ans = max(memo[n][i], ans);}cout << ans << endl;return 0;}