Pagini recente » Cod sursa (job #2028635) | Cod sursa (job #2844941) | Cod sursa (job #2332295) | Cod sursa (job #1254174) | Cod sursa (job #798072)
Cod sursa(job #798072)
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct bmatrix {
int x, y;
bmatrix() {
x = y = 0;
}
bmatrix(int x, int y) {
this->x = x;
this->y = y;
}
};
const int N = 205;
int n, m, head;
int a[N][N];
int up[N], left[N], up2[N], left2[N];
bmatrix stack[N];
char mat[N][N], mat2[N][N];
void read() {
assert(freopen("bmatrix.in", "r", stdin) != NULL);
assert(freopen("bmatrix.out", "w", stdout) != NULL);
assert(scanf("%d %d", &n, &m) == 2);
for (int i = 1; i <= n; ++i)
assert(scanf("%s", mat[i] + 1) == 1);
}
void zero() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (mat[i - 1][j] == '0')
a[i][j] = a[i - 1][j] + 1;
else
a[i][j] = 0;
}
}
int dr(int x) {
int maxSol = 0, left;
stack[head = 1] = bmatrix(a[x][1], 1);
for (int i = 2; i <= m; ++i) {
left = i;
while (head > 0 && stack[head].x >= a[x][i]) {
left = stack[head].y;
maxSol = max(maxSol, (i - stack[head].y) * stack[head].x);
--head;
}
stack[++head] = bmatrix(a[x][i], left);
}
while (head > 0) {
maxSol = max(maxSol, (m + 1 - stack[head].y) * stack[head].x);
--head;
}
return maxSol;
}
void preproc(int v[]) {
memset(v, 0, sizeof(v));
for (int i = 1; i <= n + 1; ++i)
v[i] = max(v[i - 1], dr(i));
}
void rotate() {
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
mat2[i][j] = mat[n - j + 1][i];
memcpy(mat, mat2, sizeof(mat2));
swap(n, m);
/*for (int i = 1; i <= n; ++i, printf("\n"))
for (int j = 1; j <= m; ++j)
printf("%c", mat[i][j]);
printf("\n");*/
}
int main() {
read();
zero();
preproc(up);
/*for (int i = 1; i <= n + 1; ++i)
printf("%d ", up[i]);
printf("\n");*/
rotate();
zero();
preproc(left);
/*for (int i = 1; i <= n; ++i)
printf("%d ", left[i]);
printf("\n");*/
rotate();
zero();
preproc(up2);
/*for (int i = 1; i <= n + 1; ++i)
printf("%d ", up2[i]);
printf("\n");*/
rotate();
zero();
preproc(left2);
//for (int i = 1; i <= n; ++i)
// printf("%d ", left2[i]);
int sol = 0;
for (int i = 1; i <= n + 1; ++i)
sol = max(sol, up[i] + up2[n - i]);
//printf("%d\n", sol);
for (int i = 1; i <= n + 1; ++i)
sol = max(sol, left[i] + left2[n - i]);
printf("%d\n", sol);
}