记录编号	580631	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	1.321 s
提交时间	2023-07-25 15:20:48	内存使用	5.72 MiB

    #include<bits/stdc++.h>
    using namespace std;
    int n,m,top=1,ans[40005];
    struct node{
        int v,w,p;
    }a[100000],b[100000];
    int main(){
        freopen("treasure.in","r",stdin);
        freopen("treasure.out","w",stdout);
          scanf("%d%d",&n,&m);
          for(int i=1;i<=n;i++){
              cin>>a[i].w>>a[i].v>>a[i].p;
          }
          for(int i=1;i<=n;i++){
              int t=1;
              while(a[i].p){
              if(a[i].p>=t){
                  a[i].p-=t;
                  b[top].w=a[i].w*t;
                  b[top].v=a[i].v*t;
                  top++;
              }else{
                  b[top].w=a[i].w*a[i].p;
                  b[top].v=a[i].v*a[i].p;
                  top++;
                  break;
              }          
              t*=2;
              }
    }
              for(int i=1;i<top;i++){
                  for(int j=m;j>=1;j--){
                      if(j>=b[i].v){
                          ans[j]=max(ans[j],ans[j-b[i].v]+b[i].w);
                      }else{
                          ans[j]=ans[j];
                      }
                  }
              }
              printf("%d",ans[m]);
          return 0;     
    }