Cod sursa(job #522310)

Utilizator cosmyoPaunel Cosmin cosmyo Data 14 ianuarie 2011 20:16:08
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <cstdio>
const int N = 205;
int L[N][N], l[N][N], n, m, a[N][N], b[N][N], x[N][N], y[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, c1;
	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] == '0')
				x[i][j] = x[i][j - 1] + 1;
			else
				x[i][j] = 0;
	for(i = n; i >= 1; --i)
		for(j = m; j >= 1; --j)
			if(c[i][j] == '0')
				y[i][j] = y[i][j + 1] + 1;
			else
				y[i][j] = 0;
	int k;
	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 {
			L[i][j] = x[i][j];  
			l[i][j] = 1;
			c1 = x[i][j];
			for(k = i - 1; k >= 1; --k) {
				c1 = min(c1, x[k][j]);
				if(L[i][j] * l[i][j] < c1 * (i - k + 1))
					L[i][j] = c1,	l[i][j] = i - k +1 ;
			}
			}
					
		a[i][j] = max(a[i][j - 1], max(a[i - 1][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 {
				c1 = y[i][j];
				L[i][j] = y[i][j];
				l[i][j] = 1;
				for(k = i + 1; k <= n; ++k) {
					c1 = min(c1, y[k][j]);
					if(L[i][j] * l[i][j] < c1 * (k - i +1))
						L[i][j] = c1,	l[i][j] = k - i + 1; 
				}
			}
			
		b[i][j] = max(b[i][j + 1], max(b[i +1][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];
	for(i = 1; i <= m- 1; ++i)
		if(a[n][i] + b[1][i + 1] > s)
			s = a[n][i] + b[1][i + 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;
}