Cod sursa(job #352588)

Utilizator katakunaCazacu Alexandru katakuna Data 2 octombrie 2009 15:50:34
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <cstdio>

#define Nmax 210

int n, m, i, j, l, vmin, A, Cmax, Dmax, sol;
int v[Nmax][Nmax], v2[Nmax][Nmax], a[Nmax][Nmax], b[Nmax][Nmax], C[Nmax], D[Nmax];
char c;

int main () {

	FILE *f = fopen ("bmatrix.in", "r");
	FILE *g = fopen ("bmatrix.out", "w");

	fscanf (f, "%d %d\n", &n, &m);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			fscanf (f, "%c\n", &c);
			v[i][j] = c - '0';
			if (v[i][j]) v[i][j] = -1;
			else {
				if (v[i-1][j] != -1) v[i][j] = v[i-1][j] + 1;
				else v[i][j] = 1;
			}
		}
		fscanf (f, "\n");
	}

	for (i = n; i >= 1; i--) 
		for (j = 1; j <= m; j++) {
			if (v[i][j] == -1) v2[i][j] = -1;
			else {
				if (v2[i+1][j] != -1) v2[i][j] = v2[i+1][j] + 1;
				else v2[i][j] = 1;
			}
		}
	
	for (i = 1; i <= n; i++)  {
		for (j = 1; j <= m; j++) { 
			if (v[i][j] != -1) {
				vmin = v[i][j];
				for (l = j; l >= 1 && vmin != -1; l--) {
					if (v[i][l] < vmin) vmin = v[i][l];
					if (vmin == -1) break;
					A = vmin * (j - l + 1);
					if (a[i][j] < A) a[i][j] = A;
				}
				
				vmin = v2[i][j];
				for (l = j; l <= m && vmin != -1; l++) {
					if (v2[i][l] < vmin) vmin = v2[i][l];
					if (vmin == -1) break;
					A = vmin * (l - j + 1);
					if (b[i][j] < A) b[i][j] = A;
				}				
			}
			
			if (Cmax < a[i][j]) Cmax = a[i][j];
		}
		
		C[i] = Cmax;		
	}
	
	for (i = n; i >= 1; i--) {
		for (j = 1; j <= m; j++) 
			if (Dmax < b[i][j]) Dmax = b[i][j];
		
		D[i] = Dmax;
	}
	
	for (i = 1; i < n; i++)
		if (sol < C[i] + D[i+1]) sol = C[i] + D[i+1];
	
	Cmax = 0;
	for (j = 1; j <= m; j++) {
		for (i = 1; i <= n; i++)
			if ( Cmax < a[i][j] ) Cmax = a[i][j];
		
		C[j] = Cmax;
	}
	
	Dmax = 0;
	for (j = m; j >= 1; j--) {
		for (i = 1; i <= n; i++)
			if ( Dmax < b[i][j] ) Dmax = b[i][j];
		
		D[j] = Dmax;
	}
	
	for (i = 1; i < m; i++)
		if (sol < C[i] + D[i+1]) sol = C[i] + D[i+1];	
	
	fprintf (g, "%d", sol);
	
	fclose (f);
	fclose (g);

	return 0;	
	
}