NKGOLF - Sân golf

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

uses math;
type integer = longint;
var
   tt, res, i, j, m, n : integer;
   a : array[1..1000,1..1000] of longint;
   b : array[1..1000,1..1000] of boolean;
   h, left, right : array[1..1000] of integer;
begin
     read( m, n);
     for i:=1 to m do for j:=1 to n do read(a[i,j]);
     for i:=1 to m-1 do for j:=1 to n-1 do b[i,j] :=  (a[i,j]<=a[i+1,j]) and (a[i,j]<=a[i,j+1]) and (a[i+1,j]<=a[i+1,j+1]) and (a[i][j+1]<=a[i+1][j+1]);
     res := 1;
     for i:=1 to m do begin
         tt := 1;
         for j:=2 to n do if a[i,j]>=a[i,j-1] then begin inc(tt); res := max( res, tt) end else tt:=1;

     end;
     for j:=1 to n do begin
         tt := 1;
         for i:=2 to m do if(a[i,j]>=a[i-1,j]) then begin inc(tt); res := max( res, tt) end else tt:=1;
     end;

     {for i:=1 to m-1 do begin for j:=1 to n-1 do write(b[i,j]:7); writeln end;}

     for i:=1 to m-1 do begin
         for j:=1 to n-1 do if b[i,j] then inc(h[j]) else h[j]:=0;
         for j:=1 to n-1 do begin
             tt := j-1;
             while(tt>0) and (h[tt]>=h[j]) do tt := left[tt];
             left[j] := tt;
         end;
         for j:=n-1 downto 1 do begin
             tt := j+1;
             while(tt<n) and (h[tt]>=h[j]) do tt := right[tt];
             right[j] := tt;
         end;
         for j:=1 to n-1 do if h[j]>0 then begin
              res := max( res, (h[j]+1) * (right[j] - left[j]));
         end;
     end;
     writeln(res);
end.

Download