记录编号	525846	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2018-12-06 20:45:08	内存使用	1.23 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=40010,maxm=100010;
int n,m,f[maxn],a1,a2,a3,v[maxm],sum=0,c[maxm];
int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a1,&a2,&a3);
		int p=1,c1=a2,v1=a1;
		while(p<=a3){
			v[++sum]=v1;c[sum]=c1;
			a3-=p;p<<=1;c1<<=1;v1<<=1;
		}
		if(a3)v[++sum]=a3*a1,c[sum]=a3*a2;
	}
	for(int i=1;i<=sum;i++)
	    for(int j=m;j>=c[i];j--)
	        f[j]=max(f[j],f[j-c[i]]+v[i]);
	printf("%d",f[m]);
	return 0;
}