NKGOLF - Sân golf

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
PROGRAM NKGOLF;
CONST
  FINP='';
  FOUT='';
  maxn=1005;
  oo=1000000;
VAR
  m,n,kq:longint;
  a:array[0..maxn,0..maxn] of longint;
  d2,d1:array[0..maxn,0..maxn] of longint;
  stack,pre:array[1..maxn*maxn] of longint;
  top:longint;
procedure readInput;
var
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  read(f,m,n);
  for i:=1 to m do
    for j:=1 to n do
      read(f,a[i,j]);
  close(f);
end;
procedure solve1;
var
  i,j:longint;
begin
  for j:=1 to n do
    d1[1,j]:=1;
  kq:=0;
  for i:=2 to m do
    for j:=1 to n do
      begin
        if a[i,j]>=a[i-1,j] then d1[i,j]:=d1[i-1,j]+1
        else d1[i,j]:=1;
        if d1[i,j]>kq then kq:=d1[i,j];
      end;
end;
procedure writeOutput;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
procedure pop(var u,v:longint);
begin
  u:=stack[top]; v:=pre[top]; dec(top);
end;
procedure push(u,v:longint);
begin
  inc(top); stack[top]:=u; pre[top]:=v;
end;
function min(a,b:longint):longint;
begin
  if a<b then min:=a else min:=b;
end;
procedure findMax(i:longint);
var
  j,v,u,luu:longint;
begin
  top:=0;
  for j:=1 to n do
    begin
      v:=j;
      if top>0 then luu:=stack[top];
      while (top>0) and (d2[i,stack[top]]>=d2[i,j]) do
        begin
          pop(u,v);
          if v>1 then
          begin
            if (luu-v+2)*min(d2[i,u],d1[i,v-1])>kq then
              kq:=(luu-v+2)*min(d2[i,u],d1[i,v-1]);
          end
          else
            if (luu-v+1)*d2[i,u]>kq then kq:=(luu-v+1)*d2[i,u];
        end;
      push(j,v);
    end;
  if top>0 then luu:=stack[top];
  while top>0 do
    begin
      pop(u,v);
      if v>1 then
      begin
        if kq<(luu-v+2)*min(d2[i,u],d1[i,v-1])
          then kq:=(luu-v+2)*min(d2[i,u],d1[i,v-1]);
      end
      else if (luu-v+1)*d2[i,u]>kq then kq:=(luu-v+1)*d2[i,u];
    end;
end;
procedure solve2;
var
  i,j:longint;
begin
  for i:=1 to m do a[i,0]:=-oo;
  for j:=1 to n do a[0,j]:=-oo;
  for i:=1 to m do
    for j:=1 to n do
      if a[i,j]<a[i,j-1] then d2[i,j]:=0
      else
        if a[i,j]<a[i-1,j] then d2[i,j]:=1
        else d2[i,j]:=d2[i-1,j]+1;
  for i:=1 to m do
    findMax(i);
end;
BEGIN
  readInput;
  solve1;
  solve2;
  writeOutput;
END.

Download