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

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program QBRECT;
const
  input  = '';
  output = '';
  maxn = 1000;
var
  s: array[1..maxn,1..maxn] of integer;
  stack,a,left,right: array[0..maxn] of integer;
  top,n,m,res: integer;

procedure init;
var
  f: text;
  i,j: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, m, n);
  for i := 1 to m do
    for j := 1 to n do read(f, s[i,j]);

  close(f);
end;

procedure push(v: integer);
begin
  inc(top);
  stack[top] := v;
end;

procedure calc;
var
  i: integer;
begin
  top := 0;
  for i := 1 to n do
    begin
      while (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
      if top = 0 then left[i] := 1 else left[i] := stack[top] + 1;
      push(i);
    end;

  top := 0;
  for i := n downto 1 do
    begin
      while (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
      if top = 0 then right[i] := n else right[i] := stack[top] - 1;
      push(i);
    end;

  for i := 1 to n do
    if res < (right[i] - left[i] + 1) * a[i] then res := (right[i] - left[i] + 1) * a[i];
end;

procedure solve;
var
  i,j: integer;
begin
  res := 0;
  fillchar(a, sizeof(a), 0);

  for i := 1 to m do
    begin
      for j := 1 to n do
        if s[i,j] = 1 then inc(a[j]) else a[j] := 0;
      calc;
    end;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Download