Cod sursa(job #1315406)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 12 ianuarie 2015 19:51:44
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>

using namespace std;

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

int n, m, maxim;

int l[210][210], up[210], down[210];

bool a[210][210], temp[210][210];

char s[210];

void rot(int n, int m) {

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

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] = temp[i][j];

}

inline int MAX(int a, int b) {
	return (a > b ? a : b);
}

void solve(int n, int m) {

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			l[i][j] = l[i - 1][j] + a[i][j];
	
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++){

			int last = 0;

			for (int k = 1; k <= m; k++)
				if (l[j][k] - l[i - 1][k] != 0){

					int array = (j - i + 1) * (k - last - 1);

					if (array > up[j])
						up[j] = array;
					if (array > down[i])
						down[i] = array;

					last = k;
				}
			int array = (j - i + 1) * (m - last);

			if (array > up[j])
				up[j] = array;
			if (array > down[i])
				down[i] = array;
		}

	for (int i = 1; i <= n; i++) 
		up[i] = MAX(up[i], up[i - 1]);
		
	for (int i = n; i >= 1;i--) 
		down[i] = MAX(down[i], down[i + 1]);

	for (int i = 1; i <= n; i++)
		if (up[i] + down[i + 1] > maxim)
			maxim = up[i] + down[i + 1];
}


int main() {

	fin >> n >> m;

	for (int i = 1; i <= n; i++) {
		fin >> (s + 1);
		for (int j = 1; j <= m; j++) 
			a[i][j] = s[j] - '0';
		
	}

	solve(n, m);

	rot(n, m);

	for (int i = 1; i <= n; i++)
		up[i] = down[i] = 0;

	solve(m, n);

	fout << maxim << "\n";

	return 0;
}