Cod sursa(job #728285)

Utilizator ChallengeMurtaza Alexandru Challenge Data 28 martie 2012 16:52:08
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#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;
}