結果
問題 |
No.1430 Coup de Coupon
|
ユーザー |
![]() |
提出日時 | 2021-03-15 00:54:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 1,579 bytes |
コンパイル時間 | 1,012 ms |
コンパイル使用メモリ | 98,288 KB |
実行使用メモリ | 101,336 KB |
最終ジャッジ日時 | 2024-11-06 13:28:19 |
合計ジャッジ時間 | 2,944 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
/* -*- coding: utf-8 -*- * * 1430.cc: No.1430 Coup de Coupon - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 5000; const int MAX_C = 5000; const int INF = 1 << 30; /* typedef */ /* global variables */ int ps[MAX_N], qs[MAX_C], rs[MAX_C]; int dp[MAX_N + 1][MAX_C + 1]; /* subroutines */ inline void setmin(int &a, int b) { if (a > b) a = b; } /* main */ int main() { int n, c; scanf("%d%d", &n, &c); for (int i = 0; i < n; i++) scanf("%d", ps + i); sort(ps, ps + n, greater<int>()); int qn = 0, rn = 0; for (int i = 0; i < c; i++) { int t, x; scanf("%d%d", &t, &x); if (t == 1) qs[qn++] = x; else rs[rn++] = x; } sort(qs, qs + qn, greater<int>()); sort(rs, rs + rn, greater<int>()); for (int i = 0; i <= n; i++) fill(dp[i], dp[i] + qn + 1, INF); dp[0][0] = 0; for (int i = 0; i < n; i++) for (int j = 0; j <= qn; j++) if (dp[i][j] < INF) { int k = i - j; if (j < qn) setmin(dp[i + 1][j + 1], dp[i][j] + max(ps[i] - qs[j], 0)); if (k < rn) setmin(dp[i + 1][j], dp[i][j] + ps[i] / 100 * (100 - rs[k])); else setmin(dp[i + 1][j], dp[i][j] + ps[i]); } int mind = INF; for (int j = 0; j <= qn; j++) setmin(mind, dp[n][j]); printf("%d\n", mind); return 0; }