結果
問題 | No.1430 Coup de Coupon |
ユーザー |
|
提出日時 | 2021-03-14 14:12:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 997 bytes |
コンパイル時間 | 901 ms |
コンパイル使用メモリ | 79,388 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-06 03:55:55 |
合計ジャッジ時間 | 2,705 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
コンパイルメッセージ
main.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 8 | main() | ^~~~
ソースコード
#include<iostream>#include<algorithm>#include<vector>using namespace std;int N,C;int P[5050];int dp[2][5050];main(){cin>>N>>C;for(int i=0;i<N;i++)cin>>P[i];sort(P,P+N);reverse(P,P+N);vector<int>A,B;for(int i=0;i<C;i++){int t,x;cin>>t>>x;if(t==1)A.push_back(x);else B.push_back(x);}sort(A.begin(),A.end());reverse(A.begin(),A.end());sort(B.begin(),B.end());reverse(B.begin(),B.end());int now=0;for(int i=1;i<=A.size();i++)dp[now][i]=1e9;for(int i=0;i<N;i++){int nxt=1-now;for(int j=0;j<=A.size();j++)dp[nxt][j]=1e9;for(int j=0;j<=A.size();j++)if(dp[now][j]<(int)1e9){if(j<A.size()){dp[nxt][j+1]=min(dp[nxt][j+1],dp[now][j]+max(P[i]-A[j],0));}int k=i-j;if(k<B.size()){dp[nxt][j]=min(dp[nxt][j],dp[now][j]+P[i]/100*(100-B[k]));}else{dp[nxt][j]=min(dp[nxt][j],dp[now][j]+P[i]);}}now=nxt;}int ans=1e9;for(int j=0;j<=A.size();j++)ans=min(ans,dp[now][j]);cout<<ans<<endl;}