Pagini recente » Cod sursa (job #2424201) | Cod sursa (job #2581408) | Cod sursa (job #604381) | Cod sursa (job #920406) | Cod sursa (job #1823022)
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
using namespace std;
const string name = "bmatrix",
in_file = name + ".in",
out_file = name + ".out";
ifstream fin(in_file);
ofstream fout(out_file);
const int MAX = 201;
int n, m;
int matrix[MAX][MAX];
int heights[MAX][MAX];
vector<int> stackk;
int lefty[MAX], righty[MAX];
int dp[MAX][MAX];
void build_heights(int x1, int y1, int x2, int y2) {
memset(heights, 0, sizeof(heights));
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
if (matrix[i][j]) {
heights[i][j] = 0;
} else {
heights[i][j] = heights[i - 1][j] + 1;
}
}
}
}
int go(int x1, int y1, int x2, int y2) {
build_heights(x1, y1, x2, y2);
int maxx = 0;
for (int i = x1; i <= x2; i++) {
stackk.clear();
for (int j = y1; j <= y2; j++) {
int height = heights[i][j];
if (!height) {
lefty[j] = 0;
stackk.clear();
continue;
}
while (!stackk.empty() && heights[i][stackk.back()] > height) {
stackk.pop_back();
}
if (stackk.empty() || heights[i][stackk.back()] < height) {
stackk.push_back(j);
lefty[j] = j;
} else {
lefty[j] = stackk.back();
}
}
stackk.clear();
for (int j = y2; j > 0; j--) {
int height = heights[i][j];
if (!height) {
righty[j] = 0;
stackk.clear();
continue;
}
while (!stackk.empty() && heights[i][stackk.back()] > height) {
stackk.pop_back();
}
if (stackk.empty() || heights[i][stackk.back()] < height) {
stackk.push_back(j);
righty[j] = j;
} else {
righty[j] = stackk.back();
}
}
for (int j = y1; j <= y2; j++) {
dp[i][j] = heights[i][j] * (righty[j] - lefty[j] + 1);
maxx = max(dp[i][j], maxx);
}
}
return maxx;
}
int main() {
fin >> n >> m;
string str;
for (int i = 1; i <= n; i++) {
fin >> str;
for (int j = 1; j <= m; j++) {
matrix[i][j] = str[j - 1] - '0';
}
}
int result = 0;
for (int line = 1; line < n; line++) {
int topLeftSecond = line + 1, bottomRightFirst = line;
result = max(result, go(1, 1, bottomRightFirst, m) +
go (topLeftSecond, 1, n, m));
}
for (int line = 1; line < m; line++) {
int bottomRightFirst = line, topLeftSecond = line + 1;
result = max(result, go(1, 1, n, bottomRightFirst) +
go (1, topLeftSecond, n, m));
}
fout << result;
return 0;
}