ACwing原题链接

RT，样例过力

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
const int MAXN=1010,MAXV=2e4+10;
int n,V,f[MAXV],p[MAXN],num[MAXN],pos[MAXN],head,tail;
main()
{
	n=read(),V=read();
	for(register int i=1,v,w,s;i<=n;++i)
	{
		v=read(),w=read(),s=read();
		for(register int d=0;d<v;++d)
		{
			head=1,tail=0;
			for(register int j=d;j<=V;j+=v)
			{
				if(head<=tail&&(j/v-pos[head])>s) head++;
				while(head<=tail&&num[tail]<=f[j]-j/v*w) tail--;
				pos[++tail]=j/v,num[tail]=f[j]-j/v*w;
				if(head<=tail-1) f[j]=num[head]+j/v*w;
			}
		}
	}
	printf("%lld\n",f[V]);return 0;
}