#include "festival.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; template<class T>bool minimize(T& a, T b){ if(a > b){ a = b; return true; } return false; } template<class T>bool maximize(T& a, T b){ if(a < b){ a = b; return true; } return false; } int n; ll A; vector<int>p, t; namespace sub1{ vector<int>solve(){ vector<int>R(n), ans; iota(R.begin(), R.end(), 0); sort(R.begin(), R.end(), [&] (int i, int j){ return p[i] < p[j]; }); for(int& i : R){ if((A -= p[i]) < 0){ break; } ans.push_back(i); } return ans; } } namespace sub23{ vector<int>solve(){ vector<vector<int>>part(2); for(int i = 0; i < n; i++){ part[t[i] - 1].push_back(i); } for(int i = 0; i < 2; i++){ sort(part[i].begin(), part[i].end(), [&] (int x, int y){ return p[x] < p[y]; }); } vector<ll>f(1, 0); for(int& i : part[0]){ f.push_back(f.back() + p[i]); } f[0] = -1; function<int(ll)>calc = [&] (ll x){ return upper_bound(f.begin(), f.end(), x) - f.begin() - 1; }; int best = calc(A), cnt_2 = 0; for(int i = 0; i < part[1].size(); i++){ if(A < p[part[1][i]]){ break; } if(maximize(best, i + 1 + calc(A = min((A - p[part[1][i]]) << 1LL, INF)))){ cnt_2 = i + 1; } } vector<int>ans(part[1].begin(), part[1].begin() + cnt_2); for(int i = 0; i < best - cnt_2; i++){ ans.push_back(part[0][i]); } return ans; } } namespace sub4{ ll dp[71][71][71][71]; short trace[71][71][71][71]; vector<int>solve(){ vector<vector<int>>part(5); for(int i = 0; i < n; i++){ part[t[i]].push_back(i); } for(int i = 1; i < 5; i++){ sort(part[i].begin(), part[i].end(), [&] (int x, int y){ return p[x] < p[y]; }); } memset(dp, -0x0f, sizeof(dp)); dp[0][0][0][0] = A; vector<int>N; int best = 0; for(int n1 = 0; n1 <= part[1].size(); n1++){ for(int n2 = 0; n2 <= part[2].size(); n2++){ for(int n3 = 0; n3 <= part[3].size(); n3++){ for(int n4 = 0; n4 <= part[4].size(); n4++){ ll x = dp[n1][n2][n3][n4]; if(x < 0){ continue; } minimize(x, INF); if(maximize(best, n1 + n2 + n3 + n4)){ N = {-1, n1, n2, n3, n4}; } if(n1 < part[1].size() && x >= p[part[1][n1]] && maximize(dp[n1 + 1][n2][n3][n4], x - p[part[1][n1]])){ trace[n1 + 1][n2][n3][n4] = 1; } if(n2 < part[2].size() && x >= p[part[2][n2]] && maximize(dp[n1][n2 + 1][n3][n4], (x - p[part[2][n2]]) << 1LL)){ trace[n1][n2 + 1][n3][n4] = 2; } if(n3 < part[3].size() && x >= p[part[3][n3]] && maximize(dp[n1][n2][n3 + 1][n4], (x - p[part[3][n3]]) * 3)){ trace[n1][n2][n3 + 1][n4] = 3; } if(n4 < part[4].size() && x >= p[part[4][n4]] && maximize(dp[n1][n2][n3][n4 + 1], (x - p[part[4][n4]]) << 2LL)){ trace[n1][n2][n3][n4 + 1] = 4; } } } } } vector<int>ans; for(int i = 0; i < best; i++){ int x = trace[N[1]][N[2]][N[3]][N[4]]; ans.push_back(part[x][N[x] - 1]); N[x]--; } reverse(ans.begin(), ans.end()); return ans; } } namespace sub5{ bool check_subtask(){ vector<int>idx(n); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&] (int x, int y){ return ll(p[x]) * t[x] * t[y] + ll(p[y]) * t[y] < ll(p[y]) * t[x] * t[y] + ll(p[x]) * t[x]; }); ll x = A; for(int& i : idx){ if(x < p[i]){ return false; } x = min((x - p[i]) * t[i], INF); } return true; } vector<int>solve(){ vector<int>idx(n); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&] (int x, int y){ return ll(p[x]) * t[x] * t[y] + ll(p[y]) * t[y] < ll(p[y]) * t[x] * t[y] + ll(p[x]) * t[x]; }); return idx; } } namespace sub6{ bool check_subtask(){ for(int i = 0; i < n; i++){ if((A - p[i]) * t[i] >= A){ return false; } } return true; } vector<int>solve(){ vector<int>idx, other; for(int i = 0; i < n; i++){ if(t[i] > 1){ idx.push_back(i); } else{ other.push_back(i); } } sort(other.begin(), other.end(), [&] (int x, int y){ return p[x] < p[y]; }); vector<ll>f(1, 0); for(int& i : other){ f.push_back(f.back() + p[i]); } f[0] = -1; function<int(ll)>calc = [&] (ll x){ return upper_bound(f.begin(), f.end(), x) - f.begin() - 1; }; sort(idx.begin(), idx.end(), [&] (int x, int y){ return ll(p[x]) * t[x] * t[y] + ll(p[y]) * t[y] < ll(p[y]) * t[x] * t[y] + ll(p[x]) * t[x]; }); vector<vector<ll>>dp(idx.size() + 1, vector<ll>(36, -INF)); vector<vector<bool>>trace(idx.size() + 1, vector<bool>(20, false)); dp[0][0] = A; for(int i = 0; i < idx.size(); i++){ for(int j = 0; j < 36; j++){ ll x = dp[i][j]; if(maximize(dp[i + 1][j], x)){ trace[i + 1][j] = false; } if(j < 35 && x >= p[idx[i]] && maximize(dp[i + 1][j + 1], (x - p[idx[i]]) * t[idx[i]])){ trace[i + 1][j + 1] = true; } } } int best_n1 = 0, best = -1; for(int i = 0; i < 36; i++){ if(dp[idx.size()][i] > -1 && maximize(best, i + calc(dp[idx.size()][i]))){ best_n1 = i; } } vector<int>ans; for(int i = idx.size(), j = best_n1; i > 0; i--){ if(trace[i][j]){ j--; ans.push_back(idx[i - 1]); } } reverse(ans.begin(), ans.end()); for(int i = 0; i < best - best_n1; i++){ ans.push_back(other[i]); } return ans; } } namespace sub7{ vector<int>solve(){ vector<int>idx, other; for(int i = 0; i < n; i++){ if(t[i] > 1){ idx.push_back(i); } else{ other.push_back(i); } } sort(other.begin(), other.end(), [&] (int x, int y){ return p[x] < p[y]; }); vector<ll>f(1, 0); for(int& i : other){ f.push_back(f.back() + p[i]); } f[0] = -1; function<int(ll)>calc = [&] (ll x){ return upper_bound(f.begin(), f.end(), x) - f.begin() - 1; }; sort(idx.begin(), idx.end(), [&] (int x, int y){ return ll(p[x]) * t[x] * t[y] + ll(p[y]) * t[y] < ll(p[y]) * t[x] * t[y] + ll(p[x]) * t[x]; }); vector<int>init_ans; int pref = 0; while(pref < idx.size()){ ll nA = (A - p[idx[pref]]) * t[idx[pref]]; if(nA < A){ break; } A = min(nA, INF); init_ans.push_back(idx[pref++]); } int idx_sz = int(idx.size()) - pref; vector<vector<ll>>dp(idx_sz + 1, vector<ll>(36, -INF)); vector<vector<bool>>trace(idx_sz + 1, vector<bool>(20, false)); dp[0][0] = A; for(int i = 0; i < idx_sz; i++){ for(int j = 0; j < 36; j++){ ll x = dp[i][j]; if(maximize(dp[i + 1][j], x)){ trace[i + 1][j] = false; } if(j < 35 && x >= p[idx[i + pref]] && maximize(dp[i + 1][j + 1], (x - p[idx[i + pref]]) * t[idx[i + pref]])){ trace[i + 1][j + 1] = true; } } } int best_n1 = 0, best = -1; for(int i = 0; i < 36; i++){ if(dp[idx_sz][i] > -1 && maximize(best, i + calc(dp[idx_sz][i]))){ best_n1 = i; } } vector<int>ans; for(int i = idx_sz, j = best_n1; i > 0; i--){ if(trace[i][j]){ j--; ans.push_back(idx[i + pref - 1]); } } reverse(ans.begin(), ans.end()); ans.insert(ans.begin(), init_ans.begin(), init_ans.end()); for(int i = 0; i < best - best_n1; i++){ ans.push_back(other[i]); } return ans; } } vector<int>max_coupons(int _A, vector<int>_P, vector<int>_T){ A = _A; swap(p, _P); swap(t, _T); n = p.size(); if(*max_element(t.begin(), t.end()) == 1){ return sub1::solve(); } if(*max_element(t.begin(), t.end()) <= 2){ return sub23::solve(); } if(n <= 70){ return sub4::solve(); } if(sub5::check_subtask()){ return sub5::solve(); } return sub6::check_subtask() ? sub6::solve() : sub7::solve(); }