結果
問題 | No.951 【本日限定】1枚頼むともう1枚無料! |
ユーザー |
|
提出日時 | 2019-12-14 10:01:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 1,144 bytes |
コンパイル時間 | 757 ms |
コンパイル使用メモリ | 80,576 KB |
実行使用メモリ | 199,088 KB |
最終ジャッジ日時 | 2024-06-28 03:04:15 |
合計ジャッジ時間 | 7,331 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cstring> using namespace std; typedef pair<int,int> pii; int dp[2][5001][5001]; int main(){ memset(dp, -1, sizeof(dp)); dp[0][0][0] = 0; int n, k; cin >> n >> k; vector<pii> v; for(int i = 0; i < n; i++){ int p, d; cin >> p >> d; v.push_back({p, d}); } sort(v.rbegin(), v.rend()); for(int i = 0; i < n; i++){ for(int j = k; j >= 0; j--){ dp[1][i+1][j] = max(dp[1][i+1][j], dp[1][i][j]); dp[0][i+1][j] = max(dp[0][i+1][j], dp[0][i][j]); if(dp[0][i][j] != -1){ if(j+v[i].first <= k) dp[1][i+1][j+v[i].first] = max(dp[1][i+1][j+v[i].first], dp[0][i][j]+v[i].second); } if(dp[1][i][j] != -1){ dp[0][i+1][j] = max(dp[0][i+1][j], dp[1][i][j]+v[i].second); dp[1][i+1][j] = max(dp[1][i+1][j], dp[1][i][j]); } } } int ans = 0; for(int i = 0; i <= k; i++){ ans = max(ans, dp[0][n][i]); ans = max(ans, dp[1][n][i]); } cout << ans << endl; return 0; }