Cod sursa(job #625212)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 24 octombrie 2011 00:35:35
Problema BMatrix Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <stdio.h>
#include <string.h>

long MAX, M, N, i, j, sol, a[210][210], v[210][210];
char ch;

void findSum() {
	memset(v, 0, sizeof(v));
	for (i = 1; i <= N; ++i) {
		long s = 0;
		for (j = 1; j <= M; ++j) {
			if (a[j][i] == 1) s = 0;
			else ++s;
			v[j][i] = s; 
		}
	}	
}

void rotate() {
	long g[210][210];
	for (long i = 1; i <= M; ++i) {
		for (long j = 1; j <= N; ++j) {
			g[j][i] = a[i][j];
		}
	}
	long z = M;
	M = N;
	N = z;
	memset(a, 0, sizeof(a));
	for (long i = 1; i <= M; ++i) 
		for (long j = 1; j <= N; ++j)
			a[i][j] = g[i][j];
}

/*long part(long l1, long l2) {

	return max;
}*/

void solveH() {
	for (long i = 2; i <= M; ++i) { 
		sol = 0;
		//sol += part(1, i - 1);
		long max = 0, co = 0, st[210];
		for (long j = 1; j < i; ++j) {
			co = 0;
			memset(st, 0, sizeof(st));
			for (long k = 1; k <= N; ++k) {
				if (v[j][k] == 0) {
					co = 0;
				} else {
					while (v[j][k] < st[co]) --co;
					st[++co] = v[j][k];
					if (max < co * st[1]) max = co * st[1];
				}
			}
			co = 0;
			memset(st, 0, sizeof(st));		
			for (long k = N; k >= 1; --k) {
				if (v[j][k] == 0) {
					co = 0;
				} else {
					while (v[j][k] < st[co]) --co;
					st[++co] = v[j][k];
					if (max < co * st[1]) max = co * st[1];
				}			
			}
		}	
		sol += max;
		//---------
		long aux[210][210];
		
		memset(aux, 0, sizeof(aux));
		
		for (long I = 1; I <= M; ++I) 
			for (long J = 1; J <= N; ++J) 
				aux[I][J] = v[I][J];
			
		for (long I = 1; I <= N; ++I) {
			long h = i;
			while (v[h][I] != 0 && h <= M) {
				v[h][I] -= v[i - 1][I];
				++h;
			}
		}
		//-------
		//sol += part(i, M);
		max = 0, co = 0;
		for (long j = i; j <= M; ++j) {
			co = 0;
			memset(st, 0, sizeof(st));
			for (long k = 1; k <= N; ++k) {
				if (v[j][k] == 0) {
					co = 0;
				} else {
					while (v[j][k] < st[co]) --co;
					st[++co] = v[j][k];
					if (max < co * st[1]) max = co * st[1];
				}
			}
			co = 0;
			memset(st, 0, sizeof(st));		
			for (long k = N; k >= 1; --k) {
				if (v[j][k] == 0) {
					co = 0;
				} else {
					while (v[j][k] < st[co]) --co;
					st[++co] = v[j][k];
					if (max < co * st[1]) max = co * st[1];
				}			
			}
		}	
		sol += max;		
		
		for (long I = 1; I <= M; ++I) 
			for (long J = 1; J <= N; ++J) 
				v[I][J] = aux[I][J];
			
		if (sol > MAX) MAX = sol;		
	}
}

int main() {
	freopen("bmatrix.in", "r", stdin);
	freopen("bmatrix.out", "w", stdout);
	
	scanf("%ld %ld\n", &M, &N);
	for (i = 1; i <= M; ++i) {
		for (j = 1; j <= N; ++j) {
			scanf("%c", &ch);
			a[i][j] = ch - '0';
		}
		scanf("\n");
	}
	
	findSum();
	sol = 0;
	solveH();
	rotate();
	findSum();
	sol = 0;
	solveH();	
	
	printf("%ld\n", MAX);
	
	return 0;
}