Pagini recente » Cod sursa (job #966747) | Cod sursa (job #1592643)
#include <bits/stdc++.h>
#define maxN 202
using namespace std;
int n, m, s[maxN][maxN], rs[maxN][maxN], dp, top, sol, maxA[maxN];
char a[maxN][maxN], cp[maxN][maxN];
struct st
{
int h, p;
} st[maxN];
void read()
{
int i;
freopen("bmatrix.in", "r", stdin);
scanf("%d %d\n", &n, &m);
for (i = 1; i <= n; ++ i)
gets(a[i] + 1);
}
void partial_sums()
{
int i, j;
for (i = 1; i <= n; ++ i)
for (j = 1; j <= m; ++ j)
if (a[i][j] == '0')
s[i][j] = s[i - 1][j] + 1;
for (i = n; i >= 1; -- i)
for (j = 1; j <= m; ++ j)
if (a[i][j] == '0')
rs[i][j] = rs[i + 1][j] + 1;
}
void get_maxA()
{
int i, j, p, A;
for (i = n; i >= 1; -- i)
{
maxA[i] = maxA[i + 1];
top = 0;
for (j = 1; j <= m + 1; ++ j)
{
p = j;
if (rs[i][j] > st[top].h)
{
st[++ top].p = j;
st[top].h = rs[i][j];
}
else
{
while (st[top].h > rs[i][j])
{
A = st[top].h * (j - st[top].p);
p = min(p, st[top].p);
if (A > maxA[i])
maxA[i] = A;
-- top;
}
if (rs[i][j] > 0)
{
st[++ top].h = rs[i][j];
st[top].p = p;
}
}
}
}
}
void get_sol()
{
int i, j, a, p, A;
top = 0;
a = 0;
if (sol < maxA[1])
sol = maxA[1];
for (i = 1; i <= n; ++ i)
{
for (j = 1; j <= m + 1; ++ j)
{
p = j;
if (s[i][j] > st[top].h)
{
st[++ top].p = j;
st[top].h = s[i][j];
}
else
{
while (st[top].h > s[i][j])
{
A = st[top].h * (j - st[top].p);
p = min(p, st[top].p);
if (A > a)
a = A;
-- top;
}
if (s[i][j] > 0)
{
st[++ top].h = s[i][j];
st[top].p = p;
}
}
}
if (a + maxA[i + 1] > sol)
sol = a + maxA[i + 1];
}
}
void solve()
{
partial_sums();
get_maxA();
get_sol();
}
void rotate_mat()
{
int i, j;
memcpy(cp, a, sizeof(a));
swap(n, m);
for (i = 1; i <= n; ++ i)
for (j = 1; j <= m; ++ j)
a[i][j] = cp[m - j + 1][i];
}
void write()
{
freopen("bmatrix.out", "w", stdout);
printf("%d", sol);
}
int main()
{
read();
solve();
rotate_mat();
memset(s, 0, sizeof(s));
memset(rs, 0, sizeof(rs));
memset(maxA, 0, sizeof(maxA));
solve();
write();
return 0;
}