Cod sursa(job #193731)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 6 iunie 2008 18:20:57
Problema BMatrix Scor 48
Compilator fpc Status done
Runda Arhiva de probleme Marime 6.33 kb
var v,u,p,w:array[-200..200,-200..200]of longint;
    v1,v2,v3,v4,d,o:array[-2..200]of longint;
    n,i,j,k,m,l,r:longint;
    s:string;
    f:text;
begin
   assign(f,'bmatrix.in');
   reset(f);
   readln(f,n,m);
   for i:=1 to n do
   begin
   readln(f,s);
   for j:=1 to m do
   begin
   if s[j]='0' then v[i,j]:=0
               else v[i,j]:=1;
   p[i,j]:=0;
   end;
   end;
   close(f);
   for i:=1 to n do
   begin
   r:=0;
   for j:=1 to m do
   begin
   if(v[i,j]=0)then p[i,j]:=p[i-1,j]+1
               else p[i,j]:=0;
   d[j]:=0;
   o[j]:=0;
   end;
   l:=0;
   for j:=1 to m do
   if(p[i,j]>o[l])then begin l:=l+1;
                             d[l]:=j;
                             o[l]:=p[i,j];
                             if o[l]>r then r:=o[l];
                       end
                  else begin while(p[i,j]<=o[l])and(l>0)do
                             l:=l-1;
                             l:=l+1;
                             o[l]:=p[i,j];
                             if o[l]*(j-d[l]+1)>r then r:=o[l]*(j-d[l]+1);
                       end;
   for j:=1 to m do
   begin
   o[j]:=0;
   d[j]:=0;
   end;
   l:=0;
   for j:=m downto 1 do
   if(p[i,j]>o[l])then begin l:=l+1;
                             d[l]:=m-j+1;
                             o[l]:=p[i,j];
                             if o[l]>r then r:=o[l];
                       end
                  else begin while(p[i,j]<=o[l])and(l>0)do
                             l:=l-1;
                             l:=l+1;
                             o[l]:=p[i,j];
                             if o[l]*(m-j+1-d[l]+1)>r then r:=o[l]*(m-j+1-d[l]+1);
                       end;
   v1[i]:=r;
   if v1[i-1]>v1[i] then v1[i]:=v1[i-1];
   end;
   r:=n;
   n:=m;
   m:=r;
   for i:=1 to n do
   for j:=1 to m do
   u[i,j]:=v[m-j+1,i];
   v:=u;
   u:=w;
   for i:=1 to n do
   begin
   r:=0;
   for j:=1 to m do
   begin
   if(v[i,j]=0)then p[i,j]:=p[i-1,j]+1
               else p[i,j]:=0;
   d[j]:=0;
   o[j]:=0;
   end;
   l:=0;
   for j:=1 to m do
   if(p[i,j]>o[l])then begin l:=l+1;
                             d[l]:=j;
                             o[l]:=p[i,j];
                             if o[l]>r then r:=o[l];
                       end
                  else begin while(p[i,j]<=o[l])and(l>0)do
                             l:=l-1;
                             l:=l+1;
                             o[l]:=p[i,j];
                             if o[l]*(j-d[l]+1)>r then r:=o[l]*(j-d[l]+1);
                       end;
   for j:=1 to m do
   begin
   o[j]:=0;
   d[j]:=0;
   end;
   l:=0;
   for j:=m downto 1 do
   if(p[i,j]>o[l])then begin l:=l+1;
                             d[l]:=m-j+1;
                             o[l]:=p[i,j];
                             if o[l]>r then r:=o[l];
                       end
                  else begin while(p[i,j]<=o[l])and(l>0)do
                             l:=l-1;
                             l:=l+1;
                             o[l]:=p[i,j];
                             if o[l]*(m-j+1-d[l]+1)>r then r:=o[l]*(m-j+1-d[l]+1);
                       end;
   v2[i]:=r;
   if v2[i-1]>v2[i] then v2[i]:=v2[i-1];
   end;
   r:=n;
   n:=m;
   m:=r;
   for i:=1 to n do
   for j:=1 to m do
   u[i,j]:=v[m-j+1,i];
   v:=u;
   u:=w;
   for i:=1 to n do
   begin
   r:=0;
   for j:=1 to m do
   begin
   if(v[i,j]=0)then p[i,j]:=p[i-1,j]+1
               else p[i,j]:=0;
   d[j]:=0;
   o[j]:=0;
   end;
   l:=0;
   for j:=1 to m do
   if(p[i,j]>o[l])then begin l:=l+1;
                             d[l]:=j;
                             o[l]:=p[i,j];
                             if o[l]>r then r:=o[l];
                       end
                  else begin while(p[i,j]<=o[l])and(l>0)do
                             l:=l-1;
                             l:=l+1;
                             o[l]:=p[i,j];
                             if o[l]*(m-d[l]+1)>r then r:=o[l]*(j-d[l]+1);
                       end;
   for j:=1 to m do
   begin
   o[j]:=0;
   d[j]:=0;
   end;
   l:=0;
   for j:=m downto 1 do
   if(p[i,j]>o[l])then begin l:=l+1;
                             d[l]:=m-j+1;
                             o[l]:=p[i,j];
                             if o[l]>r then r:=o[l];
                       end
                  else begin while(p[i,j]<=o[l])and(l>0)do
                             l:=l-1;
                             l:=l+1;
                             o[l]:=p[i,j];
                             if o[l]*(m-j+1-d[l]+1)>r then r:=o[l]*(m-j+1-d[l]+1);
                       end;
   v3[n-i+1]:=r;
   if v3[n-i+2]>v3[n-i+1] then v3[n-i+1]:=v3[n-i+2];
   end;
   r:=n;
   n:=m;
   m:=r;
   for i:=1 to n do
   for j:=1 to m do
   u[i,j]:=v[m-j+1,i];
   v:=u;
   u:=w;
   for i:=1 to n do
   begin
   r:=0;
   for j:=1 to m do
   begin
   if(v[i,j]=0)then p[i,j]:=p[i-1,j]+1
               else p[i,j]:=0;
   d[j]:=0;
   o[j]:=0;
   end;
   l:=0;
   for j:=1 to m do
   if(p[i,j]>o[l])then begin l:=l+1;
                             d[l]:=j;
                             o[l]:=p[i,j];
                             if o[l]>r then r:=o[l];
                       end
                  else begin while(p[i,j]<=o[l])and(l>0)do
                             l:=l-1;
                             l:=l+1;
                             o[l]:=p[i,j];
                             if o[l]*(j-d[l]+1)>r then r:=o[l]*(j-d[l]+1);
                       end;
   for j:=1 to m do
   begin
   o[j]:=0;
   d[j]:=0;
   end;
   l:=0;
   for j:=m downto 1 do
   if(p[i,j]>o[l])then begin l:=l+1;
                             d[l]:=m-j+1;
                             o[l]:=p[i,j];
                             if o[l]>r then r:=o[l];
                       end
                  else begin while(p[i,j]<=o[l])and(l>0)do
                             l:=l-1;
                             l:=l+1;
                             o[l]:=p[i,j];
                             if o[l]*(m-j+1-d[l]+1)>r then r:=o[l]*(m-j+1-d[l]+1);
                       end;
   v4[n-i+1]:=r;
   if v4[n-i+2]>v4[n-i+1] then v4[n-i+1]:=v4[n-i+2];
   end;
   r:=0;
   assign(f,'bmatrix.out');
   rewrite(f);
   for i:=1 to m-1 do
   if(v1[i]+v3[i+1]>r)then r:=v1[i]+v3[i+1];
   for i:=1 to n-1 do
   if(v2[i]+v4[i+1]>r)then r:=v2[i]+v4[i+1];
   writeln(f,r);
   close(f);
end.