70分01背包求调

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lf long double
#define INF 0x7fffffff
#define debug(alpha) cout<<alpha<<endl
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define Max3(a,b,c) (max(max((a),(b)),(c)))
#define Min3(a,b,c) (min(min((a),(b)),(c)))
using namespace std;
void iread(int &x1145141919810)
{
    x1145141919810=0;
    char c;int wx1145141919810=1;c=getchar();
    while((c>'9'||c<'0')&&c!='-')c=getchar();
    if(c=='-'){wx1145141919810=-1;c=getchar();}
    while(c>='0'&&c<='9'){x1145141919810=x1145141919810*10+c-'0';c=getchar();}
    x1145141919810*=wx1145141919810;
}
int n,T,thing[65][5],f[32005],app[65][5],tot,tot1,x,y,q;
signed main()
{
    cin>>T>>n;
    for(int i=1;i<=n;i=-~i)
    {
        cin>>x>>y>>q;
        y=y*x;
        if(!q)
        {
            thing[++tot][1]=x;
            thing[tot][2]=y;
        }
        else
        {
            app[++tot1][1]=x;
            app[tot1][2]=y;
            thing[q][(++thing[q][0])+2]=tot1;
        }
    }
    for(int i=1;i<=tot;i=-~i)
    {
        for(int j=T;j>=thing[i][1]&&thing[i][1]!=0;j=~(-j))
        {
            f[j]=max(f[j],f[j-thing[i][1]]+thing[i][2]);
            if(thing[i][1]+app[thing[i][3]][1]<=j&&thing[i][0])
                f[j]=max(f[j],f[j-thing[i][1]-app[thing[i][3]][1]]+thing[i][2]+app[thing[i][3]][2]);
            if(thing[i][1]+app[thing[i][4]][1]<=j&&thing[i][0])
                f[j]=max(f[j],f[j-thing[i][1]-app[thing[i][4]][1]]+thing[i][2]+app[thing[i][4]][2]);
            if(thing[i][1]+app[thing[i][3]][1]+app[thing[i][4]][1]<=j&&thing[i][0]-1)
                f[j]=max(f[j],f[j-thing[i][1]-app[thing[i][3]][1]-app[thing[i][4]][1]]+thing[i][2]+app[thing[i][3]][2]+app[thing[i][4]][2]);
        }
    }
    cout<<f[T];
    return 0;
}