6.1.2.pas

usacoCHAPTER6程序,非常恶心的动态规划转移方程,位运算等等

{$inline on}
{
ID:LXYXYNT3
PROG:rectbarn
LANG:PASCAL
}
const
  inf='rectbarn.in';
  ouf='rectbarn.out';
  maxn=3000;

var
  map:array[0..maxn+1,0..maxn+1] of boolean;
  h,l,r:array[0..maxn+1] of longint;
  ans,lmax,rmax,n,m,i,j,p,q:longint;


function max(a,b:longint):longint;inline;
begin
  if a<b then exit(b)
         else exit(a);
end;

begin
  assign(input,inf);reset(input);
  assign(output,ouf);rewrite(output);
  readln(n,m,j);
  ans:=0;
  fillchar(map,sizeof(map),true);
  for i:=1 to j do
  begin
    readln(p,q);
    map[p,q]:=false;
  end;
  ans:=0;
  for i:=1 to m do
  begin
    l[i]:=1;
    r[i]:=m;
    h[i]:=0;
  end;
  for i:=1 to n do
  begin
    lmax:=1;
    for j:=1 to m do
     if map[i,j] then
     begin
       inc(h[j]);
       if lmax>l[j] then l[j]:=lmax;
     end else
     begin
       h[j]:=0;
       l[j]:=1;
       r[j]:=m;
       lmax:=j+1;
     end;
    rmax:=m;
    for j:=m downto 1 do
     if map[i,j] then
     begin
       if rmax<r[j] then r[j]:=rmax;
       ans:=max(ans,(r[j]-l[j]+1)*h[j]);
     end else rmax:=j-1;
  end;
  writeln(ans);
  close(input);
  close(output);
end.