记录编号	240771	评测结果	AAAAAWAWWA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	70
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.189 s
提交时间	2016-03-23 17:54:31	内存使用	0.69 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
#define pop() if(q.front().num+m<k)q.pop_front()
using namespace std;
int f[100010]={0},n,w,c,m,v,mx,k,d,temp;
struct mine{
	int data,num;
	mine(int a=0,int b=0):data(a),num(b){}
};
deque<mine>q;
void push(mine);
void push(int,int);
int main(){
#define COGS
#ifdef COGS
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
#endif
	scanf("%d%d",&n,&v);
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&w,&c,&m);
		for(d=0;d<c;d++){
			q.clear();
			mx=v/c;
			for(k=0;k<=mx;k++){
				temp=f[d+k*c]-k*w;
				push(temp,k);
				pop();
				f[d+k*c]=q.front().data+k*w;
			}
		}
	}
	printf("%d",f[v]);
	return 0;
}
void push(mine x){
	while(!q.empty()&&q.front().data<=x.data)q.pop_back();
	q.push_back(x);
}
inline void push(int data,int num){
	push(mine(data,num));
}