NKGOLF - Sân golf

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=1010;
var n,re,m,last:longint;
    a,h,hh:array[0..1,0..maxn] of longint;
    st,d:array[0..maxn] of longint;

procedure rf;
var i,j:longint;
begin
     read(m,n);
     st[0]:=-maxlongint;
     for i:=0 to 1 do
     begin
          a[i,n+1]:=maxlongint;
          a[i,0]:=maxlongint;
     end;
     for j:=1 to n do a[0,j]:=maxlongint;
end;

procedure pr;
var i,j,z,t:longint;
begin
     for i:=1 to m do
     begin
          last:=0; z:=i and 1;
          for j:=1 to n do
          begin
               read(a[z,j]);
               if a[z,j]>=a[1-z,j] then
               begin
                    h[z,j]:=h[1-z,j]+1;
                    hh[z,j]:=hh[1-z,j]+1;
               end
               else
               begin
                    h[z,j]:=1;
                    hh[z,j]:=1;
               end;
               if a[1-z,j]>a[1-z,j+1] then hh[z,j]:=1;
               if h[z,j]>re then re:=h[z,j];
               if a[z,j]<a[z,j-1] then
               begin
                    last:=1; st[1]:=hh[z,j]; d[1]:=j;
                    continue;
               end;
               if hh[z,j]>st[last] then
               begin
                    inc(last); st[last]:=hh[z,j]; d[last]:=j;
                    continue;
               end
               else
               begin
                    while hh[z,j]<=st[last] do
                    begin
                         if st[last]<=h[z,j] then t:=1 else t:=0;
                         if re<st[last]*(j-d[last]+t) then
                            re:=st[last]*(j-d[last]+t);
                         dec(last);
                    end;
                    inc(last);
                    if hh[z,j]<>st[last] then st[last]:=hh[z,j];
               end;
          end;
          for j:=1 to last do
              if re<st[j]*(n-d[j]+1) then
                 re:=st[j]*(n-d[j]+1);
     end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     pr;
     close(input); close(output);
end.

Download