特别典的题，vp 花了三小时做完了。

$5$ 分的子任务一点用都没有，我们考虑 $T_i\le 2$。

显然的是，手里硬币越多，买这个物品亏损越少（赚的越多）。

注意到可以分为 $T_i=1$ 和 $T_i=2$ 两类，分别考虑。对于每一类，我们显然按照 $p_i$ 排序，显然如果选了 $p_i$ 大的，不选小的是不优秀的，所以我们选一个前缀。

枚举 $T_i=2$ 选哪些前缀，然后 $T_i=1$ 前缀和二分即可。

这告诉我们似乎 $T_i=1$ 要单独考虑。

我们发现子任务 $5$ 的分数很多。

不用发现，其实当我们看到我们不知道什么顺序选的时候就可以试试排序贪心。

买不起如果硬买，卖完手里的钱肯定是负的，不用特殊考虑。

我们考虑两个物品怎么做。

为了好写，记第一个物品的 $P_1=a$，$T_1=b$，$P_2=c$，$T_2=d$。

设本来有 $x$ 硬币，都购买后为 $((x-a)\times b-c)\times d=bdx-abd-cd$。

反着买就是 $bdx-abd-cd>bdx-bcd-ab$。

得到 $abd+cd<bcd+ab$。

同时除以 $bd$，得到 $a+\frac{c}{b}<c+\frac{a}{d}$。

移项得到 $a-\frac{a}{d}<c-\frac{c}{b}$。

整理得到 $a(1-\frac{1}{d})<c(1-\frac{1}{b})$。

之后显然得到 $\frac{a}{1-\frac{1}{b}}<\frac{c}{1-\frac{1}{d}}$。

为了好看，得到 $\frac{ab}{b-1}<\frac{cd}{d-1}$。

显然有传递性！所以可以排序，注意 $T_i=1$ 单独处理，不过显然都是 $T_i=1$ 就按照 $P_i$ 升序排序，并且先吃 $T_i=1$，再吃 $T_i>1$，相当于让 $T_i>1$ 的变差了，其它不变，所以不好，所以 $T_i=1$ 排在最后。

最后就是在一个序列上求一个最长子序列，使得满足条件。

我们直接把排完序数组的返回就可以获得子任务分数。

如果没啥追求，这时候写部分分，$n\le70$ 其实就是把东西按照 $T_i$ 分类之后每类 $P_i$ 升序排序，然后类分别卖多少件为状态 DP。

这告诉我们这道题要 DP。

一个显然的平方 DP，就是只考虑前 $i$ 件，买了 $j$ 件，此时硬币最多。

平方没分啊。

我们这时候会思考子任务 $6$，不过如果我们继续想贪心会自然想到如果能完成子任务 $6$，那么这道题就做完了。

咋做呢？

我们排序贪心根据定义，有个性质就是先选后面的再选前面的不优秀。

如果我们考虑到我们购买可以分为两段，分别是买了赚硬币和买了亏硬币。

为啥呢？如果亏了之后再赚，还不如先赚再亏，这样二者都能变得优秀。

我们考虑从头开始跑，如果发现买了会赚就直接买，根据定义可知不能先买后面再买前面。

然后如果亏了呢？

如果我先买了后面的会赚，那么我们为了让二者更优秀，可以先买后面的再买这个，相比于先买这个再买后面优秀，不符合定义，所以不存在。

所以我们贪心的从头试图买，能赚（或者不赚不亏）就买，亏就直接跑，跳出循环。剩下的就是子任务 $6$ 了。

瓶颈在于平方 DP。

然而，我们突然发现，这个购买的式子足够特别，根据不考虑 $T_i=1$ 似乎能买的很少。

因为原来买就是亏得，假设亏 $1$。

买了前面的，硬币个数变小，根据式子显然亏得更多，减少多少就多亏多少倍 $T_i-1$。

最坏就是 $T_i=2$，然而即使这样，我们亏得也是一倍一倍增长的，所以我们最多能买 $O(\log A)$ 个产品！

于是我们 DP 的第二维就变成了 $\log$ 量级的。

处理完 $T_i\not=1$，再随便枚举前面选几个，前缀和二分就能处理。

于是我们就做完了。

//#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
	int p,t,c;
}a[1000009];
int n;
bool cmp(st a1,st a2){
	if(a1.t==a2.t&&a1.t==1){
		return a1.p<a2.p;
	}
	return a1.p*a1.t*(a2.t-1)<a2.p*a2.t*(a1.t-1);
}
vector<int> dp;
vector<bool> zz[200009];
int l,r;vector<signed> ans;
void dfs(int x,int y){
	if(x<l){
		return;
	}
	if(y==0){
		return;
	}
	if(zz[x][y]){
		dfs(x-1,y-1);
		ans.push_back(a[x].c);
	}else{
		dfs(x-1,y);
	}
}
std::vector<signed> max_coupons(signed aa, std::vector<signed> pp, std::vector<signed> tt) {
	int A;
	A=aa;
	vector<int> P,T;
	P.clear(),T.clear();
	for(int i=0;i<pp.size();i++){
		P.push_back(pp[i]);
		T.push_back(tt[i]);
	}
	for(int i=0;i<(int)P.size();i++){
		a[i]={P[i],T[i],i};
	}
	n=P.size();
	sort(a,a+n,cmp);
	r=n;
	while(r>0&&a[r-1].t==1){
		r--;
	}
	l=r;
	
	ans.clear();
	for(int i=0;i<r;i++){
		if((A-a[i].p)*a[i].t>=A){
			A=(A-a[i].p)*a[i].t;ans.push_back(a[i].c);
			if(A>1e16){
				ans.clear();
				for(int i=0;i<n;i++){
					ans.push_back(a[i].c);
                }
				return ans;
			}
		}else{
			l=i;
			break;
		}
	}
	for(int i=r+1;i<n;i++){
		a[i].p+=a[i-1].p;
	}
	dp.clear();
	dp.push_back(A);
	for(int i=0;i<n;i++){
		zz[i].clear();
	}
	for(int i=l;i<r;i++){
		int g;
		g=dp.size();
		for(int j=0;j<g;j++){
			zz[i].push_back(0);
		}
		if((dp[g-1]-a[i].p)*a[i].t>=0){
			dp.push_back((dp[g-1]-a[i].p)*a[i].t);
			zz[i].push_back(1);
		}
		for(int j=g-2;j>=0;j--){
			if((dp[j]-a[i].p)*a[i].t>dp[j+1]){
				dp[j+1]=(dp[j]-a[i].p)*a[i].t;
				zz[i][j+1]=1;
			}
		}
	}
	int ma,ms;
	ma=ms=0;
	for(int i=0;i<dp.size();i++){
		int p;
		p=0;
		int ll,rr;
		ll=r,rr=n-1;
		while(ll<rr){
			int mid;
			mid=ll+rr+1;
			mid>>=1;
			if(dp[i]>=a[mid].p){
				p=mid-r+1;
				ll=mid;
			}else{
				rr=mid-1;
			}
		}
		if(i+p>ma){
			ma=i+p;
			ms=i;
		}
	}
	dfs(r-1,ms);
	A=dp[ms];
	for(int i=n-1;i>r;i--){
		a[i].p-=a[i-1].p;
	}
	for(int i=r;i<n;i++){
		if(A>=a[i].p){
			A-=a[i].p;
			ans.push_back(a[i].c);
		}
	}
  	return ans;
}

注意可能会爆 long long，这时候显然可以一锅端，特殊处理一下即可。

不处理会获得 $66$ 分，但是最后两个子任务都能过，别问我咋知道的。