Cod sursa(job #775796)
#include<stdio.h>
#include<fstream>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
#define MaxN 210
int N,M,Sol;
int A[MaxN][MaxN];
char S[MaxN*MaxN];
int St[MaxN],P[MaxN],D[MaxN];
void citire(void)
{
int a = 0;
f >> N >> M;
f.getline(S,40100,EOF);
for(int i=0;S[i];i++)
if(isdigit(S[i]))
{
++ a;
for(int j=0;isdigit(S[i]);A[a][++j] = S[i++]-'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++)
{
pf = 0;
P[0] = c1-1;
for(int j=c1;j<=c2;j++)
if(A[i][j] == 0)
{
for(;St[pf] > D[j]+1 && pf; --pf);
if(St[pf] < D[j]+1) {
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);
if(St[pf] < D[j]) {
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/2+1;i++)
Sol = max(Sol,SubMatMax(1,i,1,M)+SubMatMax(i+1,N,1,M));
for(int i=1;i<=M/2+1;i++)
Sol = max(Sol,SubMatMax(1,N,1,i)+SubMatMax(1,N,i+1,M));
}
int main()
{
citire();
Rezolvare();
g << Sol << "\n";
}