第13回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#B - IOI 饅頭 (IOI Manju)
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #B - IOI 饅頭 (IOI Manju) https://atcoder.jp/contests/joi2014ho/tasks/joi2014ho2 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll m,n; ll p[100001],c[100001],e[100001],dp[100001],sum[100001]; ll ans; bool comp(ll x,ll y){ return (x>y); } int main(void){ cin>>m>>n; for(ll i=1;i<=m;i++){ cin>>p[i]; dp[i]=1000000000; } for(ll i=1;i<=n;i++){ cin>>c[i]>>e[i]; c[i]=min(c[i],m); } sort(p+1,p+m+1,comp); for(ll i=1;i<=m;i++){ sum[i]=sum[i-1]+p[i]; } for(ll i=1;i<=n;i++){ for(ll j=m;j>=c[i];j--){ dp[j]=min(dp[j],dp[j-c[i]]+e[i]); } for(ll j=m-1;j>=1;j--){ dp[j]=min(dp[j],dp[j+1]); } } for(ll i=1;i<=m;i++){ ans=max(ans,sum[i]-dp[i]); } cout<<ans<<endl; return 0; }