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.