Cod sursa(job #522297)

Utilizator cosmyoPaunel Cosmin cosmyo Data 14 ianuarie 2011 19:22:31
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <cstdio>
const int N = 205;
int L[N][N], l[N][N], n, m, a[N][N], b[N][N];
char c[N][N];

int min(int a, int b) {
	return a < b ? a : b;
}

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

int main() {
	freopen("bmatrix.in", "r", stdin);
	freopen("bmatrix.out", "w", stdout);
	int j, i, l1 ,c1, l2, c2;
	char C;
	scanf("%d %d", &n, &m);
	for(i = 1;i <= n; ++i) {
		scanf("%c", &c);
		for(j = 1; j <= m; ++j)
			scanf("%c", &c[i][j]);
	}

	for(i = 1; i <= n; ++i) 
		for(j = 1; j <=m; ++j) {
			if(c[i][j] =='1')
				l[i][j] = 0,	L[i][j] = 0;
			else {
			l1 = max(min(L[i][j - 1] + 1, L[i - 1][j]), 1);
			c1 = l[i - 1][j] + 1;
			l2 = L[i][j - 1] + 1;
			c2 = max(1, min(l[i][j - 1], l[i - 1][j] + 1));
			if(l1 * c1 > l2 * c2) 
				L[i][j] = l1,	l[i][j] = c1;
			else
				L[i][j] = l2,	l[i][j] = c2;
			}
		a[i][j] = max(a[i][j - 1], a[i - 1][j]);
		a[i][j] = max(a[i][j], L[i][j] * l[i][j]);
	}
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= m; ++j)
			L[i][j] = l[i][j] = 0;
	for(i = n; i >= 1; --i) 
		for(j = m; j >= 1; --j) {
			if(c[i][j] =='1')
				l[i][j] = 0,	L[i][j] = 0;
			else {
				l1 = max(min(L[i][j  + 1] + 1, L[i + 1][j]), 1);
				c1 = l[i + 1][j] + 1;
				l2 = L[i][j + 1] + 1;
				c2 = max(1, min(l[i][j -1], l[i - 1][j] + 1));
				if(l1 * c1 > l2 * c2)
					L[i][j] = l1, 	l[i][j] = c1;
				else
					L[i][j] = l2, 	l[i][j] = c2;
			}
		b[i][j] = max(b[i][j + 1], b[i + 1][j]);
		b[i][j] = max(L[i][j] * l[i][j], b[i][j]);
	}
	int s = 0;
	for(i = 1; i <= n - 1; ++i)
		if(a[i][m] + b[i + 1][1] > s)
			s = a[i][m] + b[i +1][1];
	printf("%d \n", s);/*
	for(i = 1; i <= n; ++i) {
		for(j = 1; j <= m; ++j)
			printf("%d ", b[i][j] );
		printf("\n");
	}
	*/
	
	return 0;
}