結果
問題 |
No.1430 Coup de Coupon
|
ユーザー |
|
提出日時 | 2023-03-30 22:52:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 975 bytes |
コンパイル時間 | 1,796 ms |
コンパイル使用メモリ | 179,924 KB |
実行使用メモリ | 198,912 KB |
最終ジャッジ日時 | 2024-09-22 07:42:55 |
合計ジャッジ時間 | 5,462 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, c, t, x; cin >> n >> c; vector<ll> p(n); vector<vector<ll>> tb(2); tb[0].reserve(n); tb[1].reserve(n); for(auto &&v : p) cin >> v; for(int i = 0; i < c; i++){ cin >> t >> x; tb[t - 1].emplace_back(x); } for(int i = 0; i < 2; i++){ while(tb[i].size() < n) tb[i].emplace_back(0); sort(tb[i].rbegin(), tb[i].rend()); } sort(p.rbegin(), p.rend()); vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 1ll << 60)); dp[0][0] = 0; for(int i = 0; i < n; i++){ for(int j = 0; j <= i; j++){ dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + p[i] * (100 - tb[1][i - j]) / 100); dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + max(0ll, p[i] - tb[0][j])); } } cout << *min_element(dp[n].begin(), dp[n].end()) << '\n'; }