結果
問題 |
No.3076 Goodstuff Deck Builder
|
ユーザー |
|
提出日時 | 2025-03-28 21:21:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 134 ms / 3,000 ms |
コード長 | 1,095 bytes |
コンパイル時間 | 3,981 ms |
コンパイル使用メモリ | 294,260 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2025-03-28 21:21:14 |
合計ジャッジ時間 | 6,915 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1001001001001001001LL; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<pair<int, int>> card; ll ans = 0; for (int i = 0; i < n; i++) { int c, d; cin >> c >> d; if (c == 0) { ans += d; continue; } card.emplace_back(c, d); } sort(card.rbegin(), card.rend()); vector<vector<ll>> dp(11, vector<ll>(m + 1, -INF)); dp[0][0] = 0; for (auto [c, d] : card) { auto ndp = dp; int mul = 1 << 9; for (int p = 9; p >= 0; --p) { for (int nc = m - mul * c; nc >= 0; --nc) { ndp[p + 1][nc + mul * c] = max(ndp[p + 1][nc + mul * c], dp[p][nc] + d); } mul /= 2; } dp = ndp; } ll tmp = -INF; for (int i = 0; i < 10; i++) { tmp = max(*max_element(dp[i].begin(), dp[i].end()), tmp); } cout << ans + tmp << '\n'; return 0; }