Pagini recente » Cod sursa (job #2947545) | Cod sursa (job #1369376) | Cod sursa (job #2880618) | Cod sursa (job #2851917) | Cod sursa (job #1961433)
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
#define DIM 204
char mat[DIM][DIM];
int fromUpToDown[DIM][DIM], fromDownToUp[DIM][DIM], fromLeftToRight[DIM][DIM], fromRightToLeft[DIM][DIM];
int ansUpDown[DIM], ansDownUp[DIM], ansRightLeft[DIM], ansLeftRight[DIM];
int N, M, row[DIM], pos;
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 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));
}
int ans = 0;
int result = 0;
for(int i = 1; i <= N; ++i) {
pos = 0;
for(int j = 1; j <= M; ++j) {
if(mat[i][j] == '0') {
fromUpToDown[i][j] = fromUpToDown[i - 1][j] + 1;
}
row[pos++] = fromUpToDown[i][j];
}
result = max(result, maxHist(row, M));
ansUpDown[i] = result;
}
result = 0;
for(int i = N; i > 0; --i) {
pos = 0;
for(int j = 1; j <= M; ++j) {
if(mat[i][j] == '0') {
fromDownToUp[i][j] = fromDownToUp[i + 1][j] + 1;
}
row[pos++] = fromDownToUp[i][j];
}
result = max(result, maxHist(row, M));
ansDownUp[i] = result;
ans = max(ans, ansUpDown[i] + ansDownUp[i + 1]);
}
result = 0;
for(int j = 1; j <= M; ++j) {
int pos = 0;
for(int i = 1; i <= N; ++i) {
if(mat[i][j] == '0') {
fromLeftToRight[i][j] = fromLeftToRight[i][j - 1] + 1;
}
row[pos++] = fromLeftToRight[i][j];
}
result = max(result, maxHist(row, N));
ansLeftRight[j] = result;
}
result = 0;
for(int j = M; j > 0; --j) {
pos = 0;
for(int i = 1; i <= N; ++i) {
if(mat[i][j] == '0') {
fromRightToLeft[i][j] = fromRightToLeft[i][j + 1] + 1;
}
row[pos++] = fromRightToLeft[i][j];
}
result = max(result, maxHist(row, N));
ansRightLeft[j] = result;
ans = max(ans, ansLeftRight[j] + ansRightLeft[j + 1]);
}
cout << ans << '\n';
return 0;
}