//#include "festival.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define ff first #define ss second #define ll long long ll dp[80][80][80][80]; int op[80][80][80][80]; 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); ll MX=0; for(int i=0;i<N;i++){ v[T[i]].pb({P[i],i}); MX+=P[i]; } for(int i=1;i<5;i++){ sort(v[i].begin(),v[i].end()); } for(int a=0;a<=v[1].size();a++){ for(int b=0;b<=v[2].size();b++){ for(int c=0;c<=v[3].size();c++){ for(int d=0;d<=v[4].size();d++){ dp[a][b][c][d]=-1; } } } } dp[0][0][0][0]=A; for(int a=0;a<=v[1].size();a++){ for(int b=0;b<=v[2].size();b++){ for(int c=0;c<=v[3].size();c++){ for(int d=0;d<=v[4].size();d++){ if(a!=v[1].size()){ dp[a+1][b][c][d]=max(dp[a+1][b][c][d], dp[a][b][c][d]-v[1][a].ff); if(dp[a+1][b][c][d]==dp[a][b][c][d]-v[1][a].ff)op[a+1][b][c][d]=1; dp[a+1][b][c][d]=min(MX,dp[a+1][b][c][d]); } if(b!=v[2].size()){ dp[a][b+1][c][d]=max(dp[a][b+1][c][d], (dp[a][b][c][d]-v[2][b].ff)*2); if(dp[a][b+1][c][d]==(dp[a][b][c][d]-v[2][b].ff)*2)op[a][b+1][c][d]=2; dp[a][b+1][c][d]=min(MX, dp[a][b+1][c][d]); } if(c!=v[3].size()){ dp[a][b][c+1][d]=max(dp[a][b][c+1][d], (dp[a][b][c][d]-v[3][c].ff)*3); if(dp[a][b][c+1][d]==(dp[a][b][c][d]-v[3][c].ff)*3)op[a][b][c+1][d]=3; dp[a][b][c+1][d]=min(MX,dp[a][b][c+1][d]); } if(d!=v[4].size()){ dp[a][b][c][d+1]=max(dp[a][b][c][d+1], (dp[a][b][c][d]-v[4][d].ff)*4); if(dp[a][b][c][d+1]==((dp[a][b][c][d]-v[4][d].ff)*4))op[a][b][c][d+1]=4; dp[a][b][c][d+1]=min(MX,dp[a][b][c][d+1]); } } } } } ll g=0; vector<int>cur={0,0,0,0}; for(int a=0;a<=v[1].size();a++){ for(int b=0;b<=v[2].size();b++){ for(int c=0;c<=v[3].size();c++){ for(int d=0;d<=v[4].size();d++){ if(dp[a][b][c][d]>=0){ g=max(g,(ll)a+b+c+d); if(g==(ll)a+b+c+d){ cur={a,b,c,d}; } } } } } } vector<int>f={0,0,0,0}; vector<int>tmp; while(cur!=f){ int u=op[cur[0]][cur[1]][cur[2]][cur[3]]; cur[u-1]--; tmp.pb(u); } vector<int>ans; for(int i=1;i<=4;i++)reverse(v[i].begin(),v[i].end()); while(tmp.size()){ ans.pb(v[tmp.back()].back().ss); v[tmp.back()].pop_back(); tmp.pop_back(); } return ans; }