JOI春合宿2014 オンラインジャッジから、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#M - ストラップ
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #M - ストラップ https://www.ioi-jp.org/camp/2014/2014-sp-tasks/index.html 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; const int num=2010; int n,a[num],b[num],dp[num][2*num+1]; int main(void){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; } for(int i=0;i<=2*num;i++){ dp[0][i]=-2100000000; } dp[0][num+1]=0; for(int i=0;i<n;i++){ for(int j=0;j<=2*num;j++){ dp[i+1][j]=-2100000000; } for(int j=0;j<=2*num;j++){ int k=j+a[i]-1; if(k<0){ continue; } if(k>2*num){ k=2*num; } dp[i+1][k]=max(dp[i+1][k],dp[i][j]+b[i]); dp[i+1][j]=max(dp[i+1][j],dp[i][j]); } } int ans=0; for(int i=num;i<=2*num;i++){ ans=max(ans,dp[n][i]); } cout<<ans<<endl; return 0; }