Pagini recente » Cod sursa (job #1890944) | Cod sursa (job #3219492) | Cod sursa (job #3316059) | Cod sursa (job #1733403) | Cod sursa (job #3300893)
// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<cstdio>
#include<algorithm>
constexpr int NMAX=1024;
int N, M;
char mat[NMAX][NMAX];
int up[NMAX][NMAX];
int down[NMAX][NMAX];
int U[NMAX];
int D[NMAX];
int l[NMAX], r[NMAX];
int ans;
void calc()
{
int i, j;
for(j=0;j<M;++j)
up[0][j]=(mat[0][j]=='0');
for(i=1;i<N;++i)
for(j=0;j<M;++j)
up[i][j]=(mat[i][j]=='0' ? up[i-1][j]+1 : 0);
for(j=0;j<M;++j)
down[N-1][j]=(mat[N-1][j]=='0');
for(i=N-2;i>-1;--i)
for(j=0;j<M;++j)
down[i][j]=(mat[i][j]=='0' ? down[i+1][j]+1 : 0);
for(i=0;i<N;++i)
{
for(j=0;j<M;++j)
for(l[j]=j-1;l[j]>-1 && up[i][l[j]]>=up[i][j];l[j]=l[l[j]]);
for(j=M-1;j>-1;--j)
for(r[j]=j+1;r[j]<M && up[i][r[j]]>=up[i][j];r[j]=r[r[j]]);
for(U[i]=j=0;j<M;++j)
U[i]=std::max(U[i], up[i][j]*(r[j]-l[j]-1));
}
for(i=1;i<N;++i)
U[i]=std::max(U[i], U[i-1]);
for(i=0;i<N;++i)
{
for(j=0;j<M;++j)
for(l[j]=j-1;l[j]>-1 && down[i][l[j]]>=down[i][j];l[j]=l[l[j]]);
for(j=M-1;j>-1;--j)
for(r[j]=j+1;r[j]<M && down[i][r[j]]>=down[i][j];r[j]=r[r[j]]);
for(D[i]=j=0;j<M;++j)
D[i]=std::max(D[i], down[i][j]*(r[j]-l[j]-1));
}
for(i=N-2;i>-1;--i)
D[i]=std::max(D[i], D[i+1]);
for(i=1;i<N;++i)
ans=std::max(ans, U[i-1]+D[i]);
}
int solve()
{
int i, j;
calc();
for(i=1;i<std::max(N, M);++i)
for(j=0;j<i;++j)
std::swap(mat[i][j], mat[j][i]);
std::swap(N, M);
calc();
return ans;
}
int main()
{
FILE* f=fopen("bmatrix.in", "r"), *g=fopen("bmatrix.out", "w");
// FILE* f=stdin, *g=stdout;
int i;
fscanf(f, "%d%d", &N, &M);
fgets(mat[0], NMAX, f);
for(i=0;i<N;++i)
fgets(mat[i], NMAX, f);
printf("%d\n", solve());
fclose(f);
fclose(g);
return 0;
}