結果
問題 |
No.3076 Goodstuff Deck Builder
|
ユーザー |
![]() |
提出日時 | 2025-03-28 22:09:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 849 ms / 3,000 ms |
コード長 | 1,994 bytes |
コンパイル時間 | 1,389 ms |
コンパイル使用メモリ | 110,952 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-03-28 22:09:37 |
合計ジャッジ時間 | 16,001 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<pair<int, int>> items(N); for (int i = 0; i < N; i++){ int c, d; cin >> c >> d; items[i] = {c, d}; } // Pythonの sort(reverse=True) と同様に降順ソート sort(items.begin(), items.end(), greater<pair<int,int>>()); const int K = 11; // 選んだ個数の上限 // dp[j][k] : 使ったコストが j で、すでに k 個選んだ時のダメージの最大値 vector<vector<long long>> dp(M + 1, vector<long long>(K, 0)); // exp[k] = 2^k の事前計算 vector<long long> exp(K, 1); for (int i = 1; i < K; i++){ exp[i] = exp[i - 1] * 2; } // 各アイテムについてDPテーブルを更新 for (int i = 0; i < N; i++){ int c = items[i].first; int d = items[i].second; // 新たなDPテーブルの初期化(元のテーブルをコピーする形で更新) vector<vector<long long>> dp_d(M + 1, vector<long long>(K, 0)); for (int j = 0; j <= M; j++){ for (int k = 0; k < K; k++){ // 既存の状態を引き継ぐ dp_d[j][k] = max(dp_d[j][k], dp[j][k]); // 新たにアイテム i を選ぶ場合の遷移 long long new_cost = j + exp[k] * c; if (k==K-1 && c==0){ dp_d[j][k] = max(dp_d[j][k], dp[j][k] + d); } if(k + 1 < K && new_cost <= M){ dp_d[new_cost][k + 1] = max(dp_d[new_cost][k + 1], dp[j][k] + d); }; } } dp = move(dp_d); // 新しいテーブルで更新 } // dp[M]の中で最大値を求める long long ans = 0; for (int k = 0; k < K; k++){ ans = max(ans, dp[M][k]); } cout << ans << "\n"; return 0; }