Pagini recente » Istoria paginii runda/wellcodesimulareclasa9-13martie/clasament | Cod sursa (job #823076)
Cod sursa(job #823076)
#include <fstream>
#include <cstring>
#include <stack>
#define NM 210
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int N,M;
int i,j;
int A[NM][NM];
int HUp[NM][NM],HDown[NM][NM];
int HMaxUp[NM],HMaxDown[NM];
int L[NM],R[NM];
int ANS;
int CANS;
stack<int> S;
void Read ()
{
f >> N >> M;
string I;
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';
}
f.close();
return;
}
void Print ()
{
g << ANS << '\n';
g.close();
return;
}
void Rotate ()
{
int B[NM][NM];
memcpy(B,A,sizeof(B));
for (i=1; i<=N; i++)
for (j=1; j<=M; j++)
A[j][i]=B[i][j];
swap(N,M);
return;
}
void Solve ()
{
memset(HUp,0,sizeof(HUp));
memset(HDown,0,sizeof(HDown));
memset(HMaxUp,0,sizeof(HMaxUp));
memset(HMaxDown,0,sizeof(HMaxDown));
for (i=1; i<=N; i++)
for (j=1; j<=M; j++)
HUp[i][j]=(HUp[i-1][j]+1)*(1-A[i][j]);
for (i=N; i>=1; i--)
for (j=1; j<=M; j++)
HDown[i][j]=(HDown[i+1][j]+1)*(1-A[i][j]);
for (i=1; i<=N; i++)
{
for (j=1; j<=M; j++)
{
while (!S.empty() && HUp[i][S.top()]>=HUp[i][j])
{
R[S.top()]=j-1;
S.pop();
}
if (!S.empty())
L[j]=S.top()+1;
else
L[j]=1;
S.push(j);
}
while (!S.empty())
{
R[S.top()]=M;
S.pop();
}
CANS=0;
for (j=1; j<=M; j++)
CANS=max(CANS,HUp[i][j]*(R[j]-L[j]+1));
HMaxUp[i]=max(HMaxUp[i-1],CANS);
for (j=1; j<=M; j++)
{
while (!S.empty() && HDown[i][S.top()]>=HDown[i][j])
{
R[S.top()]=j-1;
S.pop();
}
if (!S.empty())
L[j]=S.top()+1;
else
L[j]=1;
S.push(j);
}
while (!S.empty())
{
R[S.top()]=M;
S.pop();
}
CANS=0;
for (j=1; j<=M; j++)
CANS=max(CANS,HDown[i][j]*(R[j]-L[j]+1));
HMaxDown[i]=max(HMaxDown[i+1],CANS);
}
for (i=1; i<N; i++)
ANS=max(ANS,HMaxUp[i]+HMaxDown[i+1]);
return;
}
int main ()
{
Read();
Solve();
Rotate();
Solve();
Print();
return 0;
}