#include <bits/stdc++.h> #include <boost/multiprecision/cpp_int.hpp> using namespace std; using boost::multiprecision::cpp_int; std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { int n = (int)P.size(); // coeff[t] = 12 * t / (t-1) for t=2..4 const int coeff[5] = {0, 0, 24, 18, 16}; // ---------- split coupons ---------- vector<pair<long long,int>> cheap; // (price, idx) for T=1 cheap.reserve(n); struct Booster { long long key; // p * coeff[t] (fits in int64 for p up to ~1e9) int p; int t; int idx; }; vector<Booster> boosters; boosters.reserve(n); for (int i = 0; i < n; i++) { int ti = T[i]; int pi = P[i]; if (ti == 1) { cheap.push_back({(long long)pi, i}); } else { long long key = 1LL * pi * coeff[ti]; boosters.push_back({key, pi, ti, i}); } } // ---------- sort ---------- sort(cheap.begin(), cheap.end(), [](const auto& a, const auto& b){ return a.first < b.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; }); // cheap prefix sums in int64: with P up to 1e9 and N up to 2e5 => sum <= 2e14 fits vector<long long> cheap_psum(cheap.size() + 1, 0); vector<int> cheap_idx(cheap.size()); for (size_t i = 0; i < cheap.size(); i++) { cheap_psum[i + 1] = cheap_psum[i] + cheap[i].first; cheap_idx[i] = cheap[i].second; } auto cheap_cnt_from_token = [&](const cpp_int& tok) -> int { // If tok is enormous, we can afford all cheap coupons. static const cpp_int LL_MAX = std::numeric_limits<long long>::max(); if (tok >= LL_MAX) return (int)cheap.size(); long long x = (long long)tok; // safe now auto it = upper_bound(cheap_psum.begin(), cheap_psum.end(), x); return int(it - cheap_psum.begin()) - 1; // k s.t. psum[k] <= x }; // ---------- take all non-decreasing boosters ---------- cpp_int token = A; vector<int> prefix_ids; prefix_ids.reserve(boosters.size()); int i = 0, m = (int)boosters.size(); while (i < m) { const auto &b = boosters[i]; cpp_int p = b.p; cpp_int t = b.t; // token*(t-1) >= p*t <=> token >= p*t/(t-1) if (token * (t - 1) >= p * t) { prefix_ids.push_back(b.idx); token = (token - p) * t; i++; } else break; } // ---------- hard suffix DP ---------- const int K = 61; int h_len = m - i; vector<cpp_int> dp(K + 1, cpp_int(-1)); dp[0] = token; // parent[j][c] = 1 if using hard[j] sets dp[c] at iteration j vector<vector<uint8_t>> parent(h_len, vector<uint8_t>(K + 1, 0)); for (int j = 0; j < h_len; j++) { const auto &b = boosters[i + j]; cpp_int p = b.p; cpp_int t = b.t; int max_c = min(j + 1, K); for (int c = max_c; c >= 1; c--) { if (dp[c - 1] < 0) continue; cpp_int prev = dp[c - 1]; if (prev >= p) { cpp_int cand = (prev - p) * t; if (dp[c] < 0 || cand > dp[c]) { dp[c] = cand; parent[j][c] = 1; } } } } // ---------- evaluate all possibilities ---------- int best_total = -1; int best_c = 0; cpp_int best_token = dp[0]; for (int c = 0; c <= min(K, h_len); c++) { if (dp[c] < 0) continue; int cheap_cnt = cheap_cnt_from_token(dp[c]); int total = i + c + cheap_cnt; if (total > best_total) { best_total = total; best_c = c; best_token = dp[c]; } } // ---------- reconstruct chosen hard subset ---------- vector<int> chosen_hard_pos; chosen_hard_pos.reserve(best_c); int need = best_c; for (int j = h_len - 1; j >= 0 && need > 0; j--) { if (parent[j][need]) { chosen_hard_pos.push_back(j); need--; } } reverse(chosen_hard_pos.begin(), chosen_hard_pos.end()); // ---------- build final answer ---------- vector<int> answer; answer.reserve(prefix_ids.size() + chosen_hard_pos.size() + cheap.size()); for (int id : prefix_ids) answer.push_back(id); for (int pos : chosen_hard_pos) answer.push_back(boosters[i + pos].idx); int cheap_cnt_final = cheap_cnt_from_token(best_token); for (int k = 0; k < cheap_cnt_final; k++) answer.push_back(cheap_idx[k]); return answer; }

festival.cpp:2:10: fatal error: boost/multiprecision/cpp_int.hpp: No such file or directory
    2 | #include <boost/multiprecision/cpp_int.hpp>
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.