#include "festival.h" #include <bits/stdc++.h> using namespace std; #define ll long long std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { multiset<pair<ll,ll>>a,b,c,d; a.insert({INT_MAX,-1}); b.insert({INT_MAX,-1}); c.insert({INT_MAX,-1}); d.insert({INT_MAX,-1}); ll sz = P.size(); for (int i=0 ; i<sz; i++) { if (T[i]==1) a.insert({P[i], i}); else { if (T[i]==2) b.insert({P[i], i}); else { if (T[i]==3) c.insert({P[i], i}); else d.insert({P[i], i}); } } } vector<int>res; while (true) { ll a1=A-(*a.begin()).first, a2 = (A-((*b.begin()).first))*2, a3 = (A-((*c.begin()).first))*3, a4 = (A-((*d.begin()).first))*4; if (max({a1,a2,a3,a4})<0) break; if (max({a1,a2,a3,a4})==a1) { A = a1; res.push_back((*a.begin()).second); a.erase(a.begin()); } else { if (max({a1,a2,a3,a4})==a2) { A = a2; res.push_back((*b.begin()).second); b.erase(b.begin()); } else { if (max({a1,a2,a3,a4})==a3) { A = a3; res.push_back((*c.begin()).second); c.erase(c.begin()); } else { A = a4; res.push_back((*d.begin()).second); d.erase(d.begin()); } } } } return res; }