Pagini recente » Cod sursa (job #3197966) | Cod sursa (job #1214339) | Cod sursa (job #2583790) | Cod sursa (job #254871) | Cod sursa (job #827158)
Cod sursa(job #827158)
#include<stdio.h>
#include<string.h>
int n,m,max,a[205][205],d1[205],d2[205],c[205][205],st[205];
int maxim(int a,int b) {return a>b?a:b;}
void rotate ()
{
int i,j,aa;
int aux[205][205];
for ( i=1; i<=n; i++ )
for ( j=1; j<=m; j++ )
{
aux[j][n-i+1]=a[i][j];
a[i][j]=0;
}
aa=n;n=m;m=aa;
for(i=1;i<=n;i++)
for ( j=1; j<=m; j++ )
a[i][j]=aux[i][j];
}
void update(int i,int d[205],int x)
{
int j,u,p;
u=0;memset(st,0,sizeof(st));
for(j=1;j<=m;j++)
{
p=1;
while(u>=1 && st[u]>c[i][j]) {if(st[p]*(u-p+1)>d[i]) d[i]=st[p]*(u-p+1); u--;}
st[++u]=c[i][j];
for(p=1;p<=u;p++)
if(st[p]*(u-p+1)>d[i]) d[i]=st[p]*(u-p+1);
}
u=0;memset(st,0,sizeof(st));
for(j=m;j>=1;j--)
{
p=1;
while(u>=1 && st[u]>c[i][j]) {if(st[p]*(u-p+1)>d[i]) d[i]=st[p]*(u-p+1); u--;}
st[++u]=c[i][j];
for(p=1;p<=u;p++)
if(st[p]*(u-p+1)>d[i]) d[i]=st[p]*(u-p+1);
}
d[i]=maxim(d[i],d[i+x]);
}
void solve()
{
int i,j;
memset(d1,0,sizeof(d1));
memset(d2,0,sizeof(d2));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
c[i][j]=(a[i][j]==0)?(c[i-1][j]+1):0;
for(i=1;i<=n;i++)
update(i,d1,-1);
for(i=n;i>=1;i--)
for(j=1;j<=m;j++)
c[i][j]=(a[i][j]==0)?(c[i+1][j]+1):0;
for(i=n;i>=1;i--)
update(i,d2,1);
for(i=0;i<=n;i++)
if(d1[i]!=0 && d2[i+1]!=0 && d1[i]+d2[i+1]>max)
max=d1[i]+d2[i+1];
}
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
int i,j;char x;
scanf("%d %d\n",&n,&m);
for(i=1;i<=n;i++,scanf("%c",&x))
for(j=1;j<=m;j++)
{scanf("%c",&x);a[i][j]=x-'0';}
solve();
rotate();
solve();
printf("%d\n",max);
return 0;
}