Cod sursa(job #777639)

Utilizator loginLogin Iustin Anca login Data 12 august 2012 22:15:41
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
# include <fstream>
# include <iostream>
# define DIM 202
using namespace std;
int n, m, a[DIM][DIM], b[DIM][DIM], c[DIM][DIM], s[DIM], sol;

void read ()
{
	ifstream fin ("bmatrix.in");
	fin>>n>>m;
	char c;
	for(int i=1;i<=n;++i)
	{
		fin.get();
		for(int j=1;j<=m;++j)
		{
			fin.get(c);
			a[i][j] = c-'0';
			b[j][i]=a[i][j];
		}
	}
}

void solve (int a[DIM][DIM], int n, int m)
{
	int st[DIM], d=0;
	st[0]=0;
	for(int i=0;i<=n+1;++i)
	{
		for(int j=0;j<=m+1;++j)
			c[i][j]=0;
		s[i]=0;
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
			if (!a[i][j])
				c[i][j]=c[i-1][j]+1;
			else
				c[i][j]=0;
		c[i][m+1]=0;
	}
	for(int i=1;i<=n;++i)
	{
		d=0;
		for(int j=1;j<=m+1;++j)
		{
			while(d && c[i][st[d]]>=c[i][j])
			{
				s[i]=max(s[i],c[i][st[d]]*(st[d]-st[d-1]));
				--d;
			}
			st[++d]=j;
		}
		s[i]=max(s[i],s[i-1]);
	}
	for(int i=0;i<=n+1;++i)
	{
		for(int j=0;j<=m+1;++j)
			c[i][j]=0;
	}
	for(int i=n;i;--i)
	{
		for(int j=1;j<=m;++j)
			if (!a[i][j])
				c[i][j]=c[i+1][j]+1;
			else
				c[i][j]=0;
		c[i][m+1]=0;
	}
	for(int i=n;i;--i)
	{
		d=0;
		for(int j=1;j<=m+1;++j)
		{
			while(d && c[i][st[d]]>=c[i][j])
			{
				sol=max(sol,s[i-1]+c[i][st[d]]*(st[d]-st[d-1]));
				--d;
			}
			st[++d]=j;
		}		
	}
}

int main ()
{
	read ();
	solve (a, n, m);
	solve (b, m, n);
	ofstream fout ("bmatrix.out");
	fout<<sol;
	return 0;
}