Cod sursa(job #775745)
#include<stdio.h>
FILE *f = fopen("bmatrix.in","r");
FILE *g = fopen("bmatrix.out","w");
#define MaxN 210
int N,M,Sol;
int A[MaxN][MaxN];
char S[MaxN];
int St[MaxN],P[MaxN],D[MaxN];
void citire(void)
{
fscanf(f,"%d %d\n",&N,&M);
for(int i=1;i<=N;i++)
{
fgets(S,sizeof(S),f);
for(int j=0;S[j];j++)
A[i][j+1] = S[j]-'0';
}
}
inline int max(int a,int b)
{
return a > b ? a : b;
}
inline int SubMatMax(int l1,int l2,int c1,int c2)
{
int pf = 0,Sol = 0;
for(int i=c1;i<=c2;i++)
D[i] = St[i] = P[i] = 0;
P[0] = c1-1;
for(int i=l1;i<=l2;i++)
{
for(int j=c1;j<=c2;j++)
if(A[i][j] == 0)
{
for(;St[pf] >= D[j]+1 && pf; --pf);
St[++pf] = D[j]+1; P[pf] = j;
Sol = max(Sol,St[pf]*(j-P[pf-1]));
}
else
pf = 0,D[j] = 0,P[0] = j;
pf = 0;
P[0] = c2+1;
for(int j=c2;j>=c1;j--)
if(A[i][j] == 0)
{
++ D[j];
for(;St[pf] >= D[j] && pf;--pf);
St[++pf] = D[j]; P[pf] = j;
Sol = max(Sol,St[pf]*(P[pf-1]-j));
}
else
pf = 0,P[0] = j;
}
return Sol;
}
void Rezolvare(void)
{
for(int i=1;i<N;i++)
Sol = max(Sol,SubMatMax(1,i,1,M)+SubMatMax(i+1,N,1,M));
for(int i=1;i<M;i++)
Sol = max(Sol,SubMatMax(1,N,1,i)+SubMatMax(1,N,i+1,M));
}
int main()
{
citire();
Rezolvare();
fprintf(g,"%d\n",0);
}