Cod sursa(job #728203)

Utilizator ChallengeMurtaza Alexandru Challenge Data 28 martie 2012 16:08:08
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 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];

struct node
{
	int height,length,prev,next;
};
node nodes[MaxN];
int counts[MaxN][MaxN];

inline int solve(int x1,int y1,int x2,int y2)
{
	int sol=0;
	for(register int i=y1;i<=y2;++i)
	{
		up[i]=0;
	}
	for(register int i=x1;i<=x2;++i)
	{
		for(register int j=y1;j<=y2;++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;
		}
		nodes[y2].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];
				sol=max(sol,nodes[x].length*nodes[x].height);
				int left=nodes[x].prev;
				int right=nodes[x].next;
				int y=left;
				if(right==0)
				{
					if(left==0)
					{
						break;
					}
					else
					{
						y=left;
					}
				}
				else
				{
					if(left==0)
					{
						y=right;
					}
					else
					{
						if(nodes[left].height>nodes[right].height)
						{
							y=left;
						}
						else
						{
							y=right;
						}
					}
				}
				
				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;
		}

	}
	return sol;
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=N;++i)
	{
		fin>>(A[i]+1);
	}
	fin.close();
	
	int sol=solve(1,1,N,M);
	for(register int i=1;i<=N;++i)
	{
		int tsol=solve(1,1,i,M)+solve(i+1,1,N,M);
		if(tsol>sol)
		{
			sol=tsol;
		}

	}
	
	for(register int j=1;j<=M;++j)
	{
		int tsol=solve(1,1,N,j)+solve(1,j+1,N,M);
		if(tsol>sol)
		{
			sol=tsol;
		}
	}
	
	fout<<sol;
	fout.close();
	return 0;
}