結果
問題 | No.1430 Coup de Coupon |
ユーザー |
![]() |
提出日時 | 2021-03-14 14:19:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 1,238 bytes |
コンパイル時間 | 1,877 ms |
コンパイル使用メモリ | 176,740 KB |
実行使用メモリ | 101,384 KB |
最終ジャッジ日時 | 2024-11-06 04:05:13 |
合計ジャッジ時間 | 4,148 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;int dp[5005][5005];int main() {int N,C;cin >> N >> C;vector<int>P(N);for(int i = 0; i < N; i++) {cin >> P[i];}vector<int>X,Y;for(int i = 0; i < C; i++) {int T,C;cin >> T >> C;if(T == 2) {X.push_back(C);}else {Y.push_back(C);}}sort(X.rbegin(),X.rend());sort(Y.rbegin(),Y.rend());sort(P.rbegin(),P.rend());for(int i = 0; i <= N; i++) {for(int j = 0; j <= C; j++) {dp[i][j] = 1e9;}}dp[0][0] = 0;for(int i = 0; i < N; i++) {for(int j = 0; j <= X.size(); j++) {if(dp[i][j] == 1e9) {continue;}if(j < X.size()) {dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]+P[i]/100*(100-X[j]));}if(i >= j && i-j < Y.size()) {dp[i+1][j] = min(dp[i+1][j],dp[i][j]+max(0,P[i]-Y[i-j]));}dp[i+1][j] = min(dp[i+1][j],dp[i][j]+P[i]);}}int ans = 1e9;for(int i = 0; i <= X.size(); i++) {ans = min(ans,dp[N][i]);}cout << ans << endl;}