Cod sursa(job #876124)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 11 februarie 2013 12:36:15
Problema BMatrix Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include<fstream>
#include<cstring>
using namespace std;
int n,m,sol;
char mat[210][210],A[2][210][210];
struct Turn{int h,j;};
Turn a[210],stiva[210];
int vf=-1,Nr[1001][1001];

inline int ArieMax(int p,int n,int m)
{
	int i,arie,ariemax=0,x,k,i1,nr;
	for(i=1;i<=n;i++)
		for(k=1;k<=m;k++)
		{
			if(A[p][i][k]=='0')
			{
				nr=0;
				i1=i;
				while(A[p][i1][k]=='0' && i1>=1)
				{
					nr++;
					i1--;
				}
				Nr[i][k]=nr;
			}
			else Nr[i][k]=0;
		}
	vf=-1;
	for(k=1;k<=n;k++)
	{
		a[0].h=a[0].j=0;
		a[m+1].h=a[m+1].j=0;
		stiva[++vf]=a[0];
		a[1].h=Nr[k][1];
		a[1].j=1;
		stiva[++vf]=a[1];
		for(i=2;i<=m+1;i++)
		{
			a[i].h=Nr[k][i];
			a[i].j=i;
			x=a[i].h;
			if(stiva[vf].h>x)
			{
				while(stiva[vf].h>x)
				{
					arie=stiva[vf].h*(a[i].j-stiva[vf].j);
					if(arie>ariemax) ariemax=arie;
					vf--;
				}
				stiva[++vf]=a[i];
			}
			else
				if(stiva[vf].h<x)
					stiva[++vf]=a[i];
		}
		while(vf>=0)
		{
			arie=stiva[vf].h*(m-stiva[vf].j);
			if(arie>ariemax) ariemax=arie;
			vf--;
		}
		vf=-1;
		stiva[++vf]=a[m+1];
		a[m].j=1;
		stiva[++vf]=a[m];
		for(i=m-1;i>=0;i--)
		{
			a[i].j=m-i+1;
			x=a[i].h;
			if(stiva[vf].h>x)
			{
				while(stiva[vf].h>x)
				{
						arie=stiva[vf].h*(a[i].j-stiva[vf].j);
						if(arie>ariemax) ariemax=arie;
						vf--;
				}
				stiva[++vf]=a[i];
			}
			else
				if(stiva[vf].h<x)
					stiva[++vf]=a[i];
		}
		while(vf>=0)
		{
			arie=stiva[vf].h*(m-stiva[vf].j);
			if(arie>ariemax) ariemax=arie;
			vf--;
		}
	}
	return ariemax;
}

inline int Solutie(int lin,int col)
{
	int i,j,na,nb,ma,mb,rez;
	for(i=1;i<=lin;i++)
		for(j=1;j<=col;j++)
			A[0][i][j]=mat[i][j];
	na=lin;
	ma=col;
	if(col==m)
	{
		for(i=1;i+lin<=n;i++)
			for(j=1;j<=m;j++)
				A[1][i][j]=mat[i+lin][j];
		nb=n-lin;
		mb=m;
	}
	else
	{
		for(i=1;i<=n;i++)
			for(j=1;j+col<=m;j++)
				A[1][i][j]=mat[i][j+col];
		nb=n;
		mb=m-col;
	}
	rez=ArieMax(0,na,ma);
	rez+=ArieMax(1,nb,mb);
	return rez;
}

int main()
{
	int i;
	ifstream fin("bmatrix.in");
	fin>>n>>m;
	for(i=1;i<=n;i++)
		fin>>(mat[i]+1);
	fin.close();
	
	for(i=1;i<n;i++)
		sol=max(sol,Solutie(i,m));
	for(i=1;i<m;i++)
		sol=max(sol,Solutie(n,i));
	
	ofstream fout("bmatrix.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}