結果
問題 | No.951 【本日限定】1枚頼むともう1枚無料! |
ユーザー |
|
提出日時 | 2019-12-15 01:49:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 909 bytes |
コンパイル時間 | 846 ms |
コンパイル使用メモリ | 83,884 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 10:36:58 |
合計ジャッジ時間 | 4,863 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long int ll; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,k; cin >> n >> k; vector<pair<int,int>>v; for(int i=0;i<n;i++){ int p,d; cin >> p >> d; v.push_back(make_pair(p,d)); } sort(v.begin(),v.end()); vector<vector<vector<int>>> dp(2,vector<vector<int>>(k+1,vector<int>(2,-1e9))); int pre=0,cur=1; dp[pre][0][0]=0; for(int i=n-1;i>=0;i--){ for(int j=0;j<=k;j++){ dp[cur][j][0]=max(dp[cur][j][0],dp[pre][j][0]); dp[cur][j][1]=max(dp[cur][j][1],dp[pre][j][1]); dp[cur][j][0]=max(dp[cur][j][0],dp[pre][j][1]+v[i].second); if(j>=v[i].first){ dp[cur][j][1]=max(dp[cur][j][1],dp[pre][j-v[i].first][0]+v[i].second); } } swap(pre,cur); } int res=0; for(int i=0;i<=k;i++){ res=max(res,dp[pre][i][0]); res=max(res,dp[pre][i][1]); } cout << res << endl; }