记录编号	346327	评测结果	AAAAAAAAAA
题目名称	“金明的预算方案”加强版	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	2.008 s
提交时间	2016-11-12 08:22:43	内存使用	19.17 MiB

#include<cstdio>
#include<vector>
#define is(a) ((a)>='0'&&(a)<='9')
using namespace std;
char ch;bool read_flag;
inline void read(int& x)
{
	x=0,read_flag=false;
	while(ch=getchar(),!is(ch))if(ch=='-')read_flag=1;
	do x=x*10+(ch^'0'),ch=getchar(); while(is(ch));
	if(read_flag) x=-x;
}
const int Size=10010,Sizem=5010,D=10;
vector<int> son[Sizem];
int n,m,f[Sizem][Size],val[Sizem],cost[Sizem];
inline int _max(int x,int y){return x>y?x:y;}
inline void dp(int i,int j)
{
	if(j<1) return ;
	int k,s,l;
	for(k=0;k<son[i].size();k++){
		s=son[i][k];
		for(l=0;l<=j;l++) f[s][l]=f[i][l];
		dp(s,j-cost[i]);
		for(l=j;l>=cost[s];l--)
			f[i][l]=_max(f[i][l],f[s][l-cost[s]]+val[s]);
	}
}
int _521()
{
#define enjoy_coding
#ifdef enjoy_coding
	freopen("budgetc.in","r",stdin);
	freopen("budgetc.out","w",stdout);
#else
	freopen("1.in","r",stdin);
#endif
	int i,j;
	read(m),read(n);
	for(i=1;i<=n;i++){
		read(cost[i]),read(val[i]),read(j);
		cost[i]/=D,val[i]*=cost[i];
		son[j].push_back(i);
	}
	dp(0,m/D);
	printf("%d\n",f[0][m/D]*D);
	return 0;
}
int _520=_521();
int main(){;}