Cod sursa(job #328739)

Utilizator CezarMocanCezar Mocan CezarMocan Data 3 iulie 2009 11:41:16
Problema BMatrix Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#define maxn 202

using namespace std;

int n, m, i, j, k, nr, size, pp;
int v[maxn][maxn], sum[maxn][maxn];
int l1[maxn], l2[maxn], c1[maxn], c2[maxn];
char s[maxn];

inline int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

int main() {
	freopen("bmatrix.in", "r", stdin);
	freopen("bmatrix.out", "w", stdout);

	scanf("%d%d ", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf(" %s ", s);
		for (j = 0; j < m; j++)
			v[i][j + 1] = s[j] - 48;
	}

	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			sum[i][j] = sum[i - 1][j] + v[i][j];

	for (i = 1; i <= n; i++)
		for (j = i; j <= n; j++) {
			nr = 0; pp = (j - i + 1);
			for (k = 1; k <= m; k++) {
				if (sum[i - 1][k] == sum[j][k]) {
					size += pp;
					l1[j] = max(l1[j], size);
					l2[i] = max(l2[i], size);
					c1[k] = max(c1[k], size);	
				}
				else
					size = 0;
			}

			nr = 0;
			for (k = m; k >= 1; k--) {
				if (sum[i - 1][k] == sum[j][k]) {
					size += pp;
					c2[k] = max(c2[k], size);
				}
				else
					size = 0;
			}
		}

	for (i = 1; i <= n; i++)
		l1[i] = max(l1[i - 1], l1[i]);
	for (i = 1; i <= m; i++)
		c1[i] = max(c1[i - 1], c1[i]);
	for (i = n; i >= 1; i--)
		l2[i] = max(l2[i], l2[i + 1]);
	for (j = m; j >= 1; j--)
		c2[j] = max(c2[j], c2[j + 1]);

	int rez = 0;
	for (i = 1; i <= n; i++)
		rez = max(rez, l1[i] + l2[i + 1]);
	for (j = 1; j <= m; j++)
		rez = max(rez, c1[j] + c2[j + 1]);

	printf("%d\n", rez);

	return 0;
}