結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
|
提出日時 | 2017-04-19 10:01:39 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 2,457 bytes |
コンパイル時間 | 669 ms |
コンパイル使用メモリ | 60,080 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-10 13:17:42 |
合計ジャッジ時間 | 1,863 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include <algorithm>#include <iostream>#define max(a, b) ((a) > (b) ? (a) : (b))using namespace std;int main(int argc, char *argv[]){int T;int N;cin >> T;cin >> N;int cs[N + 1];int vs[N + 1];for (int i = 1; i < N + 1; i++) {cin >> cs[i];}for (int i = 1; i < N + 1; i++) {cin >> vs[i];}int dp[N + 1][T + 1];for (int i = 0; i < T + 1; i++) {dp[0][i] = 0;}for (int j = 0; j < N + 1; j++) {dp[j][0] = 0;}int tmp = 11;int css[N + 1][tmp];int vss[N + 1][tmp];for (int i = 1; i < N + 1; i++) {int v = vs[i];int c = cs[i];for (int k = 0; k < tmp; k++) {css[i][k] = 0;vss[i][k] = 0;}int cnt = 0;vss[i][0] = v;css[i][0] = c;while (v > 0) {cnt++;v /= 2;vss[i][cnt] = vss[i][cnt - 1] + v;css[i][cnt] = css[i][cnt - 1] + c;}}// cout << "c" << endl;// for (int j = 1; j < N + 1; j++) {// for (int i = 0; i < tmp; i++) {// cout << css[j][i] << ", ";// }// cout << endl;// }// cout << endl;//// cout << "v" << endl;// for (int j = 1; j < N + 1; j++) {// for (int i = 0; i < tmp; i++) {// cout << vss[j][i] << ", ";// }// cout << endl;// }// cout << endl;for (int j = 1; j < N + 1; j++) {for (int i = 1; i < T + 1; i++) {dp[j][i] = 0;}}for (int j = 1; j < N + 1; j++) {for (int i = 1; i < T + 1; i++) {for (int k = 0;; k++) {int v = vss[j][k];int c = css[j][k];if (v == 0) break;if (i - c >= 0) {int tmp = max(dp[j - 1][i], dp[j - 1][i - c] + v);dp[j][i] = max(dp[j][i], tmp);}else {int tmp = dp[j - 1][i];dp[j][i] = max(dp[j][i], tmp);break;}}}}// for (int j = 0; j < N + 1; j++) {// for (int i = 0; i < T + 1; i++) {// cout << dp[j][i] << ", ";// }// cout << endl;// }int maxVal = *max_element(&dp[N][0], &dp[N][T + 1]);cout << maxVal;return 0;}