//#include "festival.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define ff first #define ss second #define ll long long std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { int N=P.size(); vector<vector<pair<int,int>>> v(5); for(int i=0;i<N;i++){ v[T[i]].pb({P[i],i}); } for(int i=1;i<=2;i++){ sort(v[i].begin(),v[i].end()); } // ps? vector<ll>ps((int)v[1].size()); if(v[1].size()>0){ ps[0]=v[1][0].ff; } for(int i=1;i<v[1].size();i++){ ps[i]=ps[i-1]+(ll)v[1][i].ff; } // CAP to avoid overflow: sum of all prices is enough for our checks ll cap = 0; for(int i=0;i<N;i++) cap += (ll)P[i]; pair<int,int> cnt={0,0}; // <<< FIX: init second component to 0 cnt.ff = upper_bound(ps.begin(),ps.end(),A)-ps.begin(); ll H=A; for(int i=0;i<v[2].size();i++){ // keep H bounded to avoid overflow but large enough for affordability checks if(H > cap) H = cap; if(v[2][i].ff>H) break; H -= v[2][i].ff; // multiply by 2 without overflowing: if H already large, clamp to cap if(H > cap/2) H = cap; else H = H * 2; int h= upper_bound(ps.begin(),ps.end(),H)-ps.begin(); cnt=max(cnt,{i+1+h,i+1}); } vector<int>ans; for(int i=0;i<cnt.ss;i++){ ans.pb(v[2][i].ss); } for(int i=0;i<cnt.ff-cnt.ss;i++){ ans.pb(v[1][i].ss); } return ans; }