inflate.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:inflate
}

program inflate;
const
  max=10000;
var
  fin,fout:text;
  ok:array[0..max]of boolean;
  score:array[0..max]of longint;
  m,n,i,j,p,t,s:longint;
procedure out;
  var
    i:integer;
  begin
    close(fin);
    assign(fout,'inflate.out');
    rewrite(fout);
    for i:=m downto 0 do
      if ok[i] then writeln(fout,i);
    close(fout);
  end;
begin
  fillchar(ok,sizeof(ok),0);
  ok[0]:=true;
  score[0]:=0;
  assign(fin,'inflate.in');
  reset(fin);
  readln(fin,m,n);

  for i:=1 to n do begin
    readln(fin,p,t);
    for j:=0 to m-t do
      if ok[j] then
        if ok[j+t] then begin
          if score[j]+p>score[j+t] then score[j+t]:=score[j]+p;
        end
        else begin
          ok[j+t]:=true;
          score[j+t]:=score[j]+p;
        end;
  end;

  close(fin);
  assign(fout,'inflate.out');
  rewrite(fout);
  s:=0;
  for i:=m downto 0 do
    if ok[i] then
      if score[i]>s then
        s:=score[i];
  writeln(fout,s);
  close(fout);
end.