Cod sursa(job #1783902)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 19 octombrie 2016 16:21:58
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

bool matrix[300][300];
int n, m;
int h[300];
long long lmax[300], lmaxoglind[300];

void roteste(); /// roteste spre dreapta
void oglindeste(); /// inversiune fata de mij axei ox

long long skyline(int c); /// cel mai mare dreptunghi care are baza pe linia c, c din { 1, 2, ... n - 1 }

long long f(); /// maximul pt matrix (dupa se roteste matrixul si se apeleaza din nou)

int main()
{
	ifstream in("bmatrix.in");
	ofstream out("bmatrix.out");

	in >> n >> m;

	char c;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			in >> c;
			if (c == '0')
				matrix[i][j] = true;
		}
	}
	long long mxm = f();
	oglindeste();
	roteste();
	mxm = max(mxm, f());

	out << mxm;

	return 0;
}

long long f()
{
	for (int i = 1; i <= n; i++)
		lmax[n - i + 1] = skyline(i);
	oglindeste();
	for (int i = 1; i <= n; i++)
		lmaxoglind[i] = skyline(i);

	long long mxm = 0;

	for (int i = 1; i < n; i++) {
		lmaxoglind[i] = max(lmaxoglind[i], lmaxoglind[i - 1]);
		mxm = max(mxm, lmax[i + 1] + lmaxoglind[i]);
	}


	return mxm;
}


long long skyline(int c)
{
	if (c == 1) {
		int r = 0, mxm = 0;
		for (int i = 1; i <= m; i++) {
			if (matrix[1][i])
				r++, h[i] = 1;
			else
				mxm = max(mxm, r), h[i] = 0, r = 0;
		}
		mxm = max(mxm, r);
		return mxm;
	}

	for (int i = 1; i <= m; i++) {
		if (matrix[c][i] == 0)
			h[i] = 0;
		else
			h[i]++;
	}

	stack <pair <int, int>> s;

	long long mxm = 0;

	for (int i = 1; i <= m; i++) {
		int l = 0;
		while (!s.empty() && s.top().first >= h[i]) {
			l += s.top().second;
			mxm = max(mxm, 1ll * l * s.top().first);
			s.pop();
		}
		s.push({ h[i], l + 1 });
	}

	int l = 0;
	while (!s.empty()) {
		l += s.top().second;
		mxm = max(mxm, 1ll * l * s.top().first);
		s.pop();
	}

	return mxm;
}


void roteste()
{
	bool matrix2[250][250];
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			matrix2[i][j] = matrix[j][i];

	swap(n, m);
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			matrix[i][j] = matrix2[i][j];
}

void oglindeste()
{
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n / 2; j++)
			swap(matrix[j][i], matrix[n - j + 1][i]);
	}
}