#include "festival.h" #include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() typedef long long ll; using pi = pair<ll, ll>; using vi = vector<ll>; struct coupon { ll t, p, idx; ll eval(ll R) { ll ans = (R-p)*t; if (R < p) ans = -4e18; else if (R >= 1e16) ans = R; return ans; } bool norm(ll x) { return (t * -p) <= (1-t) * x; } const bool operator<(const coupon &other) { // ad-cb > b - d >= 0 if (t == 1 && other.t == 1) return p < other.p; if (t == 1) return false; else if (other.t == 1) return true; ll x = max(p, other.p); ll fx = (x-p)*t, gx = (x-other.p)*other.t; ll fg = (gx-p)*t, gf = (fx-other.p)*other.t; return fg < gf; // return (1-other.t) * (t * -p) < (1-t) * (other.t * -other.p); // return t == other.t ? p < other.p : t < other.t; } }; vector<int> max_coupons(int A, vector<int> P, vector<int> T) { ll a = A, n = P.size(); ll required = 0, one = 0, two = 0, three = 0, four = 0; vector<coupon> coupons[5]; vector<coupon> cps; for (int i = 0; i < n; i++) { coupons[T[i]].push_back(coupon{T[i], P[i], i}), required += P[i]; cps.push_back(coupons[T[i]].back()); if (T[i] == 1) one++; else if (T[i] == 2) two++; else if (T[i] == 3) three++; else four++; } sort(all(cps)); // cout << one << " " << two << " " << three << " " << four << "\n"; for (int i = 1; i <= 4; i++) sort(all(coupons[i])); vector<ll> pref1; for (int i = 0; i < coupons[1].size(); i++) { if (i == 0) pref1.push_back(coupons[1][i].p); else pref1.push_back(pref1.back() + coupons[1][i].p); } // for (auto &el : cps) cout << el.idx << " "; cout << "\n"; vector<int> best, pos; int b1 = 0, c1 = upper_bound(all(pref1), a) - pref1.begin(); vector<int> unused; for (int i = 0; i < n; i++) { if (cps[i].t == 1) break; if (cps[i].norm(a)) { unused.push_back(i); continue; } if (cps[i].eval(a)<0) { unused.push_back(i); continue; } a = cps[i].eval(a); best.push_back(cps[i].idx); } int m = unused.size(); int k = min(m, 68); vector<ll> dp(k+1, -4e18); vector<vector<ll>> s(k+1); dp[0] = a; for (int i = 0; i < m; i++) { for (int j = k-1; j >= 0; j--) { ll f = cps[unused[i]].eval(dp[j]); if (f < 0) continue; if (f < dp[j+1]) continue; s[j+1] = s[j]; s[j+1].push_back(unused[i]); dp[j+1] = f; } } int b = 0, c = upper_bound(all(pref1), a) - pref1.begin(); for (int i = 1; i <= k; i++) { int c1 = upper_bound(all(pref1), dp[i]) - pref1.begin(); if (s[i].size() + c1 > s[b].size() + c) { b = i; c = c1; } } for (auto &el : s[b]) best.push_back(cps[el].idx); for (int i = 0; i < c; i++) best.push_back(coupons[1][i].idx); return best; }