#include <bits/stdc++.h> using namespace std; // Translate of the given Python function. // Returns the list of chosen coupon original indices (0-based), in the same order // as the Python code builds `answer`. vector<int> max_coupons(long long A, const vector<long long>& P, const vector<int>& T) { int n = (int)P.size(); // ---------- split coupons ---------- vector<pair<long long,int>> cheap; // (price, original_index) for T==1 // boosters: (weight_key, price, t, original_index) struct Booster { long long key; long long p; int t; int idx; }; vector<Booster> boosters; // coeff = 12 * T / (T-1) for T in {2,3,4} -> {24,18,16} unordered_map<int, long long> coeff; coeff[2] = 24; coeff[3] = 18; coeff[4] = 16; long long max_price = 0; for (int i = 0; i < n; i++) { int ti = T[i]; long long pi = P[i]; if (ti == 1) { cheap.push_back({pi, i}); } else { long long key = pi * coeff[ti]; boosters.push_back({key, pi, ti, i}); max_price = max(max_price, pi); } } // ---------- sort ---------- sort(cheap.begin(), cheap.end(), [](auto &a, auto &b){ return a.first < b.first; // cheapest first }); sort(boosters.begin(), boosters.end(), [](const Booster& a, const Booster& b){ if (a.key != b.key) return a.key < b.key; return a.p < b.p; // tie-break by price }); vector<long long> cheap_prices; vector<int> cheap_idx; cheap_prices.reserve(cheap.size()); cheap_idx.reserve(cheap.size()); for (auto &cp : cheap) { cheap_prices.push_back(cp.first); cheap_idx.push_back(cp.second); } // prefix sums of cheap prices // cheap_psum[k] = sum of first k cheap prices, cheap_psum[0]=0 vector<long long> cheap_psum; cheap_psum.reserve(cheap_prices.size() + 1); cheap_psum.push_back(0); for (long long p : cheap_prices) { cheap_psum.push_back(cheap_psum.back() + p); } auto bisect_right = [&](const vector<long long>& arr, long long x) -> int { // returns first index > x return (int)(upper_bound(arr.begin(), arr.end(), x) - arr.begin()); }; // ---------- take all non-decreasing boosters ---------- long long token = A; vector<int> prefix_ids; // original indices of taken prefix boosters int i = 0; int m = (int)boosters.size(); while (i < m) { const auto& b = boosters[i]; long long p = b.p; int t = b.t; int idx = b.idx; // Python: if token * (t - 1) >= p * t // Use __int128 to avoid overflow. __int128 L = (__int128)token * (t - 1); __int128 R = (__int128)p * t; if (L >= R) { prefix_ids.push_back(idx); // token = (token - p) * t token = (token - p) * (long long)t; i++; } else { break; } } // ---------- hard suffix ---------- vector<Booster> hard; for (int k = i; k < m; k++) hard.push_back(boosters[k]); int h_len = (int)hard.size(); const int K = 61; // safe upper bound per original code vector<long long> dp(K + 1, -1); dp[0] = token; // predecessor table: parent[j][c] = 1 iff hard[j] used for dp[c] vector<vector<uint8_t>> parent(h_len, vector<uint8_t>(K + 1, 0)); for (int j = 0; j < h_len; j++) { long long p = hard[j].p; int t = hard[j].t; int max_c = min(j + 1, K); for (int c = max_c; c >= 1; c--) { long long prev = dp[c - 1]; if (prev >= p) { long long cand = (prev - p) * (long long)t; if (cand > dp[c]) { dp[c] = cand; parent[j][c] = 1; } } } } // ---------- evaluate all possibilities ---------- int best_total = -1; int best_c = 0; long long best_token = dp[0]; for (int c = 0; c <= min(K, h_len); c++) { long long cur = dp[c]; if (cur < 0) continue; // cheap_cnt = bisect_right(cheap_psum, cur) - 1 int cheap_cnt = bisect_right(cheap_psum, cur) - 1; int total = i + c + cheap_cnt; if (total > best_total) { best_total = total; best_c = c; best_token = cur; } } // ---------- reconstruct the chosen hard subset ---------- vector<int> chosen_hard; // indices (within hard) chosen by DP int need = best_c; for (int j = h_len - 1; j >= 0; j--) { if (need == 0) break; if (parent[j][need]) { chosen_hard.push_back(j); need--; } } reverse(chosen_hard.begin(), chosen_hard.end()); // keep original order // ---------- build the final answer ---------- vector<int> answer; // prefix boosters answer.insert(answer.end(), prefix_ids.begin(), prefix_ids.end()); // hard boosters selected by DP // Note: same as python, we just append indices; token already best_token token = best_token; for (int j : chosen_hard) { answer.push_back(hard[j].idx); } // cheap coupons as many as we can afford now int cheap_cnt_final = bisect_right(cheap_psum, token) - 1; for (int k = 0; k < cheap_cnt_final; k++) { answer.push_back(cheap_idx[k]); } return answer; }

/usr/bin/ld: /tmp/ccUFNNRa.o: in function `main':
grader.cpp:(.text.startup+0x22a): undefined reference to `max_coupons(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status