Submission #00045

ソースコード

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define all(v2) v2.begin(),v2.end()
#define fi first
#define se second
#define P pair<int,int>
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
 
int mod=1e9+7;
int inf=INT_MAX;
 
 
//cout<<fixed<<setprecision(5);
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    int n,p; cin>>n>>p;
 
    vector<int> t(n+1),r(n+1),g(n+1);
    for(int i=1;i<=n;i++){
        cin>>t[i]>>r[i]>>g[i];
    }
 
    vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(51,vector<int>(p+1,0)));
    for(int i=2;i<=n;i++){
        for(int t1=t[i]-r[i];t1<=t[i]+r[i];t1++){
            for(int t2=t[i-1]-r[i-1];t2<=t[i-1]+r[i-1];t2++){
                for(int j=0;j<=p;j++){
                    if(dp[i-1][t2][j]==0 && i!=2){
                        continue;
                    }
                    int f=abs(t1-t2);
                    if(j+f<=p){
                        dp[i][t1][j+f]=max(dp[i][t1][j+f],dp[i-1][t2][j]+f*g[i]);
                    }
                }
            }
        }
    }
 
    int ans=0;
    for(int i=0;i<=p;i++){
        for(int j=t[n]-r[n];j<=t[n]+r[n];j++){
            ans=max(ans,dp[n][j][i]);
        }
    }
 
    cout<<ans<<"\n";
 
    return 0;
}

ステータス

項目	データ
問題	0006 - アップダウン
ユーザー名	ei2005
投稿日時	2022-05-25 17:29:17
言語	C++17
状態	Accepted
得点	1
ソースコード長	1341 Byte
最大実行時間	140 ms
最大メモリ使用量	48240 KB

セット

	セット	得点	Cases
1	ALL	1 / 1	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in1.txt	AC	79 ms	30684 KB	1
in2.txt	AC	140 ms	48240 KB	1
in3.txt	AC	48 ms	11752 KB	1
in4.txt	AC	54 ms	15936 KB	1
in5.txt	AC	76 ms	26692 KB	1