Pagini recente » Cod sursa (job #738840) | Cod sursa (job #2304791) | Cod sursa (job #2103284) | Cod sursa (job #738739) | Cod sursa (job #1532895)
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 200;
char a[kMaxN][kMaxN + 1];
char aux[kMaxN][kMaxN];
int st[kMaxN], ss;
int h[kMaxN + 1];
int lineDown[kMaxN], lineUp[kMaxN];
int columnDown[kMaxN], columnUp[kMaxN];
void histogramSolver(int n, int m, int d[]) {
int q;
for (int i = 0; i < n; i++) {
q = 0;
ss = 0;
for (int j = 0; j <= m; j++) {
if (j != m) {
h[j] = (h[j] + 1) & -(a[i][j] == '0');
} else {
h[j] = 0;
}
while ((ss > 0) && (h[st[ss - 1]] > h[j])) {
ss--;
q = max(q, h[st[ss]] * (ss ? j - st[ss - 1] - 1 : j));
}
st[ss++] = j;
}
d[i] = (i == 0) ? q : max(d[i - 1], q);
}
for (int i = 0; i < m; i++) {
h[i] = 0;
}
}
void rotate90Degrees(int &n, int &m) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
aux[i][j] = a[n - j - 1][i];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = aux[i][j];
}
}
swap(n, m);
}
int main(void) {
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
int n, m, q;
in >> n >> m;
for (int i = 0; i < n; i++) {
in >> a[i];
}
in.close();
histogramSolver(n, m, lineUp);
rotate90Degrees(n, m);
histogramSolver(n, m, columnUp);
rotate90Degrees(n, m);
histogramSolver(n, m, lineDown);
reverse(lineDown, lineDown + n);
rotate90Degrees(n, m);
histogramSolver(n, m, columnDown);
reverse(columnDown, columnDown + n);
q = 0;
for (int i = 1; i < m; i++) {
q = max(lineUp[i - 1] + lineDown[i], q);
}
for (int i = 1; i < n; i++) {
q = max(columnUp[i - 1] + columnDown[i], q);
}
out << q << '\n';
out.close();
return 0;
}