結果
問題 | No.1430 Coup de Coupon |
ユーザー |
|
提出日時 | 2023-03-30 23:01:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 843 bytes |
コンパイル時間 | 1,746 ms |
コンパイル使用メモリ | 176,064 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 07:48:30 |
合計ジャッジ時間 | 3,606 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 RE * 3 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int n, c, t, x;cin >> n >> c;vector<int> p(n), dp(1);vector<vector<int>> tb(2, vector<int>(n));for(auto &&v : p) cin >> v;for(int i = 0, j = 0, k = 0; i < c; i++){cin >> t >> x;tb[t - 1][t == 1 ? j++ : k++] = x;}sort(tb[0].rbegin(), tb[0].rend());sort(tb[1].rbegin(), tb[1].rend());sort(p.rbegin(), p.rend());for(int i = 0; i < n; i++){vector<int> ndp(i + 2, 1 << 30);for(int j = 0; j <= i; j++){ndp[j] = min(ndp[j], dp[j] + p[i] / 100 * (100 - tb[1][i - j]));ndp[j + 1] = min(ndp[j + 1], dp[j] + max(0, p[i] - tb[0][j]));}swap(dp, ndp);}cout << *min_element(dp.begin(), dp.end()) << '\n';}