結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
|
提出日時 | 2017-07-03 16:00:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 2,110 bytes |
コンパイル時間 | 1,717 ms |
コンパイル使用メモリ | 173,900 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-10-10 13:20:29 |
合計ジャッジ時間 | 2,947 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>#define show(x) cout << #x << " = " << x << endlusing namespace std;using ll = long long;using pii = pair<int, int>;using vi = vector<int>;template <typename T>ostream& operator<<(ostream& os, const vector<T>& v){os << "sz=" << v.size() << "\n[";for (const auto& p : v) {os << p << ",";}os << "]\n";return os;}template <typename S, typename T>ostream& operator<<(ostream& os, const pair<S, T>& p){os << "(" << p.first << "," << p.second<< ")";return os;}constexpr ll MOD = 1e9 + 7;template <typename T>constexpr T INF = numeric_limits<T>::max() / 100;int main(){int T, N;cin >> T >> N;vector<int> cost(N);vector<int> val(N);for (ll i = 0; i < N; i++) {cin >> cost[i];}for (ll i = 0; i < N; i++) {cin >> val[i];}for (ll i = 0; i < N; i++) {int v = val[i] / 2;while (v > 0) {cost.push_back(cost[i]);val.push_back(v);v /= 2;}}// show(val);// show(cost);const int size = cost.size();vector<vector<int>> dp(size + 1, vector<int>(T + 1, -1)); // i番目のアトラクションまでチェックして残り時間t の最大幸福dp[0][T] = 0;for (ll i = 1; i <= size; i++) {// show(dp);const int v = val[i - 1];const int tim = cost[i - 1];for (ll t = 0; t <= T; t++) {if (t + tim > T) {if (dp[i - 1][t] != -1) {dp[i][t] = dp[i - 1][t];}} else {if (dp[i - 1][t + tim] != -1) {dp[i][t] = max(dp[i][t], dp[i - 1][t + tim] + v);}if (dp[i - 1][t] != -1) {dp[i][t] = max(dp[i][t], dp[i - 1][t]);}}}}// show(dp);int ans = 0;for (ll i = 0; i <= T; i++) {if (dp[size][i] != -1) {ans = max(ans, dp[size][i]);}}cout << ans << endl;return 0;}