結果
問題 |
No.2686 商品券の使い道
|
ユーザー |
![]() |
提出日時 | 2024-03-20 21:21:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 3,000 ms |
コード長 | 3,836 bytes |
コンパイル時間 | 2,365 ms |
コンパイル使用メモリ | 156,428 KB |
最終ジャッジ日時 | 2025-02-20 08:37:46 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <string.h> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <memory> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; long long inf = 1001001001001001001; template <typename T> struct SegmentTree { int n; vector<T> dat; SegmentTree() {} SegmentTree(int N) { n = 1; while(n < N) { n *= 2; } dat.resize(2*n-1,-inf); } void update(int x, T val) { x += n-1; dat[x] = max(dat[x],val); while(x > 0) { x = (x-1)/2; dat[x] = max(dat[2*x+1],dat[2*x+2]); } } T query(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return -inf; if(a <= l && r <= b) return dat[k]; T vl = query(a, b, 2*k+1, l, (l+r)/2); T vr = query(a, b, 2*k+2, (l+r)/2, r); return max(vl, vr); } T query(int a,int b) {//[a,b) return query(a,b,0,0,n); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,M,Q; cin >> N >> M >> Q; vector<int>A(N),B(N); for(int i = 0; i < N; i++) { cin >> A[i] >> B[i]; } int n1 = N/2,n2 = N-n1; vector<array<long long,4>>res; vector<long long>cmp; for(int i = 0; i < (1 << n1); i++) { long long sum1 = 0,sum2 = 0; vector<int>tmp; for(int j = 0; j < n1; j++) { if(1 & (i >> j)) { sum1 += A[j]; sum2 += B[j]; } else { tmp.push_back(j); } } for(int j = 0; j < (1 << tmp.size()); j++) { long long sum3 = 0,sum4 = 0; for(int k = 0; k < tmp.size(); k++) { if(1 & (j >> k)) { sum3 += A[tmp[k]]; sum4 += B[tmp[k]]; } } if(sum1 <= M && sum3 <= Q) { res.push_back({sum1,sum2,sum3,sum4}); cmp.push_back(sum3); } } } sort(res.begin(),res.end()); sort(cmp.begin(),cmp.end()); cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end()); vector<array<long long,4>>res2; for(int i = 0; i < (1 << n2); i++) { long long sum1 = 0,sum2 = 0; vector<int>tmp; for(int j = 0; j < n2; j++) { if(1 & (i >> j)) { sum1 += A[n1+j]; sum2 += B[n1+j]; } else { tmp.push_back(n1+j); } } for(int j = 0; j < (1 << tmp.size()); j++) { long long sum3 = 0,sum4 = 0; for(int k = 0; k < tmp.size(); k++) { if(1 & (j >> k)) { sum3 += A[tmp[k]]; sum4 += B[tmp[k]]; } } if(sum1 <= M && sum3 <= Q) res2.push_back({sum1,sum2,sum3,sum4}); } } sort(res2.rbegin(),res2.rend()); int id = 0; long long ans = 0; SegmentTree<long long>Seg(cmp.size()); for(int i = 0; i < res2.size(); i++) { while(id < res.size() && res[id][0]+res2[i][0] <= M) { int it = lower_bound(cmp.begin(),cmp.end(),res[id][2])-cmp.begin(); Seg.update(it,res[id][1]+res[id][3]); id++; } int it = upper_bound(cmp.begin(),cmp.end(),Q-res2[i][2])-cmp.begin(); ans = max(ans,res2[i][1]+res2[i][3]+Seg.query(0,it)); } cout << ans << "\n"; }