結果
| 問題 | No.951 【本日限定】１枚頼むともう１枚無料！ |
| ユーザー |
 mugen_1337
|
| 提出日時 | 2021-03-19 23:32:20 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 1,773 bytes |
| コンパイル時間 | 3,886 ms |
| コンパイル使用メモリ | 211,484 KB |
| 実行使用メモリ | 817,024 KB |
| 最終ジャッジ日時 | 2024-04-29 19:25:11 |
| 合計ジャッジ時間 | 5,967 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 2 ms
5,376 KB |
| testcase_08 | AC | 2 ms
5,376 KB |
| testcase_09 | AC | 53 ms
34,432 KB |
| testcase_10 | AC | 31 ms
20,864 KB |
| testcase_11 | AC | 31 ms
21,504 KB |
| testcase_12 | AC | 480 ms
272,384 KB |
| testcase_13 | MLE | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
struct IOSetup{
IOSetup(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(12);
}
} iosetup;
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
for(T &x:v)is>>x;
return is;
}
signed main(){
int n,k;cin>>n>>k;
vector<int> p(n),d(n);
rep(i,n) cin>>p[i]>>d[i];
vector<int> ord(n);
iota(ALL(ord),0);
sort(ALL(ord),[&](int l,int r){return p[l]>p[r];});
vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(k+1,vector<int>(2,-INF)));
dp[0][0][0]=0;
rep(i,n){
rep(j,k+1){
chmax(dp[i+1][j][0],dp[i][j][0]);
chmax(dp[i+1][j][1],dp[i][j][1]);
int cost=p[ord[i]],val=d[ord[i]];
if(j+cost<=k){
chmax(dp[i+1][j+cost][1],dp[i][j][0]+val);
chmax(dp[i+1][j+cost][1],dp[i][j][1]+val);
}
chmax(dp[i+1][j][0],dp[i][j][1]+val);
}
}
int res=0;
rep(i,n+1)rep(j,k+1)rep(l,2) chmax(res,dp[i][j][l]);
cout<<res<<endl;
return 0;
}