Cod sursa(job #841122)
#include <fstream>
#include <stack>
#include <cstring>
using namespace std;
const int Nmax = 210;
int Hmax[Nmax][2],Sol,Act;
int Right[Nmax],Left[Nmax];
int L[Nmax][Nmax][2];
int N,M,A[Nmax][Nmax];
ifstream F("bmatrix.in");
ofstream G("bmatrix.out");
#define FOR(i,start,stop,inc) for (int i=start;i!=stop;i+=inc)
stack<int> St;
void Solve()
{
memset(L,0,sizeof(L));
memset(Hmax,0,sizeof(Hmax));
FOR(i,1,N+1,+1) FOR(j,1,M+1,+1) L[i][j][0]= ( L[i-1][j][0]+1 ) * ( 1-A[i][j] );
FOR(i,N,0,-1) FOR(j,1,M+1,+1) L[i][j][1]= ( L[i+1][j][1]+1 ) * ( 1-A[i][j] );
for (int i=1;i<=N;++i)
for (int x=0;x<2;++x)
{
for (int j=1;j<=M;++j)
{
for ( ; St.size() && L[i][St.top()][x] >= L[i][j][x] ; St.pop() )
Right[ St.top() ] = j-1;
Left[j]= St.size() ? St.top()+1 : 1;
St.push(j);
}
for ( ; St.size() ; St.pop() )
Right[St.top()]=M;
Act=0;
for (int j=1;j<=M;++j)
Act=max(Act,L[i][j][x]*(Right[j]-Left[j]+1));
Hmax[i][x]=max(Hmax[i-(x==0 ? 1 : -1)][x],Act);
}
for (int i=1;i<N;++i)
Sol=max(Sol,Hmax[i][0]+Hmax[i+1][1]);
}
void Rotate()
{
int B[Nmax][Nmax];
memcpy(B,A,sizeof(B));
FOR(i,1,N+1,+1) FOR(j,1,M+1,+1) A[j][i]=B[i][j];
swap(N,M);
}
#undef FOR
string Str;
int main()
{
F>>N>>M;
getline(F,Str);
for (int i=1;i<=N;++i)
{
getline(F,Str);
for (int j=1;j<=M;++j)
A[i][j]=Str[j-1]-'0';
}
Solve();
Rotate();
Solve();
G<<Sol<<'\n';
}