Mai intai trebuie sa te autentifici.
Cod sursa(job #328737)
Utilizator | Data | 3 iulie 2009 11:36:56 | |
---|---|---|---|
Problema | BMatrix | Scor | 60 |
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; int pp = (j - i + 1);
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 = pp * 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 = pp * 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;
}