Pagini recente » Cod sursa (job #1036916) | Cod sursa (job #304523) | Cod sursa (job #2098256) | Cod sursa (job #1493730) | Cod sursa (job #64767)
Cod sursa(job #64767)
#include <stdio.h>
#define fin "bmatrix.in"
#define fout "bmatrix.out"
#define Nmax 201
int N,M,ret,bst1[Nmax],bst2[Nmax];
char map[Nmax][Nmax];
void go(int a[Nmax],int b[Nmax]) {
int i,j,k,vf,v[Nmax];
int st[Nmax][2];
for (i=0;i<=N;++i)
v[i]=a[i]=b[i]=0;
for (i=1;i<=N;++i)
for (j=1,vf=0;j<=M;++j) {
if (map[i][j]=='0')
++v[j];
else
v[j]=0;
st[++vf][0]=v[j];
st[vf][1]=j;
for ( k = vf ; k > 0 && v[j] >= st[k][0]; --k )
if ( ( j-st[k][1]+1 ) * st[k][0] > a[j] )
a[j] = ( j-st[k][1]+1 ) * st[k][0];
for ( ; vf>1 && st[vf-1][0] >= st[vf][0] ; --vf )
st[vf-1][0]=st[vf][0];
if ( a[j-1] > a[j] )
a[j]=a[j-1];
}
for (i=1;i<=N;++i)
for (j=M,vf=0;j>0;--j) {
if (map[i][j]=='0')
++v[j];
else
v[j]=0;
st[++vf][0]=v[j];
st[vf][1]=j;
for ( k = vf ; k > 0 && v[j] >= st[k][0]; --k )
if ( ( st[k][1]-j+1 ) * st[k][0] > b[j] )
b[j] = ( st[k][1]-j+1 ) * st[k][0];
for ( ; vf>1 && st[vf-1][0] >= st[vf][0] ; --vf )
st[vf-1][0]=st[vf][0];
if ( b[j] < b[j+1] )
b[j]=b[j+1];
}
}
void inv(char map[Nmax][Nmax],int &N,int &M) {
int i,j;
char aux[Nmax][Nmax];
for (i=1;i<=N;++i)
for (j=1;j<=M;++j)
aux[j][N-i+1]=map[i][j];
N+=M; M=N-M; N-=M;
for (i=1;i<=N;++i)
for (j=1;j<=M;++j)
map[i][j]=aux[i][j];
}
int main() {
int i,j;
freopen(fin,"r",stdin); freopen(fout,"w",stdout);
scanf("%d%d",&N,&M);
for (i=1;i<=N;++i) {
fgetc(stdin);
for (j=1;j<=M;++j)
map[i][j]=fgetc(stdin);
}
go(bst1,bst2);
for (i=2;i<=M;++i)
if ( bst1[i-1] + bst2[i] > ret )
ret=bst1[i-1]+bst2[i];
inv(map,N,M);
go(bst1,bst2);
for (i=2;i<=M;++i)
if ( bst1[i-1] + bst2[i] > ret )
ret=bst1[i-1]+bst2[i];
printf("%d\n",ret);
return 0;
}