#include "festival.h" #include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second int n; vector<vector<pii > > v; vector<signed> max_coupons(signed A, vector<signed> P, vector<signed> T) { n = P.size(); v.resize(5); for(int i = 0; i < n; i++) { v[T[i]].pb(mp(P[i], i)); } for(int i = 1; i <= 4; i++) { sort(v[i].begin(), v[i].end()); } vector<int> vec; for(pii p : v[1]) { vec.pb(p.fi); if(vec.size() > 1) { vec[vec.size() - 1] += vec[vec.size() - 2]; } } int money = A; pii best = mp((upper_bound(vec.begin(), vec.end(), money) - vec.begin()), 0); int idx = 0; for(pii p : v[2]) { idx++; if(money < p.fi) { break; } money = (money - p.fi) * 2; if(money > 1e17) { money = 1e17; } best = max(best, mp(idx + (upper_bound(vec.begin(), vec.end(), money) - vec.begin()), idx)); } vector<signed> ans; best.fi -= best.se; for(int i = 0; i < best.se; i++) { ans.pb(v[2][i].se); } for(int i = 0; i < best.fi; i++) { ans.pb(v[1][i].se); } return ans; }