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

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
var
  res,top,i,j,m,n:longint;
  a:array[1..1011,1..1011] of longint;
  down,left,right,stack:array[0..1011] of longint;
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 do
    begin
      for j:=1 to n do
        if a[i,j]=1 then down[j]:=down[j]+1
        else down[j]:=0;

      top:=0; stack[0]:=0;
      for j:=1 to n do
        begin
          while (top>0) and (down[stack[top]]>=down[j]) do dec(top);
          left[j]:=stack[top]+1;
          inc(top); stack[top]:=j;
        end;
      top:=0; stack[0]:=n+1;
      for j:=n downto 1 do
        begin
          while (top>0) and (down[stack[top]]>=down[j]) do dec(top);
          right[j]:=stack[top]-1;
          inc(top); stack[top]:=j;
        end;

      for j:=1 to n do
        res:=max(res,down[j]*(right[j]-left[j]+1));
    end;

  writeln(res);
end.

Download