Cod sursa(job #1255389)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 4 noiembrie 2014 19:12:04
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.09 kb
#include<fstream>
#include<string>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");

const int nmax = 206;
string s;
int n, m, rasp, ms[nmax][nmax], maxst[nmax], maxdr[nmax], maxlin[3][nmax];
bool mat[nmax][nmax];

int orizontal()
{
	int rez = 0;
	for(int i = 1; i<=n; i++)
	{
		for(int j = 1; j<=m; j++)
		{
			if(mat[i][j]==0)
			{
				ms[i][j] = ms[i - 1][j] + 1;
			}
			else
			{
				ms[i][j] = 0;
			}
		}

		ms[i][0] = ms[i][m + 1] = -1;
		for(int j = 1; j<=m; j++)
		{
			int h;
			for(h = j - 1; ms[i][j]<=ms[i][h];)
			{
				h = maxst[h];
			}

			maxst[j] = h;
		}

		for(int j = m; j>0; j--)
		{
			int h;
			for(h = j + 1; ms[i][j]<=ms[i][h];)
			{
				h = maxdr[h];
			}

			maxdr[j] = h;
		}

		maxlin[1][i] = maxlin[1][i - 1];
		for(int j = 1; j<=m; j++)
		{
			if(ms[i][j] * (maxdr[j] - maxst[j] - 1)>maxlin[1][i])
			{
				maxlin[1][i] = ms[i][j] * (maxdr[j] - maxst[j] - 1);
			}
		}
	}
	for(int i = 0; i<nmax; i++)
		for(int j = 0; j<nmax; j++)
			ms[i][j] = 0;

	for(int i = n; i>=1; i--)
	{
		for(int j = 1; j<=m; j++)
		{
			if(mat[i][j]==0)
			{
				ms[i][j] = ms[i + 1][j] + 1;
			}
			else
			{
				ms[i][j] = 0;
			}
		}

		ms[i][0] = ms[i][m + 1] = -1;
		for(int j = 1; j<=m; j++)
		{
			int h;
			for(h = j - 1; ms[i][j]<=ms[i][h];)
			{
				h = maxst[h];
			}

			maxst[j] = h;
		}

		for(int j = m; j>0; j--)
		{
			int h;
			for(h = j + 1; ms[i][j]<=ms[i][h];)
			{
				h = maxdr[h];
			}

			maxdr[j] = h;
		}

		maxlin[2][i] = maxlin[2][i + 1];
		for(int j = 1; j<=m; j++)
		{
			if(ms[i][j] * (maxdr[j] - maxst[j] - 1)>maxlin[2][i])
			{
				maxlin[2][i] = ms[i][j] * (maxdr[j] - maxst[j] - 1);
			}
		}
	}
	for(int i = 0; i<nmax; i++)
		for(int j = 0; j<nmax; j++)
			ms[i][j] = 0;

	for(int i = 1; i<=n; i++)
	{
		if(maxlin[1][i] + maxlin[2][i + 1]>rez)
			rez = maxlin[1][i] + maxlin[2][i + 1];
	}
	for(int i = 1; i<3; i++)
		for(int j = 0; j<nmax; j++)
			maxlin[i][j] = 0;

	return rez;
}

int vertical()
{
	int rez = 0;
	for(int i = 1; i<=m; i++)
	{
		for(int j = 1; j<=n; j++)
		{
			if(mat[j][i]==0)
			{
				ms[j][i] = ms[j][i - 1] + 1;
			}
			else
			{
				ms[j][i] = 0;
			}
		}

		ms[0][i] = ms[m + 1][i] = -1;
		for(int j = 1; j<=n; j++)
		{
			int h;
			for(h = j - 1; ms[j][i]<=ms[h][i];)
			{
				h = maxst[h];
			}

			maxst[j] = h;
		}

		for(int j = n; j>0; j--)
		{
			int h;
			for(h = j + 1; ms[j][i]<=ms[h][i];)
			{
				h = maxdr[h];
			}

			maxdr[j] = h;
		}

		maxlin[1][i] = maxlin[1][i - 1];
		for(int j = 1; j<=n; j++)
		{
			if(ms[j][i] * (maxdr[j] - maxst[j] - 1)>maxlin[1][i])
			{
				maxlin[1][i] = ms[j][i] * (maxdr[j] - maxst[j] - 1);
			}
		}
	}
	for(int i = 0; i<nmax; i++)
		for(int j = 0; j<nmax; j++)
			ms[i][j] = 0;

	for(int i = m; i>=1; i--)
	{
		for(int j = 1; j<=n; j++)
		{
			if(mat[j][i]==0)
			{
				ms[j][i] = ms[j][i + 1] + 1;
			}
			else
			{
				ms[j][i] = 0;
			}
		}

		ms[0][i] = ms[m + 1][i] = -1;
		for(int j = 1; j<=m; j++)
		{
			int h;
			for(h = j - 1; ms[j][i]<=ms[h][i];)
			{
				h = maxst[h];
			}

			maxst[j] = h;
		}

		for(int j = m; j>0; j--)
		{
			int h;
			for(h = j + 1; ms[j][i]<=ms[h][i];)
			{
				h = maxdr[h];
			}

			maxdr[j] = h;
		}

		maxlin[2][i] = maxlin[2][i + 1];
		for(int j = 1; j<=m; j++)
		{
			if(ms[j][i] * (maxdr[j] - maxst[j] - 1)>maxlin[2][i])
			{
				maxlin[2][i] = ms[j][i] * (maxdr[j] - maxst[j] - 1);
			}
		}
	}
	for(int i = 0; i<nmax; i++)
		for(int j = 0; j<nmax; j++)
			ms[i][j] = 0;

	for(int i = 1; i<=m; i++)
	{
		if(maxlin[1][i] + maxlin[2][i + 1]>rez)
			rez = maxlin[1][i] + maxlin[2][i + 1];
	}
	for(int i = 1; i<3; i++)
		for(int j = 0; j<nmax; j++)
			maxlin[i][j] = 0;

	return rez;
}

int main(){
	int player_unu=0;

	in>>n>>m;getline(in, s);
	for(int i = 1; i<=n; i++)
	{
		getline(in, s);
		for(int j = 0; j<(int)s.size(); j++)
			mat[i][j + 1] = s[j] - '0';
	}

	int a = orizontal(), b = vertical();
	out<<max(a, b)<<'\n';

	return player_unu;
}