Pagini recente » Cod sursa (job #3238570) | Cod sursa (job #2031194) | Cod sursa (job #1688587) | Cod sursa (job #45723) | Cod sursa (job #2990646)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int kN = 200;
string a[1 + kN];
int v[1 + kN], up[1 + kN], down[1 + kN + 1], st[1 + kN], dr[1 + kN + 1], stk[1 + kN], nextLeft[1 + kN], nextRight[1 + kN];
void maxSelf(int &x, int y) {
if (x < y) {
x = y;
}
}
int solve(int n) {
for (int i = 1; i <= n; ++i) {
nextLeft[i] = 0;
nextRight[i] = n + 1;
}
int vf = 0;
for (int i = 1; i <= n; ++i) {
while (vf && v[i] < v[stk[vf]]) {
nextRight[stk[vf]] = i;
vf -= 1;
}
stk[++vf] = i;
}
vf = 0;
for (int i = n; i > 0; --i) {
while (vf && v[i] < v[stk[vf]]) {
nextLeft[stk[vf]] = i;
vf -= 1;
}
stk[++vf] = i;
}
int best = 0;
for (int i = 1; i <= n; ++i) {
maxSelf(best, v[i] * (nextRight[i] - nextLeft[i] - 1));
}
return best;
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= n; ++i) {
fin >> a[i];
a[i] = '$' + a[i];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] == '0') {
v[j] += 1;
} else {
v[j] = 0;
}
}
up[i] = max(up[i - 1], solve(m));
}
for (int i = 1; i <= m; ++i) {
v[i] = 0;
}
for (int i = n; i > 0; --i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] == '0') {
v[j] += 1;
} else {
v[j] = 0;
}
}
down[i] = max(down[i + 1], solve(m));
}
for (int i = 1; i <= n; ++i) {
v[i] = 0;
}
for (int j = 1; j <= m; ++j) {
for (int i = 1; i <= n; ++i) {
if (a[i][j] == '0') {
v[i] += 1;
} else {
v[i] = 0;
}
}
st[j] = max(st[j - 1], solve(n));
}
for (int i = 1; i <= n; ++i) {
v[i] = 0;
}
for (int j = m; j > 0; --j) {
for (int i = 1; i <= n; ++i) {
if (a[i][j] == '0') {
v[i] += 1;
} else {
v[i] = 0;
}
}
dr[j] = max(dr[j + 1], solve(n));
}
int best = 0;
for (int i = 0; i <= n; ++i) {
maxSelf(best, up[i] + down[i + 1]);
}
for (int i = 0; i <= m; ++i) {
maxSelf(best, st[i] + dr[i + 1]);
}
fout << best << '\n';
fin.close();
fout.close();
return 0;
}