Cod sursa(job #819156)

Utilizator antimioritzaUngurul Bulan antimioritza Data 18 noiembrie 2012 16:34:41
Problema BMatrix Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <cstring>
#include <queue>
#include <algorithm>
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], m2[MAXN][MAXN], a[MAXN][MAXN];
int dimCoada, maxSol;
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;
	}
	
	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';
		}
	}
	memcpy(m2, m, sizeof(m));
}

void solve() {
	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));
}

void reverse() {
	for (int i = 1; i <= n1; ++i)
		for (int j = 1; j <= n2; ++j)
			m[i][j] = m2[i][n2 - j + 1];
}


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