結果
問題 | No.2686 商品券の使い道 |
ユーザー |
![]() |
提出日時 | 2024-03-20 22:56:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 251 ms / 3,000 ms |
コード長 | 1,241 bytes |
コンパイル時間 | 4,170 ms |
コンパイル使用メモリ | 250,764 KB |
最終ジャッジ日時 | 2025-02-20 09:54:37 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep(i, n) for(int i=0;i<(n);++i) #define rep1(i, n) for(int i=1;i<=(n);i++) #define ll long long using mint = modint998244353; using P = pair<ll,ll>; using lb = long double; using T = tuple<ll, ll, ll>; #ifdef LOCAL # include <debug_print.hpp> # define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define dbg(...) (static_cast<void>(0)) #endif int main() { int n, m, q; cin >> n >> m >> q; vector<ll> a(n), b(n); rep(i,n) cin >> a[i] >> b[i]; vector<ll> c(1<<n), v(1<<n); vector<ll> dp(1<<n, -1e18), ep(1<<n, -1e18); rep(i,1<<n){ rep(j,n) if(i>>j&1){ c[i] += a[j]; v[i] += b[j]; } } rep(i,1<<n){ if(c[i]<=m) dp[i] = max(dp[i], v[i]); rep(j,n){ dp[i|(1<<j)] = max(dp[i|1<<j], dp[i]); } } rep(i,1<<n){ if(c[i]<=q) ep[i] = max(ep[i], v[i]); rep(j,n){ ep[i|(1<<j)] = max(ep[i|1<<j], ep[i]); } } int mask = (1<<n)-1; ll ans = 0; dbg(dp, ep); rep(i,1<<n){ ans = max(ans, dp[i]+ep[i^mask]); } cout<<ans<<endl; return 0; }