a,b,c:array[0..100]of longint;
f:array[0..100,0..3100]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
readln(d,n);
for i:=1 to n do readln(a[i],b[i],c[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then begin
t:=a[i];a[i]:=a[j];a[j]:=t;
t:=b[i];b[i]:=b[j];b[j]:=t;
t:=c[i];c[i]:=c[j];c[j]:=t;
end;
for i:=0 to n do
for j:=0 to 3100 do f[i,j]:=-999999;
f[0,10]:=0;
for i:=1 to n do begin
r:=a[i]-a[i-1];
for j:=0 to 3000 do begin
f[i,j]:=max(f[i,j],f[i-1,j+r]+c[i]);
f[i,j+b[i]]:=max(f[i,j+b[i]],f[i-1,j+r]);
if f[i,j]>=d then begin writeln(a[i]);exit;end;
end;
end;
t:=0;
for i:=1 to 3000 do
if f[n,i]>=0 then t:=max(t,f[n,i]);
writeln(t+a[n]);
end.
和讨论里有个人wa的一模一样
50分
: Unaccepted
测评机： Xeost[5]
得分： 50分
提交日期： 2011-10-7 11:29:00
有效耗时： 327毫秒
测试结果1: 通过本测试点|有效耗时62ms
测试结果2:
测试结果3: 通过本测试点|有效耗时62ms
测试结果4:
测试结果5: 通过本测试点|有效耗时62ms
测试结果6:
测试结果7:
测试结果8: 通过本测试点|有效耗时63ms
测试结果9:
测试结果10: 通过本测试点|有效耗时78ms