結果
問題 |
No.2686 商品券の使い道
|
ユーザー |
![]() |
提出日時 | 2024-03-20 22:10:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 144 ms / 3,000 ms |
コード長 | 1,220 bytes |
コンパイル時間 | 4,440 ms |
コンパイル使用メモリ | 308,520 KB |
実行使用メモリ | 11,520 KB |
最終ジャッジ日時 | 2024-09-30 08:02:50 |
合計ジャッジ時間 | 9,674 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using ll = long long; using ull = unsigned long long; #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define REP(i, m, n) for(int i = (int)(m); i < (int)(n); i++) using namespace std; using namespace atcoder; using mint = modint998244353; const int inf = 1000000007; const ll longinf = 1ll << 60; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q1, q2; cin >> n >> q1 >> q2; vector<ll> a(n), b(n); rep(i, n) cin >> a[i] >> b[i]; int all = 1 << n; vector<ll> dp(all); rep(i, all) { ll v = 0, p = 0; rep(j, n) { if(i >> j & 1) { p += a[j]; v += b[j]; } } if(p <= q1) { dp[i] = v; } } rep(j, n) rep(i, all) { dp[i | (1 << j)] = max(dp[i | (1 << j)], dp[i]); } ll ans = 0; rep(i, all) { ll v = 0, p = 0; rep(j, n) { if(i >> j & 1) { p += a[j]; v += b[j]; } } if(p <= q2) { ans = max(ans, v + dp[(all - 1) ^ i]); } } cout << ans << endl; return 0; }