记录编号	551791	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	ZooxTark➲	是否通过	通过
代码语言	C++	运行时间	1.032 s
提交时间	2020-06-27 12:51:27	内存使用	14.80 MiB

#include <iostream>
#include <cstdio>
#define MAXN 100000
//#define DEBUG

using namespace std;

int w[MAXN],v[MAXN],tot = 0;
int f[MAXN];

int main()
{
#ifndef DEBUG
    freopen("treasure.in","r",stdin);
    freopen("treasure.out","w",stdout);
#endif // DEBUG
    int n,W;
    cin >> n >> W;
    for(int i = 1;i <= n;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        int t = 1;
        while(t <= c)
        {
            v[++tot] = a*t;
            w[tot] = b*t;
            c -= t;
            t <<= 1;
        }
        if(c)
        {
            v[++tot] = a*c;
            w[tot] = b*c;
        }
    }
    for(int i = 1;i <= tot;i++)
    {
        for(int j = W;j >= w[i];j--)
        {
            f[j] = max(f[j],f[j-w[i]] + v[i]);
        }
    }
    cout << f[W];
    return 0;
}