记录编号	80642	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.745 s
提交时间	2013-11-07 14:20:33	内存使用	0.47 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<deque>
#include<set>
using namespace std;
const int SIZEW=4*10000+1;
int N,W;
int f[SIZEW]={0};
void singlerelax(int nowv,int noww){//价值nowv重量noww
	int i;
	for(i=W;i>=noww;i--) f[i]=max(f[i],f[i-noww]+nowv);
	for(i=1;i<=W;i++) f[i]=max(f[i],f[i-1]);
}
void relax(int nowv,int noww,int num){//单件:价值nowv,重量noww,共nowm个
	int ind=1;
	while(true){
		if(num>=ind){
			singlerelax(nowv*ind,noww*ind);
			num-=ind;
		}
		else{
			singlerelax(nowv*num,noww*num);
			return;
		}
		ind*=2;
	}
}
void work(void){
	scanf("%d%d",&N,&W);
	int nowv,noww,nowm;
	int i;
	for(i=1;i<=N;i++){
		scanf("%d%d%d",&nowv,&noww,&nowm);
		relax(nowv,noww,nowm);
	}
}
int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	work();
	printf("%d\n",f[W]);
	return 0;
}