rectbarn.pas

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

{
ID:maigoak1
PROG:rectbarn
}

program rectbarn;
const
  maxsize=3000;
  maxp=30000;
var
  fin,fout:text;
  x,y:array[1..maxp+1]of word;
  h,l,r:array[1..maxsize]of word;
  m,n,p,i,j,left,right,ans:longint;
procedure qsort(s,t:word);
  var
    p,i,j,tx,ty:word;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tx:=x[p];x[p]:=x[s];ty:=y[p];y[p]:=y[s];
    i:=s;j:=t;
    repeat
      while (i<j) and ((x[j]>tx) or (x[j]=tx) and (y[j]>ty)) do dec(j);
      if i=j then break;x[i]:=x[j];y[i]:=y[j];inc(i);
      while (i<j) and ((x[i]<tx) or (x[i]=tx) and (y[i]<ty)) do inc(i);
      if i=j then break;x[j]:=x[i];y[j]:=y[i];dec(j);
    until i=j;
    x[i]:=tx;y[i]:=ty;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
procedure update(left,right:word);
  var
    i,t:longint;
  begin
    for i:=left to right do begin
      inc(h[i]);
      if h[i]=1 then begin
        l[i]:=left;r[i]:=right;
      end
      else begin
        if left>l[i] then l[i]:=left;if right<r[i] then r[i]:=right;
      end;
      t:=h[i]*(r[i]-l[i]+1);
      if t>ans then ans:=t;
    end;
  end;
begin
  assign(fin,'rectbarn.in');
  reset(fin);
  read(fin,m,n,p);
  for i:=1 to p do
    read(fin,x[i],y[i]);
  close(fin);

  qsort(1,p);
  x[p+1]:=0;

  fillchar(h,sizeof(h),0);
  ans:=0;p:=1;
  for i:=1 to m do begin
    left:=1;
    for j:=1 to n do
      if (x[p]=i) and (y[p]=j) then begin
        right:=j-1;
        update(left,right);
        h[j]:=0;left:=j+1;
        while (x[p]=i) and (y[p]=j) do inc(p);
      end;
    if left<=n then update(left,n);
  end;

  assign(fout,'rectbarn.out');
  rewrite(fout);
  writeln(fout,ans);
  close(fout);
end.