Pagini recente » Cod sursa (job #1679676) | Cod sursa (job #2257294) | Cod sursa (job #716484) | Cod sursa (job #661380) | Cod sursa (job #1346617)
#include<stdio.h>
int l[202],r[202],st[202],nr,n,m,a[202][202],p[202],sol,i,j,sus[202],jos[202],aux[202][202];
char c;
int max(int a, int b)
{
if(a>b)
return a;
return b;
}
void solve(int *d)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
if(a[i][j]==0)
p[j]++;
else p[j]=0;
nr=0;
st[0]=0;
for(j=1;j<=m;j++)
{
while(nr>0&&p[st[nr]]>=p[j])
nr--;
l[j]=st[nr];
nr++;
st[nr]=j;
}
nr=0;
st[0]=m+1;
p[m+1]=0;
for(j=m;j>=1;j--)
{
while(nr>0&&p[st[nr]]>=p[j])
nr--;
r[j]=st[nr];
nr++;
st[nr]=j;
}
d[i]=d[i-1];
for(j=1;j<=m;j++){
d[i]=max(d[i],(r[j]-l[j]-1)*p[j]);
}
//8printf("%d ",d[i]);
}
// printf("\n");
}
int solve2()
{
solve(sus);
for(j=1;j<=m;j++)
p[j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
aux[i][j]=a[n-i+1][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][j]=aux[i][j];
solve(jos);
for(i=1,j=n;i<j;i++,j--)
{
int ax=jos[i];
jos[i]=jos[j];
jos[j]=ax;
}
for(i=1;i<m;i++)
sol=max(sol,sus[i]+jos[i+1]);
}
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
scanf("%d%d ",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%c ",&c);
a[i][j]=c-'0';
}
solve2();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
aux[i][j]=a[n-i+1][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][j]=aux[i][j];
for(i=1;i<=m;i++)
sus[i]=jos[i]=p[i]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
aux[i][j]=a[j][i];
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
a[i][j]=aux[i][j];
// swap(n,m);
int ax=n;
n=m;
m=ax;
solve2();
printf("%d",sol);
return 0;
}