結果
問題 |
No.2686 商品券の使い道
|
ユーザー |
![]() |
提出日時 | 2023-12-16 02:00:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 3,000 ms |
コード長 | 1,246 bytes |
コンパイル時間 | 746 ms |
コンパイル使用メモリ | 87,464 KB |
実行使用メモリ | 19,740 KB |
最終ジャッジ日時 | 2024-09-30 05:05:21 |
合計ジャッジ時間 | 5,452 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <iostream> #include <vector> using namespace std; using i64 = long long; int n; void fast_zeta(vector<i64>& v) { for (int j = 0; j < n; j++) { for (int i = 0; i < (1 << n); i++) { if (i >> j & 1) { v[i] = max(v[i], v[i ^ (1 << j)]); } } } } void slow_zeta(vector<i64>& v) { for (int i = 0; i < (1 << n); i++) { for (int j = i; j >= 0; j--) { j &= i; v[i] = max(v[i], v[j]); } } } int main() { i64 m, q; cin >> n >> m >> q; vector<i64> a(n), b(n); for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; vector<i64> dpm(1 << n), dpq(1 << n); for (int i = 0; i < (1 << n); i++) { i64 p = 0, v = 0; for (int j = 0; j < n; j++) { if (i >> j & 1) { p += a[j]; v += b[j]; } } if (p <= m) dpm[i] = v; if (p <= q) dpq[i] = v; } fast_zeta(dpm); fast_zeta(dpq); // slow_zeta(dpm); // slow_zeta(dpq); int mask = (1 << n) - 1; i64 ans = 0; for (int i = 0; i < (1 << n); i++) { int sub = mask ^ i; ans = max(ans, dpm[i] + dpq[sub]); } cout << ans << endl; }