Cod sursa(job #333765)

Utilizator ionutz32Ilie Ionut ionutz32 Data 23 iulie 2009 19:51:56
Problema BMatrix Scor 96
Compilator fpc Status done
Runda Arhiva de probleme Marime 8.34 kb
var a:array[1..200,1..200] of 0..1;
v,u,st,c:array[1..200] of 0..200;
v1,v2,v3,v4:array[0..200] of longint;
m,n,i,j,ns,amax:longint;
ca:char;
f,g:text;
procedure sus;
          var smax,t,k:longint;
          begin
          t:=0;
          smax:=0;
          for i:=1 to n do
              begin
              if a[1,i]=0 then
                 begin
                 u[i]:=1;
                 inc(t);
                 end
              else
                  begin
                  u[i]:=0;
                  t:=0;
                  end;
              if t>smax then
                 smax:=t;
              end;
          v1[1]:=smax;
          for i:=2 to m do
              begin
              ns:=0;
              for j:=1 to n do
                  if a[i,j]=0 then
                     begin
                     v[j]:=u[j]+1;
                     if v[j]>smax then
                        smax:=v[j];
                     k:=j;
                     while (ns>0) and (st[ns]>=v[j]) do
                           begin
                           if st[ns]*(j-c[ns])>smax then
                              smax:=st[ns]*(j-c[ns]);
                           k:=c[ns];
                           ns:=ns-1;
                           end;
                     ns:=ns+1;
                     st[ns]:=v[j];
                     c[ns]:=k;
                     end
                  else
                      begin
                      v[j]:=0;
                      while ns>0 do
                            begin
                            if st[ns]*(j-c[ns])>smax then
                               smax:=st[ns]*(j-c[ns]);
                            ns:=ns-1;
                            end;
                      end;
              for j:=1 to n do
                  u[j]:=v[j];
              while ns>0 do
                    begin
                    if st[ns]*(n-c[ns]+1)>smax then
                       smax:=st[ns]*(n-c[ns]+1);
                    ns:=ns-1;
                    end;
              v1[i]:=smax;
              end;
          end;
procedure jos;
          var smax,t,k:longint;
          begin
          smax:=0;
          t:=0;
          for i:=1 to n do
              begin
              if a[m,i]=0 then
                 begin
                 u[i]:=1;
                 t:=t+1;
                 end
              else
                  begin
                  u[i]:=0;
                  t:=0;
                  end;
              if t>smax then
                 smax:=t;
              end;
          v2[m]:=smax;
          for i:=m-1 downto 1 do
              begin
              ns:=0;
              for j:=1 to n do
                  if a[i,j]=0 then
                     begin
                     v[j]:=u[j]+1;
                     if v[j]>smax then
                        smax:=v[j];
                     k:=j;
                     while (ns>0) and (st[ns]>=v[j]) do
                           begin
                           if st[ns]*(j-c[ns])>smax then
                              smax:=st[ns]*(j-c[ns]);
                           k:=c[ns];
                           ns:=ns-1;
                           end;
                     ns:=ns+1;
                     st[ns]:=v[j];
                     c[ns]:=k;
                     end
                  else
                      begin
                      v[j]:=0;
                      while ns>0 do
                            begin
                            if st[ns]*(j-c[ns])>smax then
                               smax:=st[ns]*(j-c[ns]);
                            ns:=ns-1;
                            end;
                      end;
              for j:=1 to n do
                  u[j]:=v[j];
              while ns>0 do
                    begin
                    if st[ns]*(n-c[ns]+1)>smax then
                       smax:=st[ns]*(n-c[ns]+1);
                    ns:=ns-1;
                    end;
              v2[i]:=smax;
              end;
          end;
procedure stg;
          var smax,t,k:longint;
          begin
          smax:=0;
          t:=0;
          for i:=1 to m do
              begin
              if a[i,1]=0 then
                 begin
                 u[i]:=1;
                 t:=t+1;
                 end
              else
                  begin
                  u[i]:=0;
                  t:=0;
                  end;
              if t>smax then
                 smax:=t;
              end;
          v3[1]:=smax;
          for i:=2 to n do
              begin
              ns:=0;
              for j:=1 to m do
                  if a[j,i]=0 then
                     begin
                     v[j]:=u[j]+1;
                     if v[j]>smax then
                        smax:=v[j];
                     k:=j;
                     while (ns>0) and (st[ns]>=v[j]) do
                           begin
                           if st[ns]*(j-c[ns])>smax then
                              smax:=st[ns]*(j-c[ns]);
                           k:=c[ns];
                           ns:=ns-1;
                           end;
                     ns:=ns+1;
                     st[ns]:=v[j];
                     c[ns]:=k;
                     end
                  else
                      begin
                      v[j]:=0;
                      while ns>0 do
                            begin
                            if st[ns]*(j-c[ns])>smax then
                               smax:=st[ns]*(j-c[ns]);
                            ns:=ns-1;
                            end;
                      end;
              while ns>0 do
                    begin
                    if st[ns]*(m-c[ns]+1)>smax then
                       smax:=st[ns]*(m-c[ns]+1);
                    ns:=ns-1;
                    end;
              v3[i]:=smax;
              for j:=1 to m do
                  u[j]:=v[j];
              end;
          end;
procedure drt;
          var smax,t,k:longint;
          begin
          smax:=0;
          t:=0;
          for i:=1 to m do
              begin
              if a[i,n]=0 then
                 begin
                 u[i]:=1;
                 t:=t+1;
                 end
              else
                  begin
                  u[i]:=0;
                  t:=0;
                  end;
              if t>smax then
                 smax:=t;
              end;
          v4[n]:=smax;
          for i:=n-1 downto 1 do
              begin
              ns:=0;
              for j:=1 to m do
                  if a[j,i]=0 then
                     begin
                     v[j]:=u[j]+1;
                     if v[j]>smax then
                        smax:=v[j];
                     k:=j;
                     while (ns>0) and (st[ns]>=v[j]) do
                           begin
                           if st[ns]*(j-c[ns])>smax then
                              smax:=st[ns]*(j-c[ns]);
                           k:=c[ns];
                           ns:=ns-1;
                           end;
                     ns:=ns+1;
                     st[ns]:=v[j];
                     c[ns]:=k;
                     end
                  else
                      begin
                      v[j]:=0;
                      while ns>0 do
                            begin
                            if st[ns]*(j-c[ns])>smax then
                               smax:=st[ns]*(j-c[ns]);
                            ns:=ns-1;
                            end;
                      end;
              while ns>0 do
                    begin
                    if st[ns]*(m-c[ns]+1)>smax then
                       smax:=st[ns]*(m-c[ns]+1);
                    ns:=ns-1;
                    end;
              for j:=1 to n do
                  u[j]:=v[j];
              v4[i]:=smax;
              end;
          end;
begin
assign(f,'bmatrix.in');
assign(g,'bmatrix.out');
reset(f);rewrite(g);
readln(f,m,n);
for i:=1 to m do
    begin
    for j:=1 to n do
        begin
        read(f,ca);
        a[i,j]:=ord(ca)-48;
        end;
    readln(f);
    end;
sus;
jos;
stg;
drt;
amax:=0;
for i:=0 to m-1 do
    if v1[i]+v2[i+1]>amax then
       amax:=v1[i]+v2[i+1];
for i:=0 to n-1 do
    if v3[i]+v4[i+1]>amax then
       amax:=v3[i]+v4[i+1];
write(g,amax);
close(f);close(g);
end.