记录编号	192216	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2015-10-10 06:26:59	内存使用	11.73 MiB

#include<cstdio>

using namespace std;
int n,m,v[1000005],w[1000005],f[1000005];
int vi,wi,t,ne,num;
int main(){
    freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		t=1;
		scanf("%d%d%d",&vi,&wi,&num);
		while(num>=t){
			v[++ne]=vi*t; w[ne]=wi*t;
			num-=t; t*=2;
		}
		v[++ne]=num*vi; w[ne]=num*wi;
	}
	for(int i=1;i<=ne;++i)
	 for(int j=m;j>=w[i];--j)
	  if(f[j]<f[j-w[i]]+v[i]) f[j]=f[j-w[i]]+v[i];
	printf("%d",f[m]);
	getchar();getchar();
}