记录编号	238256	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	水墨青花	是否通过	通过
代码语言	C++	运行时间	0.181 s
提交时间	2016-03-18 19:34:18	内存使用	1.07 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

void Read();
void Work();

int n,tot;
int v[50000];
int w[50000];
int m[50000];
int f[50000];

int main()
{
	memset(f,0,sizeof(f));
	memset(v,0,sizeof(v));
	memset(w,0,sizeof(w));
	memset(m,0,sizeof(m));
	
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
		
	Read();
	Work();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

void Read()
{
	scanf("%d%d",&n,&tot);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&v[i],&w[i],&m[i]);
	}
	
}

void Work()
{
	for(int i=1;i<=n;i++)
	{
		int k=1;
		while(k<m[i])
		{
			for(int j=tot;j>=k*w[i];j--)
			{
				f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);
			}
			m[i]-=k;
			k=k<<1;
		}
		
		for(int j=tot;j>=m[i]*w[i];j--)
		{
			f[j]=max(f[j],f[j-m[i]*w[i]]+m[i]*v[i]);
		}
		
	}
	
	printf("%d",f[tot]);
}