记录编号	156864	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	筽邝	是否通过	通过
代码语言	C++	运行时间	0.161 s
提交时间	2015-04-06 18:03:55	内存使用	0.47 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int n,m;
int f[40010];
 
inline void ZeroOneDP(int v,int w)
{
	for (int i=m; i>=v; i--)
		f[i]=max(f[i],f[i-v]+w);
}
 
inline void MultiDP()
{
	for (int i=1; i<=n; i++)
	{
		int V,W,C;
		scanf("%d%d%d",&W,&V,&C);
		for (int k=1; k<=C; k<<=1)
		{
			ZeroOneDP(k*V,k*W);
			C-=k;
		}
		if (C>0)
			ZeroOneDP(C*V,C*W);
	}
} 
 
int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
 
	scanf("%d%d",&n,&m);
	MultiDP();
	printf("%d",f[m]);
 
	return 0;
}