Pagini recente » Cod sursa (job #2144637) | Cod sursa (job #1797271) | Cod sursa (job #959483) | Cod sursa (job #3255186) | Cod sursa (job #1788336)
#include <iostream>
#include <cstdio>
#define MAXN 210
using namespace std;
int n, m, a[MAXN][MAXN], aux[MAXN][MAXN];
int best[MAXN]; /// cel mai mare dreptunghi plin cu 0 care se termina pe linia i
int st[MAXN], val[MAXN], h[MAXN], rez;
char s[MAXN];
void read()
{
scanf("%d %d\n", &n, &m);
for (int i = 1; i <= n; i++) {
gets(s+1);
for (int j = 1; j <= m; j++)
a[i][j] = s[j]-'0';
}
}
void solve()
{
// for (int i = 1; i <= n; i++, cerr <<"\n")
// for (int j = 1; j <= m; j++)
// cerr << a[i][j] << " ";
for (int i = 1; i <= max(n, m); i++)
h[i] = val[i] = best[i] = 0;
for (int i = 1; i <= n; i++) {
st[st[0] = 1] = 0;
for (int j = 1; j <= m; j++) {
if (a[i][j] != 0) h[j] = 0;
else h[j]++;
while (st[0] > 1 && h[st[st[0]]] >= h[j])
st[0]--;
val[j] = st[st[0]];
st[++st[0]] = j;
}
st[st[0] = 1] = m+1;
for (int j = m; j >= 1; j--) {
while (st[0]>1 && h[st[st[0]]] >= h[j])
st[0]--;
int v = st[st[0]];
st[++st[0]] = j;
if (h[j]*(v-val[j]-1) > best[i])
best[i] = h[j]*(v-val[j]-1);
for (int k = 1; k <= h[j]; k++)
if (k*(v-val[j]-1) + best[i-k] > rez)
rez = k*(v-val[j]-1) + best[i-k];
}
}
}
int main()
{
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
read();
solve();
swap(n, m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
aux[i][j] = a[j][i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = aux[i][j];
solve();
printf("%d", rez);
return 0;
}