CREC01 - Đếm hình chữ nhật trên bảng 0-1

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=1010;
var n,m:longint;
    re:int64;
    f,st:array[0..maxn] of longint;
    num:array[0..maxn] of int64;

procedure pr;
var i,j,now,t:longint; c:char;
begin
     assign(input,fi);
     reset(input);
     readln(m,n);
     re:=0;
     fillchar(f,sizeof(f),0);
     for i:=1 to m do
     begin
          for j:=1 to n do
          begin
               read(c);
               if c='0' then f[j]:=0 else inc(f[j]);
          end;
          readln;
          num[0]:=0; f[0]:=-1; st[0]:=0; now:=0;
          for j:=1 to n do
          begin
               while f[st[now]]>=f[j] do dec(now);
               t:=st[now];
               inc(now);
               st[now]:=j;
               num[j]:=f[j]*(j-t)+num[t];
               re:=re+num[j];
          end;
     end;
     close(input);
end;

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

begin
     pr;
     wf;
end.

Download