Pagini recente » Cod sursa (job #573270) | Cod sursa (job #270578) | Cod sursa (job #163202) | Cod sursa (job #625208)
Cod sursa(job #625208)
#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;
}