记录编号	41654	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.282 s
提交时间	2012-08-07 17:51:07	内存使用	0.59 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 40000 + 10;
int n, m, v, w, p;
unsigned long long int f[M];
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", &v, &w, &p);
        for(int k=1; k<=p; p-=k, k*=2)
            for(int j=m; j>=w*k; j--)
                f[j] = max(f[j], f[j - w*k] + v*k);
        if(p > 0)
            for(int j=m; j>=w*p; j--)
                f[j] = max(f[j], f[j - w*p] + v*p);
    }
    printf("%lld\n", f[m]);
    return 0;
}