Cod sursa(job #2206676)

Utilizator aurelionutAurel Popa aurelionut Data 23 mai 2018 13:07:23
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 210;
int n, m;
char a[NMAX][NMAX];
int b[NMAX];
int ans = -1;
int st[NMAX], top;
int stg[NMAX], drp[NMAX];

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

void CreateStg(int start, int finish)
{
	top = 0;
	st[0] = start - 1;
	b[start - 1] = -1;
	for (int j = start;j <= finish;++j)
	{
		while (top > 0 && b[j] <= b[st[top]])
			--top;
		stg[j] = j - st[top] - 1;
		st[++top] = j;
	}
}

void CreateDrp(int start, int finish)
{
	top = 0;
	st[0] = finish + 1;
	b[finish + 1] = -1;
	for (int j = finish;j >= start;--j)
	{
		while (top > 0 && b[j] <= b[st[top]])
			--top;
		drp[j] = st[top] - j - 1;
		st[++top] = j;
	}
}

int FirstCase(int start, int finish)
{
	for (int j = 1;j <= m;++j)
		b[j] = 0;
	int ret = 0;
	for (int i = start;i <= finish;++i)
	{
		for (int j = 1;j <= m;++j)
			a[i][j] == '0' ? ++b[j] : b[j] = 0;
		CreateStg(1, m);
		CreateDrp(1, m);
		for (int j = 1;j <= m;++j)
			ret = max(ret, (stg[j] + drp[j] + 1) * b[j]);
	}
	return ret;
}

int SecondCase(int start, int finish)
{
	for (int j = 1;j <= m;++j)
		b[j] = 0;
	int ret = 0;
	for (int i = 1;i <= n;++i)
	{
		for (int j = start;j <= finish;++j)
			a[i][j] == '0' ? ++b[j] : b[j] = 0;
		CreateDrp(start, finish);
		CreateStg(start, finish);
		for (int j = start;j <= finish;++j)
			ret = max(ret, (stg[j] + drp[j] + 1) * b[j]);
	}
	return ret;
}

void Solve()
{
	int aux1, aux2;
	for (int i = 1;i < n;++i)
	{
		aux1 = FirstCase(1, i);
		aux2 = FirstCase(i + 1, n);
		ans = max(ans, aux1 + aux2);
	}
	for (int j = 1;j < m;++j)
	{
		aux1 = SecondCase(1, j);
		aux2 = SecondCase(j + 1, m);
		ans = max(ans, aux1 + aux2);
	}
}

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

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