Pagini recente » Borderou de evaluare (job #241565) | Borderou de evaluare (job #2279085) | Borderou de evaluare (job #321750) | Borderou de evaluare (job #1932012) | Cod sursa (job #1926930)
#include <bits/stdc++.h>
#define NMAX 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
char a[NMAX][NMAX], aux[NMAX][NMAX];
int N, M, limit, sol;
void rotateMatrix() {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
aux[i][j] = a[j][i];
}
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
a[i][j] = aux[i][j];
}
}
}
int getMaxArea(int start, int stop) {
vector < int > st;
int zeros[NMAX], area = 0;
memset(zeros, 0, sizeof(zeros));
for (int i = start; i <= stop; ++i) {
st.clear();
for (int j = 1; j <= M + 1; ++j) {
if (a[i][j] == '0') {
++zeros[j];
} else {
zeros[j] = 0;
}
if (j == M + 1) {
zeros[j] = 0;
}
int top = 0;
if (st.size()) {
top = st.back();
}
while (st.size() && zeros[st.back()] > zeros[j]) {
area = max(area, zeros[st.back()] * (top - st[st.size() - 2]));
st.pop_back();
}
st.push_back(j);
}
}
return area;
}
int main() {
f >> N >> M;
for (int i = 1; i <= N; ++i) {
f >> (a[i] + 1);
}
limit = N >> 1;
for (int i = 1; i <= limit; ++i) {
sol = max(sol, getMaxArea(1, i) + getMaxArea(i + 1, N));
}
swap(N, M);
rotateMatrix();
limit = N >> 1;
for (int i = 1; i <= limit; ++i) {
sol = max(sol, getMaxArea(1, i) + getMaxArea(i + 1, N));
}
g << sol << '\n';
return 0;
}