#include "festival.h" #include <bits/stdc++.h> #define int long long #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using namespace std; vector<vector<vector<vector<int>>>> dp; vector<vector<vector<vector<pair<int,int>>>>> prv; int n; vector<vector<pair<int,int>>> v(4); const int MAX_VAL=1e11; std::vector<signed> max_coupons(signed A, std::vector<signed> P, std::vector<signed> T) { v.resize(4); n=sz(P); for (int i = 0; i < n; i++) v[T[i]-1].push_back({P[i],i}); for (int i = 0; i < 4; i++) sort(all(v[i])); vector<int> pref(sz(v[0])); for (int i = 0; i < sz(v[0]); i++) { pref[i]=v[0][i].first; if(i>0) pref[i]+=pref[i-1]; } int mxI=0; int mx=0; int a=A; for (int i = 0; i <= sz(v[1]); i++) { if(a<0) break; int up=upper_bound(all(pref), a)-pref.begin(); if(i+up>mx){ mx=i+up; mxI=i; } if(i<sz(v[1])) a=min(MAX_VAL,(a-v[1][i].first)*2); } a=A; vector<signed> outp; for (int i = 0; i < mxI; i++) { outp.push_back(v[1][i].second); a=min(MAX_VAL,(a-v[1][i].first)*2); } for (int i = 0; i < sz(v[0]); i++) { if(a<v[0][i].first) break; outp.push_back(v[0][i].second); a-=v[0][i].first; } return outp; }