Pagini recente » Cod sursa (job #1486724) | Cod sursa (job #3299549) | Cod sursa (job #3305747) | Cod sursa (job #704180) | Cod sursa (job #3346667)
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define top() back()
#define pop() pop_back()
#define push(x) push_back(x)
char a[205][205];
int h[205];
int max_area_orizontal[205], max_area_vertical[205];
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifndef LOCAL
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
#endif
int m, n; cin >> m >> n;
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
cin >> a[i][j];
}
}
int last = 0;
for(int bara = 1; bara <= m; ++bara) {
for(int j = 1; j <= n; ++j) {
if(a[bara][j] == '0')
++h[j];
else h[j] = 0;
}
vector<pair<int, int>> bounds(n+1, {0, n+1});
vector<int> st;
for(int j = 1; j <= n; ++j) {
while(!st.empty() && h[j] <= h[st.top()])
st.pop();
if(!st.empty())
bounds[j].fi = st.top();
st.push(j);
}
st.clear();
for(int j = n; j >= 1; --j) {
while(!st.empty() && h[j] <= h[st.top()])
st.pop();
if(!st.empty())
bounds[j].se = st.top();
st.push(j);
}
int aMax = 0;
for(int j = 1; j <= n; ++j) {
int calcul = h[j] * (bounds[j].se - bounds[j].fi - 1);
aMax = max(aMax, calcul);
}
last = max(last, aMax);
max_area_orizontal[bara] += last;
}
memset(h, 0, sizeof(h));
last = 0;
for(int bara = m; bara > 1; --bara) {
for(int j = 1; j <= n; ++j) {
if(a[bara][j] == '0')
++h[j];
else h[j] = 0;
}
vector<pair<int, int>> bounds(n+1, {0, n+1});
vector<int> st;
for(int j = 1; j <= n; ++j) {
while(!st.empty() && h[j] <= h[st.top()])
st.pop();
if(!st.empty())
bounds[j].fi = st.top();
st.push(j);
}
st.clear();
for(int j = n; j >= 1; --j) {
while(!st.empty() && h[j] <= h[st.top()])
st.pop();
if(!st.empty())
bounds[j].se = st.top();
st.push(j);
}
int aMax = 0;
for(int j = 1; j <= n; ++j) {
int calcul = h[j] * (bounds[j].se - bounds[j].fi - 1);
aMax = max(aMax, calcul);
}
last = max(last, aMax);
max_area_orizontal[bara-1] += last;
}
memset(h, 0, sizeof(h));
last = 0;
for(int bara = 1; bara <= n; ++bara) {
for(int j = 1; j <= m; ++j) {
if(a[j][bara] == '0')
++h[j];
else h[j] = 0;
}
vector<pair<int, int>> bounds(m+1, {0, m+1});
vector<int> st;
for(int j = 1; j <= m; ++j) {
while(!st.empty() && h[j] <= h[st.top()])
st.pop();
if(!st.empty())
bounds[j].fi = st.top();
st.push(j);
}
st.clear();
for(int j = m; j >= 1; --j) {
while(!st.empty() && h[j] <= h[st.top()])
st.pop();
if(!st.empty())
bounds[j].se = st.top();
st.push(j);
}
int aMax = 0;
for(int j = 1; j <= m; ++j) {
int calcul = h[j] * (bounds[j].se - bounds[j].fi - 1);
aMax = max(aMax, calcul);
}
last = max(last, aMax);
max_area_vertical[bara] += last;
}
memset(h, 0, sizeof(h));
last = 0;
for(int bara = n; bara > 1; --bara) {
for(int j = 1; j <= m; ++j) {
if(a[j][bara] == '0')
++h[j];
else h[j] = 0;
}
vector<pair<int, int>> bounds(m+1, {0, m+1});
vector<int> st;
for(int j = 1; j <= m; ++j) {
while(!st.empty() && h[j] <= h[st.top()])
st.pop();
if(!st.empty())
bounds[j].fi = st.top();
st.push(j);
}
st.clear();
for(int j = m; j >= 1; --j) {
while(!st.empty() && h[j] <= h[st.top()])
st.pop();
if(!st.empty())
bounds[j].se = st.top();
st.push(j);
}
int aMax = 0;
for(int j = 1; j <= m; ++j) {
int calcul = h[j] * (bounds[j].se - bounds[j].fi - 1);
aMax = max(aMax, calcul);
}
last = max(last, aMax);
max_area_vertical[bara-1] += last;
}
int maxx = 0;
for(int i = 1; i <= m; ++i) {
maxx = max(maxx, max_area_orizontal[i]);
}
for(int i = 1; i <= n; ++i) {
maxx = max(maxx, max_area_vertical[i]);
}
cout << maxx;
return 0;
}