結果
問題 | No.1430 Coup de Coupon |
ユーザー |
![]() |
提出日時 | 2021-03-14 14:49:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 1,267 bytes |
コンパイル時間 | 1,999 ms |
コンパイル使用メモリ | 96,816 KB |
最終ジャッジ日時 | 2025-01-19 16:46:20 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> using namespace std; using ll = long long; int dp[5001]; int main() { int n, c; cin >> n >> c; vector<int> p(n); for (int i = 0; i < n; i++) { cin >> p[i]; } sort(p.begin(), p.end()); reverse(p.begin(), p.end()); vector<int> q[2]; for (int i = 0; i < c; i++) { int t, x; cin >> t >> x; q[t - 1].push_back(x); } for (int i = 0; i < 2; i++) { sort(q[i].begin(), q[i].end()); reverse(q[i].begin(), q[i].end()); while ((int)q[i].size() < n) q[i].push_back(0); } constexpr int INF = 1 << 29; for (int j = 0; j <= n; j++) { dp[j] = INF; } dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j >= 0; j--) { int j0 = j; int j1 = i - j; int t0 = 0 < j0 ? dp[j - 1] + max(p[i] - q[0][j0 - 1], 0) : INF; int t1 = 0 <= j1 ? dp[j] + p[i] / 100 * (100 - q[1][j1]) : INF; dp[j] = min(t0, t1); } } int r = INF; for (int j = 0; j <= n; j++) { r = min(r, dp[j]); } cout << r << endl; return 0; }