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