Cod sursa(job #1295209)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 18 decembrie 2014 23:08:23
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <algorithm>
#define DIM 205
#define infile "bmatrix.in"
#define outfile "bmatrix.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

int m, n;

char s[DIM][DIM], ss[DIM][DIM];

int a[DIM][DIM], D[DIM][DIM], v[DIM];

void DP() {
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= n; ++j)
			a[i][j] = a[i - 1][j] + s[i][j] - '0';
	for (int i = m; i >= 1; --i) {
		for (int j = i; j <= m; ++j) {
			for (int k = 1; k <= n; ++k)
				v[k] = a[j][k] - a[i - 1][k];
			int Max = 0, len = 0;
			for (int k = 1; k <= n; ++k) {
				if (!v[k])
					++len;
				else {
					Max = std::max(Max, len); 
					len = 0;
				}
			}
			Max = std::max(Max, len);
			D[i][j] = Max * (j - i + 1);
			if (i < j) {
				D[i][j] = std::max(D[i][j], D[i + 1][j]);
				D[i][j] = std::max(D[i][j], D[i][j - 1]);
			}
		}
	}
}

int main() {

	int SOL = 0;

	f >> m >> n;
	for (int i = 1; i <= m; ++i)
		f >> s[i] + 1;

	DP();

	for (int i = 1; i < m; ++i)
		SOL = std::max(SOL, D[1][i] + D[i + 1][m]);

	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= n; ++j)
			ss[j][m - i + 1] = s[i][j];
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= n; ++j)
			s[i][j] = ss[i][j];

	DP();

	for (int i = 1; i < m; ++i)
		SOL = std::max(SOL, D[1][i] + D[i + 1][m]);

	g << SOL;

	return 0;
}

//Trust me, I'm the Doctor!