#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=0; for (int j = 0; j < 4; j++) { if(cv[j]>=sz(v[j])) continue; if((a-v[j][cv[j]].first)*(j+1)>mx){ mx=(a-v[j][cv[j]].first)*(j+1); mxI=j; } } while(mx==-1){ } a=max(MAX_VAL,mx); outp.push_back(v[mxI][cv[mxI]].second); cv[mxI]++; } return outp; }