#include "festival.h"
#include <algorithm>
#include <utility>
using namespace std;
#define ll long long
ll price[200005], type[200005], idx[200005];
const ll INF = 1000000000000000000LL;
ll f[200005][50];
bool use[200005][50];
bool compare(pair<pair<ll, ll>, int> a1, pair<pair<ll, ll>, int> b1)
{
pair<ll, ll> a = a1.first;
pair<ll, ll> b = b1.first;
ll val1 = a.second == 1 ? INF + a.first : (6LL * a.first * a.second) / (a.second - 1);
ll val2 = b.second == 1 ? INF + b.first : (6LL * b.first * b.second) / (b.second - 1);
return val1 < val2;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int n = P.size();
vector<pair<pair<ll, ll>, int>> pairs;
for (int i = 0; i < n; i++) {
pairs.push_back(make_pair(make_pair((ll)P[i], (ll)T[i]), i));
}
sort(pairs.begin(), pairs.end(), compare);
for (int i = 0; i < n; i++) {
price[i] = pairs[i].first.first;
type[i] = pairs[i].first.second;
idx[i] = pairs[i].second;
}
ll balance = A;
vector<int> ans;
int cur = 0;
while (cur < n) {
ll nbalance = (balance - price[cur]) * type[cur];
if (nbalance < balance) break;
balance = nbalance;
ans.push_back(idx[cur]);
if (balance >= INF) {
for (int j = cur + 1; j < n; j++) {
ans.push_back(idx[j]);
}
return ans;
}
cur++;
}
if (cur == n) return ans;
for (int i = cur; i < n; i++) {
for (int j = 0; j < 50; j++) f[i][j] = -1;
}
f[cur][0] = balance;
f[cur][1] = max((balance - price[cur]) * type[cur], -1LL);
use[cur][1] = true;
int endpt = cur + 1;
while (endpt < n && type[endpt] > 1) endpt++;
for (int i = cur + 1; i < endpt; i++) {
for (int j = 0; j < 50; j++) {
f[i][j] = f[i-1][j];
if (j > 0) {
ll f2 = (f[i-1][j-1] - price[i]) * type[i];
if (f2 > f[i][j]) {
use[i][j] = true;
f[i][j] = f2;
}
}
}
}
int best = 0;
vector<int> bestextra;
vector<int> bestdecreases;
for (int i = 0; i < 50; i++) {
ll remain = f[endpt-1][i];
if (remain < 0) continue;
vector<int> extra;
for (int j = endpt; j < n; j++) {
if (price[j] <= remain) {
remain -= price[j];
extra.push_back(idx[j]);
}
}
if (extra.size() + i > best) {
best = extra.size() + i;
bestextra = extra;
vector<int> decreases;
int x = endpt - 1;
int amt = i;
while (x >= cur) {
if (use[x][amt]) {
decreases.push_back(idx[x]);
amt--;
}
x--;
}
bestdecreases = decreases;
}
}
reverse(bestdecreases.begin(), bestdecreases.end());
for (int x: bestdecreases) {
ans.push_back(x);
}
for (int x: bestextra) {
ans.push_back(x);
}
return ans;
}
