結果
問題 | No.951 【本日限定】1枚頼むともう1枚無料! |
ユーザー |
![]() |
提出日時 | 2019-12-12 21:27:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 773 bytes |
コンパイル時間 | 1,810 ms |
コンパイル使用メモリ | 172,872 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-27 16:09:32 |
合計ジャッジ時間 | 5,083 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct pizza{ int p; int d; }; int main(){ int n, k; cin >> n >> k; vector<pizza> v(n); for(int i = 0; i < n; i++){ cin >> v[i].p >> v[i].d; } sort(v.begin(), v.end(), [](pizza &l, pizza &r){ return l.p < r.p; }); vector<int> dp(k + 1, 0), ma(k + 1, 0); for(int i = 0; i < n; i++){ for(int j = k; j >= v[i].p; j--){ ma[j] = max(ma[j], dp[j] + v[i].d); dp[j] = max(dp[j], ma[j - v[i].p] + v[i].d); } for(int j = v[i].p - 1; j >= 0; j--){ ma[j] = max(ma[j], dp[j] + v[i].d); } } int ans = 0; for(int i = 0; i <= k; i++){ ans = max(ans, dp[i]); } cout << ans << endl; }