#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])); dp.resize(n+1, vector<vector<vector<int>>>(sz(v[0])+1, vector<vector<int>>(sz(v[1])+1, vector<int>(sz(v[2])+1,-1)))); prv.resize(n+1, vector<vector<vector<pair<int,int>>>>(sz(v[0])+1, vector<vector<pair<int,int>>>(sz(v[1])+1, vector<pair<int,int>>(sz(v[2])+1,{-1,-1})))); dp[0][0][0][0]=A; int mx=0; int mxI[4]={0,0,0,0}; for (int k = 0; k <= n; k++) { for (int v0 = 0; v0 <= min(k,sz(v[0])); v0++) { for (int v1 = 0; v1 <= min(k-v0,sz(v[1])); v1++) { for (int v2 = 0; v2 <= min(k-v0-v1,sz(v[2])); v2++) { int v3=k-v0-v1-v2; if(v3>sz(v[3])) continue; int a=min(MAX_VAL,dp[k][v0][v1][v2]); if(a==-1) continue; if(k>mx){ mxI[0]=k; mxI[1]=v0; mxI[2]=v1; mxI[3]=v2; mx=k; } mx=max(k,mx); if(mx==n) break; if(v0<sz(v[0])&&v[0][v0].first<=a){ if(dp[k+1][v0+1][v1][v2]<a-v[0][v0].first){ dp[k+1][v0+1][v1][v2]=a-v[0][v0].first; prv[k+1][v0+1][v1][v2]={0,v[0][v0].second}; } } if(v1<sz(v[1])&&v[1][v1].first<=a){ if(dp[k+1][v0][v1+1][v2]<(a-v[1][v1].first)*2){ dp[k+1][v0][v1+1][v2]=(a-v[1][v1].first)*2; prv[k+1][v0][v1+1][v2]={1,v[1][v1].second}; } } if(v2<sz(v[2])&&v[2][v2].first<=a){ if(dp[k+1][v0][v1][v2+1]<(a-v[2][v2].first)*3){ dp[k+1][v0][v1][v2+1]=(a-v[2][v2].first)*3; prv[k+1][v0][v1][v2+1]={2,v[2][v2].second}; } } if(v3<sz(v[3])&&v[3][v3].first<=a){ if(dp[k+1][v0][v1][v2]<(a-v[3][v3].first)*4){ dp[k+1][v0][v1][v2]=(a-v[3][v3].first)*4; prv[k+1][v0][v1][v2]={3,v[3][v3].second}; } } } } } } vector<signed> outp; while(mxI[0]>0){ outp.push_back(prv[mxI[0]][mxI[1]][mxI[2]][mxI[3]].second); if(prv[mxI[0]][mxI[1]][mxI[2]][mxI[3]].first<3) mxI[prv[mxI[0]][mxI[1]][mxI[2]][mxI[3]].first+1]--; mxI[0]--; } reverse(all(outp)); return {outp}; }