Cod sursa(job #625209)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 24 octombrie 2011 00:24:51
Problema BMatrix Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 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) {
	long max = 0, co = 0, st[210];
	for (long j = l1; j <= l2; ++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];
			}			
		}
	}	
	return max;
}

void solveH() {
	for (long i = 2; i <= M; ++i) { 
		sol = 0;
		sol += part(1, i - 1);
		
		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) {
				v[h][I] -= v[i - 1][I];
				++h;
			}
		}
		
		sol += part(i, M);
		
		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;
}