Pagini recente » Cod sursa (job #2516255) | Cod sursa (job #2748959) | Cod sursa (job #2557720) | Cod sursa (job #2441300) | Cod sursa (job #1459786)
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int N = 202;
int a [N][N], dp [N][N], st [N], dr [N], b [N][N];
char ch [N];
int n, m, ans1 [N], ans2 [N], ans3 [N], ans4 [N];
stack <pair <int, int> > s;
void solve (int ans []) {
int i, j;
for (j = 1; j <= m; j ++)
dp [1][j] = 1 - a [1][j];
for (i = 1; i <= n; i ++)
for (j = 1; j <= m; j ++)
if (a [i][j] == 0)
dp [i][j] = dp [i - 1][j] + 1;
else dp [i][j] = 0;
for (i = 1; i <= n; i ++) {
ans [i] = 0;
while (!s.empty ())
s.pop ();
for (j = 1; j <= m; j ++) {
while (!s.empty () && s.top ().first >= dp [i][j])
s.pop ();
if (s.empty ())
st [j] = 1;
else
st [j] = s.top ().second + 1;
s.push (make_pair (dp [i][j], j));
}
while (!s.empty ())
s.pop ();
for (j = m; j >= 1; j --) {
while (!s.empty () && s.top ().first >= dp [i][j])
s.pop ();
if (s.empty ())
dr [j] = m;
else
dr [j] = s.top ().second - 1;
s.push (make_pair (dp [i][j], j));
}
for (j = 1; j <= m; j ++)
if (st [j] <= dr [j] && a [i][j] == 0)
ans [i] = max (ans [i], dp [i][j] * (dr [j] - st [j] + 1));
ans [i] = max (ans [i], ans [i - 1]);
}
}
void rotatie () {
int i, j, aux;
for (i = 1; i <= m; i ++)
for (j = 1; j <= n; j ++)
b [i][j] = a [n - j + 1][i];
aux = m;
m = n;
n = aux;
memcpy (a, b, sizeof (a));
}
int main () {
int i, j, sol = 0, aux;
freopen ("bmatrix.in", "r", stdin);
freopen ("bmatrix.out", "w", stdout);
scanf ("%d%d\n", &n, &m);
for (i = 1; i <= n; i ++) {
scanf ("%s", ch);
for (j = 0; j < m; j ++)
a [i][j + 1] = ch [j] - '0';
}
solve (ans1);
rotatie ();
solve (ans3);
rotatie ();
solve (ans2);
rotatie();
solve (ans4);
aux = n;
n = m;
m = aux;
for (i = 1; i < n; i ++) {
sol = max (sol, ans1 [i] + ans2 [n - i]);
}
for (i = 1; i < m; i ++) {
sol = max (sol, ans3 [i] + ans4 [m - i]);
}
printf ("%d\n", sol);
return 0;
}