Cod sursa(job #2206698)

Utilizator aurelionutAurel Popa aurelionut Data 23 mai 2018 15:00:09
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 210;
int n, m;
char a[NMAX][NMAX];
char b[NMAX][NMAX];
int dUp[NMAX][NMAX], dDown[NMAX][NMAX];
int st[NMAX], top;
int stg[NMAX], drp[NMAX];
int ans = 0;

void Read()
{
	ifstream fin("bmatrix.in");
	fin >> n >> m;
	for (int i = 1;i <= n;++i)
		fin >> (a[i] + 1);
	fin.close();
}

void Initialize()
{
	for (int i = 0;i <= n + 1;++i)
		for (int j = 0;j <= m + 1;++j)
			dUp[i][j] = dDown[i][j] = 0;
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j)
			a[i][j] == '0' ? dUp[i][j] = dUp[i - 1][j] + 1 : dUp[i][j] = 0;
	for (int i = n;i >= 1;--i)
		for (int j = 1;j <= m;++j)
			a[i][j] == '0' ? dDown[i][j] = dDown[i + 1][j] + 1 : dDown[i][j] = 0;
}

void Rotate()
{
	int p = n;
	for (int i = 1;i <= n;++i)
	{
		for (int j = 1;j <= m;++j)
			b[j][p] = a[i][j];
		--p;
	}
	swap(n, m);
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j)
			a[i][j] = b[i][j];
	for (int i = 1;i <= n;++i)
		a[i][m + 1] = 0;
	for (int j = 1;j <= m;++j)
		a[n + 1][j] = 0;
}

void CreateStg(int line, bool ok)
{
	if (ok)
		dUp[line][0] = -1;
	else
		dDown[line][0] = -1;
	top = 0;
	st[0] = 0;
	for (int i = 1;i <= m;++i)
	{
		if (ok)
			while (top > 0 && dUp[line][i] <= dUp[line][st[top]])
				--top;
		else
			while (top > 0 && dDown[line][i] <= dDown[line][st[top]])
				--top;
		stg[i] = i - st[top] - 1;
		st[++top] = i;
	}
}

void CreateDrp(int line, bool ok)
{
	if (ok)
		dUp[line][m + 1] = -1;
	else
		dDown[line][m + 1] = -1;
	top = 0;
	st[0] = m + 1;
	for (int i = m;i >= 1;--i)
	{
		if (ok)
			while (top > 0 && dUp[line][i] <= dUp[line][st[top]])
				--top;
		else
			while (top > 0 && dDown[line][i] <= dDown[line][st[top]])
				--top;
		drp[i] = st[top] - i - 1;
		st[++top] = i;
	}
}

void Solve()
{
	int aux1, aux2;
	Initialize();
	for (int i = 1;i < n;++i)
	{
		aux1 = aux2 = 0;
		CreateStg(i, true);
		CreateDrp(i, true);
		for (int j = 1;j <= m;++j)
			aux1 = max(aux1, (stg[j] + drp[j] + 1) * dUp[i][j]);
		CreateStg(i + 1, false);
		CreateDrp(i + 1, false);
		for (int j = 1;j <= m;++j)
			aux2 = max(aux2, (stg[j] + drp[j] + 1) * dDown[i + 1][j]);
		ans = max(ans, aux1 + aux2);
	}
	Rotate();
	Initialize();
	for (int i = 1;i < n;++i)
	{
		aux1 = aux2 = 0;
		CreateStg(i, true);
		CreateDrp(i, true);
		for (int j = 1;j <= m;++j)
			aux1 = max(aux1, (stg[j] + drp[j] + 1) * dUp[i][j]);
		CreateStg(i + 1, false);
		CreateDrp(i + 1, false);
		for (int j = 1;j <= m;++j)
			aux2 = max(aux2, (stg[j] + drp[j] + 1) * dDown[i + 1][j]);
		ans = max(ans, aux1 + aux2);
	}
}

void Write()
{
	ofstream fout("bmatrix.out");
	fout << ans << "\n";
	fout.close();
}

int main()
{
	Read();
	Solve();
	Write();
	return 0;
}