//#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<int>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]+v[1][i].ff; } pair<int,int>cnt={-1,-1}; cnt.ff= upper_bound(ps.begin(),ps.end(),A)-ps.begin(); for(int i=0;i<v[2].size();i++){ if(A<v[2][i].ff)break; A-=v[2][i].ff; A*=2; int h= upper_bound(ps.begin(),ps.end(),A)-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; }