一飞冲天xqc @ 2018-02-24 17:14:58

by 一飞冲天xqc @ 2018-02-24 17:18:11

include<iostream>

include<cstdio>

include<cmath>

include<algorithm>

using namespace std; int dp[3201],a[61],b[61],p,vs[61],v1[61],v2[61],w1[61],w2[61]; int main() { int n,m; cin>>n>>m; n/=10; for(int i=1;i<=m;i++) {
cin>>a[i]>>b[i]>>p; a[i]/=10,vs[i]=p; if( p && !v1[p])

    {
        v1[p]=a[i];
        w1[p]=a[i]*b[i];
    }   
    if(p && v1[p])          //是附件且所附主件现有一附件
    {
        v2[p]=a[i];
        w2[p]=a[i]*b[i];
    }
    if(!p)                  //是主件 
    {
        b[i]=a[i]*b[i];     //记录主件的价值 
    }
}
for(int i=1;i<=m;i++)
    for(int j=n;j>=a[i];j--) //01背包处理 
    {
        if(vs[i]==0)         //枚举所有主件 
        {
            dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
            if(v1[i] && (j-a[i]-v1[i])>=0) dp[j]=max(dp[j],dp[j-a[i]-v1[i]]+b[i]+w1[i]);
            if(v2[i] && (j-a[i]-v2[i])>=0) dp[j]=max(dp[j],dp[j-a[i]-v2[i]]+b[i]+w2[i]);
            if(v1[i] && v2[i] && (j-a[i]-v1[i]-v2[i])>=0)
            dp[j]=max(dp[j],dp[j-a[i]-v1[i]-v2[i]]+b[i]+w1[i]+w2[i]);
        }
    }
printf("%d",dp[n]);
printf("0");
return 0;

}