记录编号	156861	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	helloworld123	是否通过	通过
代码语言	C++	运行时间	0.134 s
提交时间	2015-04-06 17:52:56	内存使用	0.50 MiB

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;

int n,v,w,zhong,shu;
int f[50001];
void dp2(int zhong,int w)
{
	for (int i=v; i>=zhong; i--)
	{
		if (f[i]<f[i-zhong]+w)
		f[i]=f[i-zhong]+w;
	}
}
void dp1(int w,int zhong,int shu)
{
	int k;
	k=1;
	while (k<shu) 
	{
		dp2(k*zhong,k*w);
		shu=shu-k;
		k*=2;
	}
	dp2(shu*zhong,shu*w);
}
int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	scanf("%d%d",&n,&v);
	for (int i=1; i<=n; i++)
	{
		scanf("%d%d%d",&w,&zhong,&shu);
		dp1(w,zhong,shu);
	}
	cout<<f[v];
	return 0;
}