记录编号	352281	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	0.498 s
提交时间	2016-11-17 06:39:43	内存使用	0.42 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<deque>
using namespace std;
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
struct node
{
	int num,data;
	node(int x,int y)
	{
		num=x;data=y;
	}
};
int f[40010];
int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	int n=read(),v=read();
	for(int i=1;i<=n;i++)
	{
		int c=read(),w=read(),z=read();
		for(int j=0;j<w;j++)
		{
			deque<node> q;
			int x=v/w;
			for(int k=0;k<=x;k++)
			{
				int tem=f[j+k*w]-k*c;
				while(!q.empty()&&q.back().data<=tem)q.pop_back();
				q.push_back(node(k,tem));
				if(q.front().num<k-z)q.pop_front();
				f[j+k*w]=q.front().data+k*c;
			}
		}
	}
	printf("%d",f[v]);
//	system("pause");
}