QBRECT - Hình chữ nhật 0 1

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=1010;
var m,n,re:longint;
    a:array[0..maxn,0..maxn] of longint;
    st,pos:array[0..2*maxn] of longint;

procedure rf;
var i,j,t:longint;
begin
     assign(input,fi);
     reset(input);
     readln(m,n);
     re:=0;
     fillchar(a,sizeof(a),0);
     for i:=1 to m do
     begin
          for j:=1 to n do
          begin
               read(t);
               if t=0 then a[i,j]:=0
               else
               begin
                    a[i,j]:=a[i-1,j]+1;
                    if a[i,j]>re then re:=a[i,j];
               end;
          end;
          readln;
     end;
     close(input);
end;

procedure pr;
var i,j,now,k,q,s:longint;
begin
     if re=0 then exit;
     st[0]:=0; pos[0]:=0;
     for i:=1 to m do
     begin
          j:=1; now:=0;
          repeat
                if a[i,j]>0 then
                begin
                     if a[i,j]>=st[now] then
                     begin
                          inc(now);
                          st[now]:=a[i,j]; pos[now]:=j;
                     end
                     else
                     begin
                          k:=now;
                          while (st[now]>a[i,j]) and (now>0) do dec(now);
                          inc(now);
                          for q:=k-1 downto now do
                          begin
                               s:=st[q]*(pos[k]-pos[q]+1);
                               if s>re then re:=s;
                          end;
                          st[now]:=a[i,j];
                          inc(now);
                          st[now]:=a[i,j]; pos[now]:=j;
                     end;
                end
                else
                begin
                     if a[i,j-1]>0 then
                     begin
                          for q:=now downto 1 do
                          begin
                               s:=st[q]*(j-pos[q]);
                               if s>re then re:=s;
                          end;
                          now:=0;
                     end;
                end;
                inc(j);
          until j>n+1;
     end;
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download