#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=1e15; 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])); int cv[4]={0,0,0,0}; vector<signed> outp; int a=A; for (int i = 0; i < n; i++) { int mx=-1; int mxI=-1; for (int j = 0; j < 4; j++) { if(cv[j]>=sz(v[j])) continue; cv[j]++; int mx2=0; for (int k = 0; k < 4; k++) { if(cv[k]==sz(v[k])) continue; mx2=max(v[k].back().first,mx2); } cv[j]--; if((a-v[j][cv[j]].first)*(j+1)>mx&&mx2<=(a-v[j][cv[j]].first)*(j+1)){ mx=(a-v[j][cv[j]].first)*(j+1); mxI=j; } } if(mxI==-1) break; a=min(MAX_VAL,mx); outp.push_back(v[mxI][cv[mxI]].second); cv[mxI]++; } return outp; }