第11回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#C - 夜店 (Night Market)
https://www.ioi-jp.org/joi/2011/2012-ho-prob_and_sol/2012-ho.pdf#page=7
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #C - 夜店 (Night Market) https://www.ioi-jp.org/joi/2011/2012-ho-prob_and_sol/2012-ho.pdf#page=7 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,t,s; cin>>n>>t>>s; vector<ll> a(n),b(n); for(ll i=0;i<n;i++){ cin>>a[i]>>b[i]; } vector<vector<ll>> dp(3005,vector<ll>(3005,0)); if(b[0]<=s){ dp[0][b[0]]+=a[0]; } for(ll i=1;i<=t;i++){ dp[0][i]=max(dp[0][i],dp[0][i-1]); } for(ll i=1;i<n;i++){ for(ll j=1;j<=t;j++){ if(j>=b[i] && !(j-b[i]<s && s<j)){ dp[i][j]=max(dp[i-1][j-b[i]]+a[i],dp[i-1][j]); }else{ dp[i][j]=dp[i-1][j]; } } for(ll j=1;j<=t;j++){ dp[i][j]=max(dp[i][j],dp[i][j-1]); } } ll ans=0; for(ll i=s;i<t+1;i++){ ans=max(ans,dp[n-1][i]); } cout<<ans<<endl; return 0; }