Pagini recente » Cod sursa (job #198266) | Cod sursa (job #910017) | Cod sursa (job #1476368) | Cod sursa (job #1247326) | Cod sursa (job #728285)
Cod sursa(job #728285)
#include <fstream>
using namespace std;
const char InFile[]="bmatrix.in";
const char OutFile[]="bmatrix.out";
const int MaxN=205;
ifstream fin(InFile);
ofstream fout(OutFile);
int N,M,up[MaxN];
char A[MaxN][MaxN],B[MaxN][MaxN];
struct node
{
int height,length,prev,next;
};
node nodes[MaxN];
int counts[MaxN][MaxN],sol,D[MaxN];
int BestUp[MaxN],BestDown[MaxN];
inline void solve()
{
int sol=0;
for(register int i=1;i<=M;++i)
{
up[i]=0;
}
for(register int i=1;i<=N;++i)
{
for(register int j=1;j<=M;++j)
{
if(A[i][j]=='0')
{
++up[j];
}
else
{
up[j]=0;
}
nodes[j].prev=j-1;
nodes[j].next=j+1;
nodes[j].length=1;
nodes[j].height=up[j];
counts[up[j]][++counts[up[j]][0]]=j;
}
D[i]=0;
nodes[M].next=0;
for(register int k=N;k>=0;--k)
{
for(register int l=1;l<=counts[k][0];++l)
{
int x=counts[k][l];
D[i]=max(D[i],nodes[x].length*nodes[x].height);
int left=nodes[x].prev;
int right=nodes[x].next;
int y=right;
if(nodes[left].height>nodes[right].height)
{
y=left;
}
nodes[nodes[x].prev].next=nodes[x].next;
nodes[nodes[x].next].prev=nodes[x].prev;
nodes[y].height=min(nodes[y].height,nodes[x].height);
nodes[y].length+=nodes[x].length;
nodes[x].prev=nodes[x].next=0;
}
counts[k][0]=0;
}
}
}
inline void mirror()
{
int i=1,j=N;
while(i<j)
{
for(register int k=1;k<=M;++k)
{
swap(A[i][k],A[j][k]);
}
++i;
--j;
}
}
inline void rotate90()
{
for(register int i=1;i<=N;++i)
{
for(register int j=1;j<=M;++j)
{
B[i][j]=A[i][j];
}
}
int N2=N;
int M2=M;
int ti=N2;
int tj=1;
swap(N,M);
for(register int i=1;i<=N;++i)
{
for(register int j=1;j<=M;++j)
{
A[i][j]=B[ti][tj];
--ti;
if(ti==0)
{
ti=N2;
++tj;
}
}
}
}
inline void solve2()
{
for(register int i=1;i<=N;++i)
{
BestUp[i]=max(BestUp[i],BestUp[i-1]);
}
for(register int i=N;i>0;--i)
{
BestDown[i]=max(BestDown[i],BestDown[i+1]);
}
for(register int i=1;i<=N;++i)
{
sol=max(sol,BestUp[i]+BestDown[i+1]);
}
}
int main()
{
fin>>N>>M;
for(register int i=1;i<=N;++i)
{
fin>>(A[i]+1);
}
fin.close();
nodes[0].height=-1;
solve();
for(register int i=1;i<=N;++i)
{
BestUp[i]=D[i];
}
mirror();
solve();
for(register int i=1;i<=N;++i)
{
BestDown[N-i+1]=D[i];
}
solve2();
mirror();
rotate90();
for(register int i=1;i<MaxN;++i)
{
BestUp[i]=BestDown[i]=0;
}
solve();
for(register int i=1;i<=N;++i)
{
BestUp[i]=D[i];
}
mirror();
solve();
for(register int i=1;i<=N;++i)
{
BestDown[N-i+1]=D[i];
}
solve2();
fout<<sol;
fout.close();
return 0;
}