Pagini recente » Cod sursa (job #357766) | Cod sursa (job #941483) | Cod sursa (job #772414) | Cod sursa (job #1792002) | Cod sursa (job #2003897)
#include <cstdio>
#include <cstring>
#define NMax 205
#define MAX(a,b)((a)>(b)?(a):(b))
char a[NMax+1][NMax+1];
char v[NMax+1][NMax+1];
char s[NMax+1];
int h[NMax+1][NMax+1];
int maxim1[NMax+1];
int maxim2[NMax+1];
int stiva[NMax+1];
int l[NMax+1];
int r[NMax+1];
int ans;
void Get_best(int N, int M)
{
int i,j,vf;
for(i = 1; i <= N; ++i)
for(j = 1; j <= M; ++j)
if( !v[i][j] ) h[i][j] = 1 + h[i-1][j];
else h[i][j] = 0;
for(i = 1; i < N; ++i)
{
for(stiva[vf=0] = 0, j = 1; j <= M; ++j)
{
while(vf > 0 && h[i][j] <= h[i][ stiva[vf] ] ) --vf;
l[j] = stiva[vf]+1; stiva[++vf] = j;
}
for(stiva[vf=0] = M+1, j = M; j >= 1; --j)
{
while(vf > 0 && h[i][j] <= h[i][ stiva[vf] ] ) --vf;
r[j] = stiva[vf]-1; stiva[++vf] = j;
}
for(maxim1[i] = maxim1[i-1], j = 1; j <= M; ++j) maxim1[i] = MAX( maxim1[i], h[i][j] * ( r[j]-l[j]+1 ) );
}
for(i = N; i >= 1; --i)
for(j = 1; j <= M; ++j)
if( !v[i][j] ) h[i][j] = 1 + h[i+1][j];
else h[i][j] = 0;
for(i = N; i > 1; --i)
{
for(stiva[vf=0] = 0, j = 1; j <= M; ++j)
{
while(vf > 0 && h[i][j] <= h[i][ stiva[vf] ] ) --vf;
l[j] = stiva[vf]+1; stiva[++vf] = j;
}
for(stiva[vf=0] = M+1, j = M; j >= 1; --j)
{
while(vf > 0 && h[i][j] <= h[i][ stiva[vf] ] ) --vf;
r[j] = stiva[vf]-1; stiva[++vf] = j;
}
for(maxim2[i] = maxim2[i+1], j = 1; j <= M; ++j) maxim2[i] = MAX( maxim2[i], h[i][j] * ( r[j]-l[j]+1 ) );
}
for(i = 1; i < N; ++i)
if( maxim1[i] + maxim2[i+1] > ans ) ans = maxim1[i] + maxim2[i+1];
}
int main(){
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
int i,j,N,M,aux;
scanf("%d %d\n",&N,&M);
for(i = 1; i <= N; ++i)
{
fgets(s,NMax,stdin);
for(j = 1; j <= M; ++j) v[i][j] = s[j-1] - '0';
}
Get_best(N,M);
for(i = 1; i <= M; ++i)
for(j = 1; j <= N; ++j) a[i][j] = v[N-j+1][i];
for(i = 1; i <= M; ++i)
for(j = 1; j <= N; ++j) v[i][j] = a[i][j];
aux = N; N = M; M = aux;
Get_best(N,M);
printf("%d\n",ans);
return 0;
}