记录编号	41651	评测结果	AWWWWWAWWA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	30
用户昵称	fflyt	是否通过	未通过
代码语言	C++	运行时间	0.242 s
提交时间	2012-08-07 13:26:07	内存使用	0.34 MiB

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

int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	
	int n,v;cin>>n>>v;
	
	int save[40001]={0};
	int c,w,num,non[20],nof,weight[20],cost[20],temp;
	int i,j,k;
	for(i=0;i<n;i++)
	{
		cin>>c>>w>>num;
		nof=1;
		non[1]=1;
		temp=0;
		for(j=1;;j++)
		{
			temp+=non[j];
			if(temp<num)
			{
				non[j+1]=2*non[j];
				nof++;
				continue;
			}
			if(temp==num) break;
			if(temp>num)
			{
				non[j]=num-temp+non[j];
				break;
			}
		}
		for(j=1;j<=nof;j++)
		{
			weight[j]=non[j]*w;
			cost[j]=non[j]*c;
		}
		
		for(j=1;j<=nof;j++)
		{
			for(k=v;k>0;k--)
			{
				if(k-weight[j]>0)
				save[k]=max(save[k],save[k-weight[j]]+cost[j]);
				else continue;
			}
			
			
			
		}
		
		
		
	}
	
	int ans=0;
	for(i=v;i>0;i--)
		if(save[i]>ans) ans=save[i];
	
	cout<<ans<<endl;
	
	
	return 0;
}