状态: Accepted

测评机： Xeond[6]

得分： 100分

提交日期： 2011-5-10 17:40:00

有效耗时： 1062毫秒

测试结果1: 通过本测试点|有效耗时203ms

测试结果2: 通过本测试点|有效耗时62ms

测试结果3: 通过本测试点|有效耗时63ms

测试结果4: 通过本测试点|有效耗时62ms

测试结果5: 通过本测试点|有效耗时63ms

测试结果6: 通过本测试点|有效耗时62ms

测试结果7: 通过本测试点|有效耗时78ms

测试结果8: 通过本测试点|有效耗时79ms

测试结果9: 通过本测试点|有效耗时187ms

测试结果10: 通过本测试点|有效耗时203ms

var m,n,i,j,k,t:longint;

q,w:array[0..60] of longint;

v,p,v1,p1:array[0..60,0..10] of longint;

f:array[0..60,0..32000] of longint;

function max(x,y:longint):longint;

begin if (x>y) then exit(x) else exit(y) end;

begin

readln(n,m); t:=0;

fillchar(f,sizeof(f),0);

fillchar(w,sizeof(w),0);

for i:=1 to m do

begin read(v[i,0],p[i,0],q[i]); p[i,0]:=p[i,0]*v[i,0]; end;

for i:=1 to m do

begin

if (q[i]<>0) then

begin

if (w[q[i]]=1) then

begin

w[q[i]]:=3;

p[q[i],2]:=p[i,0]+p[q[i],0];

v[q[i],2]:=v[i,0]+v[q[i],0];

p[q[i],3]:=p[q[i],1]+p[i,0];

v[q[i],3]:=v[q[i],1]+v[i,0];

end

else

begin

w[q[i]]:=1;

p[q[i],1]:=p[i,0]+p[q[i],0];

v[q[i],1]:=v[q[i],0]+v[i,0];

end;

end;

end;

for i:=1 to m do

if (q[i]=0) then

begin

inc(t);

for j:=0 to w[i] do

begin

p1[t,j]:=p[i,j];

v1[t,j]:=v[i,j];

w[t]:=w[i];

end;

end;

for i:=1 to t do

for j:=1 to n do

begin f[i,j]:=f[i-1,j];

for k:=0 to w[i] do

if (j>=v1[i,k]) then

f[i,j]:=max(f[i,j],f[i-1,j-v1[i,k]]+p1[i,k]);

end;

write(f[t,n]);

end.