记录编号	428034	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	_WA自动机	是否通过	通过
代码语言	C++	运行时间	0.108 s
提交时间	2017-07-24 13:14:22	内存使用	0.31 MiB

#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
int V,f[40000],w[120],c[120],n[1500];
inline void zop(int ci,int wi)
{
    for (int v=V;v>=ci;--v)
        f[v]=max(f[v],f[v-ci]+wi);
}
inline void cp(int ci,int wi)
{
    for (int v=ci;v<=V;++v)
        f[v]=max(f[v],f[v-ci]+wi);
}
inline void mp(int ci,int wi,int ni)
{
    if (ci*ni>=V) {cp(ci,wi);return;}
    int x=1;
    while (x<ni)
    {
        zop(x*ci,x*wi);
        ni-=x;
        x*=2;
    }
    zop(ni*ci,ni*wi);
}
inline int getint()
{
    char c;
    while (!isdigit(c=getchar()));
    int x=c-48;
    while (isdigit(c=getchar()))
        x=x*10+c-48;
    return x;
}
int Main()
{
    #ifndef COGS
    freopen("treasure.in","r",stdin);
    freopen("treasure.out","w",stdout);
    #endif // COGS
    int N=getint();V=getint();
    for (int i=1;i<=N;++i)
    {
        w[i]=getint();
        c[i]=getint();
        n[i]=getint();
    }
    for (int i=1;i<=N;++i)
        mp(c[i],w[i],n[i]);
    printf("%d\n",f[V]);
    return 0;
}
int a=Main();
int main(){;}