結果
問題 |
No.1430 Coup de Coupon
|
ユーザー |
![]() |
提出日時 | 2021-03-14 17:11:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 98 ms / 2,000 ms |
コード長 | 954 bytes |
コンパイル時間 | 2,093 ms |
コンパイル使用メモリ | 199,876 KB |
最終ジャッジ日時 | 2025-01-19 17:06:09 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; #include <bits/stdc++.h> using namespace std; int dp[5010][5010]; const int INF=1e9+7; int main(){ int n,c; cin>>n>>c; vector<int> P(n); rep(i,n) cin>>P[i]; sort(ALL(P)); reverse(ALL(P)); vector<int> X1,X2; rep(i,c){ int t,x; cin>>t>>x; if(t==1) X1.push_back(x); else X2.push_back(x); } sort(ALL(X1)); sort(ALL(X2)); reverse(ALL(X1)); reverse(ALL(X2)); int n1=X1.size(); rep(i,5010){ rep(j,5010) dp[i][j]=INF; } dp[0][0]=0; for(int i=0;i<=min(n,c)-1;i++){ for(int j=0;j<=c;j++){ if(j<n1) dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+max(0,P[i]-X1[j])); if(i-j>=0 && i-j<c-n1) dp[i+1][j]=min(dp[i+1][j],dp[i][j]+P[i]/100*(100-X2[i-j])); } } int ans=INF; rep(j,n1+1) ans=min(ans,dp[min(c,n)][j]); for(int i=min(n,c);i<n;i++) ans+=P[i]; cout<<ans<<endl; return 0; }