Pagini recente » Cod sursa (job #2723586) | Cod sursa (job #2659188) | Cod sursa (job #1378230) | Cod sursa (job #1959350) | Cod sursa (job #2027004)
#include <fstream>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n,m,i,j,k,ult,fr[1<<8],D[1<<8],up[1<<8],down[1<<8],Left[1<<8],Right[1<<8];
char M[1<<8][1<<8];
int main()
{
f>>n>>m;
for(i=1;i<=n;++i) f>>(M[i]+1);
for(i=1;i<=n;++i)
for(j=1,k=ult=0;j<=m;++j)
{
if(M[i][j]=='0')
{
++fr[j];
int nr=0;
while(k&&fr[D[k]]>=fr[j])
{
nr=max(nr,fr[j]*(j-D[k]+1));
--k;
}
if(!k) nr=max(nr,fr[j]*(j-ult));
else nr=max(nr,fr[D[1]]*(j-D[1]+1));
up[i]=max(up[i],max(up[i-1],nr));
Left[j]=max(Left[j],max(Left[j-1],nr));
D[++k]=j;
continue;
}
fr[j]=k=0;
ult=j;
}
for(i=1;i<=m;++i) fr[i]=0;
for(i=n;i>0;--i)
for(j=m,k=0,ult=m+1;j>0;--j)
{
if(M[i][j]=='0')
{
++fr[j];
int nr=0;
while(k&&fr[D[k]]>=fr[j])
{
nr=max(nr,fr[j]*(D[k]-j+1));
--k;
}
if(!k) nr=max(nr,fr[j]*(ult-j));
else nr=max(nr,fr[D[1]]*(D[1]-j+1));
down[i]=max(down[i],max(down[i+1],nr));
Right[j]=max(Right[j],max(Right[j+1],nr));
D[++k]=j;
continue;
}
fr[j]=k=0;
ult=j;
}
int sol=0;
for(i=1;i<n;++i) sol=max(sol,Left[i]+Right[i+1]);
for(i=1;i<m;++i) sol=max(sol,up[i]+down[i+1]);
g<<sol;
return 0;
}