#include "festival.h" using namespace std; #include <bits/stdc++.h> static int how_many_type_1_can_we_buy(long long A2, const vector<long long>& type1_prefix) { // type1_prefix[0] = 0, increasing int k = int(upper_bound(type1_prefix.begin(), type1_prefix.end(), A2) - type1_prefix.begin()) - 1; return max(0, k); } std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { __int128 tokens = A; struct Coupon { long long cost; int type; int index; bool operator<(const Coupon& other) const { if (cost != other.cost) return cost < other.cost; return type > other.type; // your tie-break } }; vector<Coupon> type4, type3, type2, type1; for (int i = 0; i < (int)P.size(); i++) { if(T[i] == 4){ type4.push_back({P[i], T[i], i}); } else if(T[i] == 3) { type3.push_back({P[i], T[i], i}); } else if (T[i] == 2){ type2.push_back({P[i], T[i], i}); } else { type1.push_back({P[i], T[i], i}); } } sort(type4.begin(), type4.end()); sort(type3.begin(), type3.end()); sort(type2.begin(), type2.end()); sort(type1.begin(), type1.end()); vector<long long> type1_prefix(1, 0); type1_prefix.reserve(type1.size() + 1); for (auto &c : type1) { type1_prefix.push_back(type1_prefix.back() + c.cost); } // dp[i][j][k] = max tokens after using i type 2, j type 3, k type 4 struct DPstate { __int128 val; array<int, 3> prev; int item_index; }; vector<vector<vector<DPstate>>> dp(type2.size()+1, vector<vector<DPstate>>(type3.size()+1, vector<DPstate>(type4.size()+1, {0, {0, 0, 0}, -1}))); int best_numitems = 0; array<int, 3> bestDPstate; int best_type1 = 0; dp[0][0][0].val = A; for(int i = 0; i <= type2.size(); i ++){ for(int j = 0; j <= type3.size(); j ++){ for(int k = 0; k <= type4.size(); k ++){ if(i > 0){ DPstate new_state = dp[i-1][j][k]; new_state.val -= type2[i-1].cost; new_state.val *= 2; new_state.prev = {i-1, j, k}; new_state.item_index = type2[i-1].index; if(new_state.val > dp[i][j][k].val && new_state.val >= 0){ dp[i][j][k] = new_state; } } if(j > 0){ DPstate new_state = dp[i][j-1][k]; new_state.val -= type3[j-1].cost; new_state.val *= 3; new_state.prev = {i, j-1, k}; new_state.item_index = type3[j-1].index; if(new_state.val > dp[i][j][k].val && new_state.val >= 0){ dp[i][j][k] = new_state; } } if(k > 0){ DPstate new_state = dp[i][j][k-1]; new_state.val -= type4[k-1].cost; new_state.val *= 4; new_state.prev = {i, j, k-1}; new_state.item_index = type4[k-1].index; if(new_state.val > dp[i][j][k].val && new_state.val >= 0){ dp[i][j][k] = new_state; } } int items_bought = i + j + k; int also_type1 = how_many_type_1_can_we_buy(dp[i][j][k].val, type1_prefix); //cout << also_type1; if(items_bought + also_type1 > best_numitems && dp[i][j][k].item_index != -1){ best_numitems = items_bought + also_type1; bestDPstate = {i, j, k}; best_type1 = also_type1; } } } } //cout << best_numitems; vector<int> res; array<int, 3> cur = bestDPstate; while(1){ res.push_back(dp[cur[0]][cur[1]][cur[2]].item_index); cur = dp[cur[0]][cur[1]][cur[2]].prev; if(cur[0] == 0 && cur[1] == 0 && cur[2] == 0){ break; } } reverse(res.begin(), res.end()); for(int i = 0; i < best_type1; i ++){ res.push_back(type1[i].index); } return res; // baseline: buy only type1 /*long long A_ll = (long long)min<__int128>(tokens, LLONG_MAX); int best = how_many_type_1_can_we_buy(A_ll, type1_prefix); int best_t2 = 0, best_t1 = best; __int128 cur = tokens; for (int i = 0; i < (int)type2.size(); i++) { if (cur < type2[i].cost) break; cur -= type2[i].cost; cur *= 2; if(cur > LONG_LONG_MAX){ best = T.size(); best_t1 = type1.size(); best_t2 = type2.size(); break; } long long cur_ll = (long long)min<__int128>(cur, LLONG_MAX); int can1 = how_many_type_1_can_we_buy(cur_ll, type1_prefix); if (i + 1 + can1 > best) { best = i + 1 + can1; best_t2 = i + 1; best_t1 = can1; } } vector<int> res; res.reserve(best_t2 + best_t1); for (int i = 0; i < best_t2; i++) res.push_back(type2[i].index); for (int i = 0; i < best_t1; i++) res.push_back(type1[i].index); return res;*/ } /* 12 10 1 2 3 2 2 2 6 2 6 2 1 2 2 2 5 1 5 1 5 2 20 1 25 1 State = [how many type 2 we have used][how many type 3 we have used] dp[i][j] = max( (dp[i-1][j] - type2[i].price) * 2, (dp[i][j-1] - type3[i].price) * 3 ) */