turnin.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 76 行

{
PROG:turnin
LANG:PASCAL
}

program turnin;
const
  range=1000;
var
  fin,fout:text;
  loc,ready:array[0..range]of integer;
  t:array[0..range,0..range,(left,right)]of integer;
    {Denote by t[x,y,p] the least time needed to reach the situation in
     which Bessie has turned in 0..x and y..c and is at x (if p=left) or
     y (if p=right)}
  c,h,b,i,x,y,z:integer;
function min(a,b:integer):integer;
  begin
    if a<b then min:=a else min:=b;
  end;
function max(a,b:integer):integer;
  begin
    if a>b then max:=a else max:=b;
  end;
begin
  assign(fin,'turnin.in');
  reset(fin);
  readln(fin,c,h,b);
  for i:=0 to h do
    ready[i]:=-1;
  ready[b]:=0;
  for i:=1 to c do begin
    readln(fin,x,y);
    if y>ready[x] then ready[x]:=y;
  end;
  close(fin);
  c:=-1;
  for i:=0 to h do
    if ready[i]>-1 then begin
      inc(c);
      loc[c]:=i;
      ready[c]:=ready[i];
      if i=b then b:=c;
    end;

  for x:=0 to c do
    for y:=0 to c do begin
      t[x,y,left]:=maxint;
      t[x,y,right]:=maxint;
    end;
  t[0,c,left]:=max(loc[0],ready[0]);t[0,c,right]:=max(loc[c],ready[c]);
  for i:=c-1 downto 0 do
    for x:=0 to c-i do begin
      y:=x+i;
      if x=0 then
        z:=t[x,y+1,right]+loc[y+1]-loc[x]
      else if y=c then
        z:=t[x-1,y,left]+loc[x]-loc[x-1]
      else
        z:=min(t[x-1,y,left]+loc[x]-loc[x-1],t[x,y+1,right]+loc[y+1]-loc[x]);
      t[x,y,left]:=max(z,ready[x]);
      if x=0 then
        z:=t[x,y+1,right]+loc[y+1]-loc[y]
      else if y=c then
        z:=t[x-1,y,left]+loc[y]-loc[x-1]
      else
        z:=min(t[x,y+1,right]+loc[y+1]-loc[y],t[x-1,y,left]+loc[y]-loc[x-1]);
      t[x,y,right]:=max(z,ready[y]);
    end;

  assign(fout,'turnin.out');
  rewrite(fout);
  writeln(fout,min(t[b,b,left],t[b,b,right]));
  close(fout);
end.