Pagini recente » Cod sursa (job #494981) | Cod sursa (job #3172434) | Cod sursa (job #2897307) | Cod sursa (job #2606231) | Cod sursa (job #2923756)
//
// Created by mihai145 on 18.09.2022.
//
#include <fstream>
#include <vector>
#include <string>
#include <stack>
using namespace std;
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
int max_area_histogram(const vector<int>& h) {
int max_area = 0;
stack<int> stk;
auto update_max_area = [&](int i) {
int width, height = h[stk.top()];
stk.pop();
if(stk.empty()) {
width = i;
} else {
width = i - 1 - stk.top();
}
max_area = max(max_area, width * height);
};
for(int i = 0; i < (int)h.size(); i++) {
while(!stk.empty() && h[stk.top()] >= h[i]) {
update_max_area(i);
}
stk.push(i);
}
while(!stk.empty()) {
update_max_area((int)h.size());
}
return max_area;
}
int calculate_ans(const vector<string>& mat) {
int n = (int)mat.size(), m = (int)mat[0].size();
int ans = 0;
vector<int> dp_up(n, 0), dp_down(n, 0);
vector<int> h(m, 0);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(mat[i][j] == '1') {
h[j] = 0;
} else {
h[j]++;
}
}
int mx = max_area_histogram(h);
dp_up[i] = (i >= 1) ? max(dp_up[i - 1], mx) : mx;
}
for(int i = 0; i < m; i++) {
h[i] = 0;
}
for(int i = n - 1; i >= 0; i--) {
for(int j = 0; j < m; j++) {
if(mat[i][j] == '1') {
h[j] = 0;
} else {
h[j]++;
}
}
int mx = max_area_histogram(h);
dp_down[i] = (i < n - 1) ? max(dp_down[i + 1], mx) : mx;
}
ans = dp_up[n - 1];
for(int i = 0; i < n - 1; i++) {
ans = max(ans, dp_up[i] + dp_down[i + 1]);
}
return ans;
}
int main() {
int n, m, ans = 0;
cin >> n >> m;
vector<string> mat(n);
for(int i = 0; i < n; i++) {
cin >> mat[i];
}
ans = calculate_ans(mat);
vector<string> mat2(m);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
mat2[i] += mat[j][i];
}
}
ans = max(ans, calculate_ans(mat2));
cout << ans << '\n';
return 0;
}