Cod sursa(job #823049)
#include <fstream>
#include <stack>
#define NM 210
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int N,M;
int i,j;
int l,c;
int A[NM][NM];
int H[NM][NM];
int L[NM];
string I;
int ANS;
int cc;
stack<int> S;
int GetSubmatrix (int L1, int C1, int L2, int C2)
{
int ANS=0;
for (i=L1; i<=L2; i++)
{
for (j=C1; j<=C2; j++)
{
while (!S.empty() && H[i][S.top()]>=H[i][j])
{
cc=S.top();
S.pop();
ANS=max(ANS,min(H[i][cc],i-L1+1)*(j-L[cc]));
}
if (!S.empty())
L[j]=S.top()+1;
else
L[j]=C1;
S.push(j);
}
while (!S.empty())
{
cc=S.top();
S.pop();
ANS=max(ANS,min(H[i][cc],i-L1+1)*(C2-L[cc]+1));
}
}
return ANS;
}
int main ()
{
f >> N >> M;
getline(f,I);
for (i=1; i<=N; i++)
{
getline(f,I);
for (j=1; j<=M; j++)
{
A[i][j]=I[j-1]-'0';
H[i][j]=(H[i-1][j]+1)*(1-A[i][j]);
}
}
for (l=1; l<=N/2; l++)
ANS=max(ANS,GetSubmatrix(1,1,l,M)+GetSubmatrix(l+1,1,N,M));
for (c=1; c<=M/2; c++)
ANS=max(ANS,GetSubmatrix(1,1,N,c)+GetSubmatrix(1,c+1,N,M));
g << ANS << '\n';
f.close();
g.close();
return 0;
}