Cod sursa(job #333765)
Utilizator | 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.