Pagini recente » Cod sursa (job #1479598) | Cod sursa (job #1054573) | Cod sursa (job #1311371) | Cod sursa (job #2171228) | Cod sursa (job #2741139)
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << "\n";
using ll = long long;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int maxN = (int)3e2 + 5;
int n, m;
char mat[maxN][maxN];
int hist[maxN];
int upMax[maxN], lowMax[maxN], rightMax[maxN], leftMax[maxN];
int solveHistogram(int len) {
int ans = 0;
stack<int> st;
hist[len + 1] = hist[0] = 0;
st.push(0);
for (int i = 1; i <= len + 1; i++) {
while ((int)st.size() > 0 && hist[st.top()] > hist[i]) {
int top = st.top();
st.pop();
ans = max(ans, hist[top] * (i - st.top() - 1));
}
st.push(i);
}
return ans;
}
int main() {
in >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
in >> mat[i][j];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mat[i][j] == '0') {
hist[j]++;
} else {
hist[j] = 0;
}
}
upMax[i] = solveHistogram(m);
}
for (int i = 0; i <= m + 1; i++) {
hist[i] = 0;
}
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= m; j++) {
if (mat[i][j] == '0') {
hist[j]++;
} else {
hist[j] = 0;
}
}
lowMax[i] = solveHistogram(m);
}
for (int i = 0; i <= m + 1; i++) {
hist[i] = 0;
}
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) {
if (mat[i][j] == '0') {
hist[i]++;
} else {
hist[i] = 0;
}
}
leftMax[j] = solveHistogram(n);
}
for (int i = 0; i <= n + 1; i++) {
hist[i] = 0;
}
for (int j = m; j >= 1; j--) {
for (int i = 1; i <= n; i++) {
if (mat[i][j] == '0') {
hist[i]++;
} else {
hist[i] = 0;
}
}
rightMax[j] = solveHistogram(n);
}
for (int i = 1; i < n; i++) {
ans = max(ans, upMax[i] + lowMax[i + 1]);
}
for (int i = 1; i < m; i++) {
ans = max(ans, leftMax[i] + rightMax[i + 1]);
}
out << ans << "\n";
return 0;
}