Pagini recente » Cod sursa (job #877683) | Cod sursa (job #2301316) | Cod sursa (job #2192596) | Cod sursa (job #2807418) | Cod sursa (job #2139409)
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
const int nmax = 200;
int n, m;
int h[1 + nmax], st[1 + nmax], dr[1 + nmax];
stack <int> myStack;
int dp[2][5 + nmax];
char a[5 + nmax][5 + nmax];
int calulareDp(int lin, int init, int incr, int d) {
memset(h, 0, sizeof(h));
if(lin) {
h[0] = h[m + 1] = -1;
for(int i = init; 1 <= i && i <= n; i += incr) {
dp[d][i] = dp[d][i - incr];
for(int j = 1; j <= m; ++ j) {
if(a[i][j] == '0') {
h[j] ++;
} else {
h[j] = 0;
}
}
myStack.push(0);
for(int j = 1; j <= m; ++ j) {
while(h[j] <= h[myStack.top()]) {
myStack.pop();
}
st[j] = myStack.top() + 1;
myStack.push(j);
}
while(!myStack.empty())
myStack.pop();
myStack.push(m + 1);
for(int j = m; j >= 1; -- j) {
while(h[j] <= h[myStack.top()]) {
myStack.pop();
}
dr[j] = myStack.top() - 1;
myStack.push(j);
}
while(!myStack.empty())
myStack.pop();
for(int j = 1; j <= m; ++ j) {
int arie = h[j] * (dr[j] - st[j] + 1);
if(arie > dp[d][i]) {
dp[d][i] = arie;
}
}
}
} else {
h[0] = h[n + 1] = -1;
for(int j = init; 1 <= j && j <= m; j += incr) {
dp[d][j] = dp[d][j - incr];
for(int i = 1; i <= n; ++ i) {
if(a[i][j] == '0') {
h[i] ++;
} else {
h[i] = 0;
}
}
myStack.push(0);
for(int i = 1; i <= n; ++ i) {
while(h[i] <= h[myStack.top()]) {
myStack.pop();
}
st[i] = myStack.top() + 1;
myStack.push(i);
}
while(!myStack.empty())
myStack.pop();
myStack.push(n + 1);
for(int i = n; i >= 1; -- i) {
while(h[i] <= h[myStack.top()]) {
myStack.pop();
}
dr[i] = myStack.top() - 1;
myStack.push(i);
}
while(!myStack.empty())
myStack.pop();
for(int i = 1; i <= n; ++ i) {
int arie = h[i] * (dr[i] - st[i] + 1);
if(arie > dp[d][j]) {
dp[d][j] = arie;
}
}
}
}
}
int main() {
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
int maxim = 0;
scanf("%d%d\n", &n, &m);
for(int i = 1; i <= n; ++ i) {
gets(a[i] + 1);
}
calulareDp(1, 1, 1, 1);
calulareDp(1, n, -1, 2);
for(int i = 1; i <= n; ++ i) {
if(maxim < dp[1][i] + dp[2][i + 1]) {
maxim = dp[1][i] + dp[2][i + 1];
}
}
calulareDp(0, 1, 1, 1);
calulareDp(0, m, -1, 2);
for(int j = 1; j <= m; ++ j) {
if(maxim < dp[1][j] + dp[2][j + 1]) {
maxim = dp[1][j] + dp[2][j + 1];
}
}
printf("%d\n", maxim);
return 0;
}