結果
問題 |
No.3076 Goodstuff Deck Builder
|
ユーザー |
|
提出日時 | 2025-03-28 22:20:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 3,000 ms |
コード長 | 1,278 bytes |
コンパイル時間 | 2,250 ms |
コンパイル使用メモリ | 204,492 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-28 22:20:08 |
合計ジャッジ時間 | 4,866 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<pair<int, long long>> cards; long long sumZero = 0; for(int i = 0; i < N; i++){ int c; long long d; cin >> c >> d; if(c == 0) sumZero += d; else cards.push_back({c, d}); } sort(cards.begin(), cards.end(), [](auto &a, auto &b){ return a.first > b.first; }); int maxK = min((int)cards.size(), 10); const int cap = M; const long long NEG = -1LL << 60; vector<vector<long long>> dp(maxK+1, vector<long long>(cap+1, NEG)); dp[0][0] = 0; for(auto &card : cards){ int c = card.first; long long d = card.second; for(int k = maxK - 1; k >= 0; k--){ int mul = 1 << k; for(int e = 0; e <= cap; e++){ if(dp[k][e] == NEG) continue; int ne = e + mul * c; if(ne <= cap) dp[k+1][ne] = max(dp[k+1][ne], dp[k][e] + d); } } } long long ans = 0; for(int k = 0; k <= maxK; k++){ for(int e = 0; e <= cap; e++){ ans = max(ans, dp[k][e]); } } cout << ans + sumZero << "\n"; return 0; }