#include<iostream>
using namespace std;
const int maxv=32007,maxn=10086;
int dp[maxv],c[maxn],w[maxn],fj[maxn],yid[maxn];
int v,m,k;
struct node
{
	int id;
	int id1,id2;
} a[65];
int main()
{
	int p=0,id,id1,id2;
	cin>>v>>m;
	for(int i=1;i<=m;i++) cin>>c[i]>>w[i]>>fj[i],w[i]*=c[i];
	for(int i=1;i<=m;i++) if(fj[i]==0) a[++k].id=i,yid[i]=k;
	for(int i=1;i<=m;i++)
	{
		if(fj[i]!=0)
		{
			p=yid[fj[i]];
			if(a[p].id1==0) a[p].id1=i;
			else a[p].id2=i;
		}
	}
	for(int i=1;i<=k;i++)
	{
		id=a[i].id; id1=a[i].id1; id2=a[i].id2;
		for(int j=v;j>=c[id];j--)
		{
			dp[j]=max(dp[j],dp[j-c[id]+w[id]]);
			if(j>=c[id]+c[id1]) dp[j]=max(dp[j],dp[j-c[id]-c[id1]]+w[id]+w[id1]);
			if(j>=c[id]+c[id2]) dp[j]=max(dp[j],dp[j-c[id]-c[id2]]+w[id]+w[id2]);
			if(j>=c[id]+c[id1]+c[id2]) dp[j]=max(dp[j],dp[j-c[id]-c[id1]-c[id2]]+w[id]+w[id1]+w[id2]);
		}
	}
	cout<<dp[v];
	return 0;
}

subtask 1过了

其他九个WA一个RE

记录