Pagini recente » Cod sursa (job #339249) | Cod sursa (job #1247850) | Cod sursa (job #1653722) | Cod sursa (job #750916) | Cod sursa (job #1961042)
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
char mat[204][204];
int dp[204][204];
int N, M;
int maxHist(int row[], int C) {
stack <int> result;
int top_val;
int max_area = 0;
int area = 0;
int i = 0;
while(i < C) {
if(result.empty() || row[result.top()] <= row[i]) {
result.push(i++);
}
else {
top_val = row[result.top()];
result.pop();
area = top_val * i;
if(!result.empty()) {
area = top_val * (i - result.top() - 1);
}
max_area = max(max_area, area);
}
}
while(!result.empty()) {
top_val = row[result.top()];
result.pop();
area = top_val * i;
if(!result.empty()) {
area = top_val * (i - result.top() - 1);
}
max_area = max(max_area, area);
}
return max_area;
}
int calculate(int a, int b, int c, int d) {
int line[204];
int result = 0;
for(int i = a; i <= c; ++i) {
int pos = 0;
for(int j = b; j <= d; ++j) {
line[pos++] = min(i - a + 1, dp[i][j]);
}
line[pos] = 0;
result = max(result, maxHist(line, d - b + 1));
}
return result;
}
int main() {
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
scanf("%d %d\n", &N, &M);
for(int i = 1; i <= N; ++i) {
scanf("%s", (mat[i] + 1));
}
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= M; ++j) {
if(mat[i][j] == '0') {
dp[i][j] = dp[i - 1][j] + 1;
}
}
}
int ans = calculate(1, 1, N, M);
for(int colbetween = 1; colbetween < M; ++colbetween) {
ans = max(ans, calculate(1, 1, N, colbetween) + calculate(1, colbetween + 1, N, M));
}
for(int linebetween = 1; linebetween < N; ++linebetween) {
ans = max(ans, calculate(1, 1, linebetween, M) + calculate(linebetween + 1, 1, N, M));
}
cout << ans << '\n';
return 0;
}