Cod sursa(job #819039)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 18 noiembrie 2012 14:19:28
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<fstream>
using namespace std;

int a[205][205],u[205][205],l[205],r[205],s[205],sol[2][205],i,n,m,j,x,y,mx,k;
char ch;

void find(int p)
{
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			if (a[i][j]==1)
				u[i][j]=0;
			else u[i][j]=u[i-1][j]+1;
	for (i=1;i<=n;i++)
	{
		k=0;s[0]=0;
		for (j=1;j<=m;j++)
		{
			while ((k>0) && (u[i][j]<=u[i][s[k]]))
				k--;
			l[j]=j-s[k]-1;
			s[++k]=j;
		}
		k=0;s[0]=m+1;
		for (j=m;j>=1;j--)
		{
			while ((k>0) && (u[i][j]<=u[i][s[k]]))
				k--;
			r[j]=s[k]-j-1;
			s[++k]=j;
		}
		x=0;
		for (j=1;j<=m;j++)
			if (u[i][j]*(l[j]+r[j]+1)>x)
				x=u[i][j]*(l[j]+r[j]+1);
		k=0;
		if (p==0)
			sol[0][i]=x;
		else sol[1][n-i+1]=x;
	}
}

void flip()
{
	int i,j;
	for (i=1;i<=n/2;i++)
		for (j=1;j<=m;j++)
			swap(a[i][j],a[n-i+1][j]);
}

void solve()
{
	int i;
	find(0);
	flip();
	find(1);
	flip();
	for (i=2;i<=n;i++)
		sol[0][i]=max(sol[0][i],sol[0][i-1]);
	for (i=n-1;i>=1;i--)
		sol[1][i]=max(sol[1][i],sol[1][i+1]);
	for (i=1;i<n;i++)
		if (sol[0][i]+sol[1][i+1]>mx)
			mx=sol[0][i]+sol[1][i+1];
}

int main()
{
	ifstream f("bmatrix.in");
	ofstream g("bmatrix.out");
	f >> n >> m;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			f >> ch;
			a[i][j]=ch-'0';
		}
	solve();
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			u[j][i]=a[i][j];
	swap(n,m);
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			a[i][j]=u[i][j];
	solve();
	g << mx;
}