#include "festival.h" #include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second int n; vector<vector<pii > > v; vector<int> sz; int appl(int money, int p_, int t_) { return min((int) 1e17, (money - p_) * t_); } vector<signed> max_coupons(signed A, vector<signed> P, vector<signed> T) { n = P.size(); v.resize(5); sz.assign(5, 0); for(int i = 0; i < n; i++) { v[T[i]].pb(mp(P[i], i)); } for(int i = 1; i <= 4; i++) { sort(v[i].begin(), v[i].end()); sz[i] = v[i].size(); } vector<vector<vector<vector<pii > > > > dp(1 + sz[1], vector<vector<vector<pii > > > (1 + sz[2], vector<vector<pii > > (1 + sz[3], vector<pii > (1 + sz[4], mp(-1, -1))))); //vector<vector<vector<vector<int> > > > from(1 + sz[1], vector<vector<vector<int> > > (1 + sz[2], vector<vector<int> > (1 + sz[3], vector<int> (1 + sz[4], 0)))); dp[0][0][0][0] = mp(A, -1); pair<int, vector<int> > best = mp(0, vector<int> {0, 0, 0, 0, 0}); for(int x1 = 0; x1 <= sz[1]; x1++) { for(int x2 = 0; x2 <= sz[2]; x2++) { for(int x3 = 0; x3 <= sz[3]; x3++) { for(int x4 = 0; x4 <= sz[4]; x4++) { if(x1 > 0 && dp[x1 - 1][x2][x3][x4].fi >= v[1][x1 - 1].fi) { dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], mp(appl(dp[x1 - 1][x2][x3][x4].fi, v[1][x1 - 1].fi, 1), 1ll)); } if(x2 > 0 && dp[x1][x2 - 1][x3][x4].fi >= v[2][x2 - 1].fi) { dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], mp(appl(dp[x1][x2 - 1][x3][x4].fi, v[2][x2 - 1].fi, 2), 2ll)); } if(x3 > 0 && dp[x1][x2][x3 - 1][x4].fi >= v[3][x3 - 1].fi) { dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], mp(appl(dp[x1][x2][x3 - 1][x4].fi, v[3][x3 - 1].fi, 3), 3ll)); } if(x4 > 0 && dp[x1][x2][x3][x4 - 1].fi >= v[4][x4 - 1].fi) { dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], mp(appl(dp[x1][x2][x3][x4 - 1].fi, v[4][x4 - 1].fi, 4), 4ll)); } if(dp[x1][x2][x3][x4].fi != -1) { best = max(best, mp(x1 + x2 + x3 + x4, vector<int> {0, x1, x2, x3, x4})); } } } } } vector<signed> ans; while(best.fi != 0) { best.fi--; int which = dp[best.se[1]][best.se[2]][best.se[3]][best.se[4]].se; ans.pb(v[which][best.se[which] - 1].se); best.se[which]--; } reverse(ans.begin(), ans.end()); return ans; }