记录编号	41650	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.821 s
提交时间	2012-08-07 12:35:58	内存使用	3.43 MiB

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int a[100][3],b,c,d,f[40001],l,m,n,x[40001],y=1,z;
int main(void)
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	scanf("%d%d",&b,&c);
	for (d=0;d<b;d++) scanf("%d%d%d",&a[d][0],&a[d][1],&a[d][2]);
	for (d=0;d<b;d++)
	{
		for (l=1;l<=a[d][2];a[d][2]-=l,l*=2)
			for (m=c;m>=l*a[d][1];m--)
				f[m]=f[m]>f[m-l*a[d][1]]+l*a[d][0]?f[m]:f[m-l*a[d][1]]+l*a[d][0];
		if (a[d][2]>0) for (m=c;m>=a[d][1]*a[d][2];m--) f[m]=f[m]>f[m-a[d][2]*a[d][1]]+a[d][2]*a[d][0]?f[m]:f[m-a[d][2]*a[d][1]]+a[d][2]*a[d][0];
	}
	printf("%d",f[c]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}