Pagini recente » Cod sursa (job #2938583) | Cod sursa (job #1557101) | Cod sursa (job #1280090) | Cod sursa (job #2541325) | Cod sursa (job #2200033)
#include <cstdio>
#include <algorithm>
using namespace std;
int a[205][205], b[205][205];
int sp[205], sus[205], st[205], l[205], r[205];
int solve1(int h[], int m) {
int top = 0;
st[top] = 0;
for (int j = 1; j <= m; ++j) {
while (top > 0 && h[j] <= h[st[top]])
top--;
l[j] = st[top];
st[++top] = j;
}
top = 0;
st[top] = m + 1;
for (int j = m; j >= 1; --j) {
while (top > 0 && h[j] <= h[st[top]])
top--;
r[j] = st[top];
st[++top] = j;
}
int ans = 0;
for (int j = 1; j <= m; ++j)
ans = max(ans, sp[j] * (r[j] - l[j] - 1));
return ans;
}
int solve(int x[205][205], int n, int m) {
for (int j = 1; j <= m; ++j)
sp[j] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
if (x[i][j] == 0)
sp[j]++;
else
sp[j] = 0;
sus[i] = max(sus[i - 1], solve1(sp, m));
}
int ans = 0;
for (int j = 1; j <= m; ++j)
sp[j] = 0;
int aux = 0;
for (int i = n; i >= 1; --i) {
for (int j = 1; j <= m; ++j)
if (x[i][j] == 0)
sp[j]++;
else
sp[j] = 0;
aux = max(aux, solve1(sp, m));
ans = max(ans, aux + sus[i - 1]);
}
return ans;
}
int main() {
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
scanf("%1d", &a[i][j]);
b[m - j + 1][i] = a[i][j];
}
printf("%d\n", max(solve(a, n, m), solve(b, m, n)));
return 0;
}