Cod sursa(job #328372)

Utilizator CezarMocanCezar Mocan CezarMocan Data 1 iulie 2009 20:15:47
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#define maxn 202

using namespace std;

int n, m, i, j, k, nr, size;
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;
			for (k = 1; k <= m; k++) {
				if (sum[i - 1][k] == sum[j][k])
					nr++;
				else
					nr = 0;
//				fprintf(stderr, "%d %d  %d  %d\n", i, j, k, nr);
				size = (j - i + 1) * nr;
				l1[j] = max(l1[j], size);
				l2[i] = max(l2[i], size);
				c1[k] = max(c1[k], size);
			}

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

	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;
}