Cod sursa(job #1963589)

Utilizator horiainfoTurcuman Horia horiainfo Data 12 aprilie 2017 17:17:54
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

ofstream fout("bmatrix.out");

char mat[201][201];
int n, m, maxArea, histo[201];
int best[4][201];

void Turn90()
{
	char aux[201][201];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			aux[j][n - i + 1] = mat[i][j];

	swap(n, m);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			mat[i][j] = aux[i][j];
			cout << mat[i][j];
		}
		cout << '\n';
	}
	cout << '\n';
}

int MaxHistoRectArea()
{
	stack<pair<int, int>> myS;
	int maxArea = 0;

	for (int i = 1; i <= m; i++)
	{
		while (!myS.empty() && histo[i] <= myS.top().first)
		{
			int h = myS.top().first; myS.pop();
			int ant = myS.empty() ? 0 : myS.top().second;
			maxArea = max(maxArea, h * (i - 1 - ant));
		}

		int ant = myS.empty() ? 0 : myS.top().second;
		maxArea = max(maxArea, histo[i] * (i - ant));

		myS.push(make_pair(histo[i], i));
	}

	while (!myS.empty())
	{
		int h = myS.top().first; myS.pop();
		int ant = myS.empty() ? 0 : myS.top().second;

		int area = h * (m - ant);
		maxArea = max(maxArea, area);
	}

	return maxArea;
}

void Process(int v[])
{
	memset(histo, 0, sizeof(histo));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			if (mat[i][j] == '0')
				histo[j] ++;
			else
				histo[j] = 0;

		v[i] = max(v[i - 1], MaxHistoRectArea());
	}
}

int main()
{
	freopen("bmatrix.in", "r", stdin);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%s", &mat[i][1]);

	Process(best[0]);
	Turn90(); Process(best[1]);
	Turn90(); Process(best[2]);
	Turn90(); Process(best[3]);
	
	swap(n, m);
	for (int i = 1; i < n; i++)
		maxArea = max(maxArea, best[0][i] + best[2][n - i]);

	for (int i = 1; i < m; i++)
		maxArea = max(maxArea, best[1][i] + best[3][m - i]);

	fout << maxArea << '\n';
	return 0;
}