Cod sursa(job #819163)

Utilizator antimioritzaUngurul Bulan antimioritza Data 18 noiembrie 2012 16:42:30
Problema BMatrix Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

#define MAXN 300

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

struct point {
	int first, second;
};

int n1, n2;
int m[MAXN][MAXN], a[MAXN][MAXN];
int dimCoada;
point coada[MAXN];

void doSums(int sti, int stj, int fni, int fnj) {

	memset (a, 0, sizeof(a));

	for (int i = sti; i <= fni; ++i)
		for (int j = stj; j <= fnj; ++j)
			if (m[i][j] == 0)
				a[i][j] = a[i - 1][j] + 1;
}

void addElem(point e, int &rez) {
	while (dimCoada > 0 && e.first < coada[dimCoada].first) {

		int dim = 1;
		point aux = coada[dimCoada];

		while (coada[dimCoada].first == coada[dimCoada - 1].first) {
			--dimCoada;
			++dim;
		}

		if (dimCoada == 1)
			dim += coada[dimCoada].second - 1;

		rez = max(rez, dim * aux.first);
		--dimCoada;
	}

	coada[++dimCoada] = e;

}

int doDinamicu (int sti, int stj, int fni, int fnj) {
	int maxDrept = 0;

	doSums (sti, stj, fni, fnj);

	for (int i = sti; i <= fni; ++i) {
		point aux;
		for (int j = stj; j <= fnj; ++j) {
			aux.first = a[i][j];
			aux.second = j - stj + 1;
			addElem(aux, maxDrept);
		}
		aux.first = -1;
		addElem(aux, maxDrept);
		dimCoada = 0;
		for (int j = fnj; j >= stj; --j) {
			aux.first = a[i][j];
			aux.second = j - fnj + 1;
			addElem(aux, maxDrept);
		}
		aux.first = -1;
		addElem(aux, maxDrept);
		dimCoada = 0;
	}

	return maxDrept;
}

void read() {

	fin >> n1 >> n2;

	for (int i = 1; i <= n1; ++i) {
		fin.get();
		for (int j = 1; j <= n2; ++j) {
			char c = fin.get();
			m[i][j] = (int)c - '0';
		}
	}

}

int solve() {
	int maxSol = 0;

	for (int i = 1; i < n1; ++i)
		maxSol = max (maxSol, doDinamicu (1, 1, i, n2) + doDinamicu (i + 1, 1, n1, n2));
	for (int i = 1; i < n2; ++i)
		maxSol = max (maxSol, doDinamicu (1, 1, n1, i) + doDinamicu (1, i + 1, n1, n2));

	return maxSol;
}


int main() {
	read();
	fout << solve();
	return 0;
}