Cod sursa(job #357249)

Utilizator Addy.Adrian Draghici Addy. Data 18 octombrie 2009 15:40:57
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <stdio.h>
#define Nmax 203

int vA[Nmax][Nmax], vB[Nmax][Nmax], A[Nmax][Nmax], B[Nmax][Nmax];
int sus[Nmax], jos[Nmax], st[Nmax], dr[Nmax];
int n, m, i, j, vMin, k, susMax, josMax, stMax, drMax, Ac, Bc, L, C, sol;
char x;

int main() {
	
	FILE *f = fopen("bmatrix.in", "r");
	FILE *g = fopen("bmatrix.out", "w");
	
	fscanf(f, "%d %d", &n, &m);
	
	for (i = 1; i <= n; i++) {
		fscanf(f, "\n");
		for (j = 1; j <= m; j++) {
			fscanf(f, "%c", &x);
			if (x != '1') {
				if (vA[i-1][j] != -1)
					vA[i][j] = vA[i-1][j] + 1;
				else
					vA[i][j] = 1;
			}
			else
				vA[i][j] = -1;
		}
	}
	
	for (i = n; i > 0; i--)
		for (j = 1; j <= m; j++)
			if (vA[i][j] != -1) {
				if (vB[i+1][j] != -1)
					vB[i][j] = vB[i+1][j] + 1;
				else
					vB[i][j] = 1;
			}
			else
				vB[i][j] = -1;
	
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			if (vA[i][j] != -1) {
				vMin = vA[i][j];
				for (k = j; k > 0 && vMin != -1; k--) {
					Ac = vMin * (j - k + 1);
					if (Ac > A[i][j])
						A[i][j] = Ac;
					if (vA[i][k-1] < vMin)
						vMin = vA[i][k-1];
				}
				
				vMin = vB[i][j];
				for (k = j; k <= m && vMin != -1; k++) {
					Bc = vMin * (k - j + 1);
					if (Bc > B[i][j])
						B[i][j] = Bc;
					if (vB[i][k+1] < vMin)
						vMin = vB[i][k+1];
				}
			}
			if (A[i][j] > susMax)
				susMax = A[i][j];
		}
		if (susMax > sus[i])
			sus[i] = susMax;
	}
	
	for (i = n; i > 0; i--) {
		for (j = m; j > 0; j--)
			if (B[i][j] > josMax)
				josMax = B[i][j];
		if (josMax > jos[i])
			jos[i] = josMax;
	}
	
	for (L = 1; L < n; L++)
		if (sus[L] + jos[L+1] > sol)
			sol = sus[L] + jos[L+1];
	
	for (j = 1; j <= m; j++) {
		for (i = 1; i <= n; i++)
			if (A[i][j] > stMax)
				stMax = A[i][j];
		st[j] = stMax;
	}
	
	for (j = m; j > 0; j--) {
		for (i = n; i > 0; i--)
			if (B[i][j] > drMax)
				drMax = B[i][j];
		dr[j] = drMax;
	}
	
	for (C = 1; C < m; C++)
		if (st[C] + dr[C+1] > sol)
			sol = st[C] + dr[C+1];
	
	fprintf(g, "%d", sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}