Pagini recente » Cod sursa (job #944593) | Cod sursa (job #1915055) | Cod sursa (job #2566174) | Cod sursa (job #2710990) | Cod sursa (job #2345093)
#include <bits/stdc++.h>
#define int_pair std::pair <int, int>
#define MAXN 205
int N, M;
int Height[MAXN], DP[4][MAXN];
bool BMatrix[MAXN][MAXN];
bool Rotator[MAXN][MAXN];
void Rotate90() {
for (int i=1, j; i<=N; ++i)
for (j=1; j<=M; ++j)
Rotator[j][N-i+1] = BMatrix[i][j];
std::swap(N, M);
for (int i=1, j; i<=N; ++i)
for (j=1; j<=M; ++j)
BMatrix[i][j] = Rotator[i][j];
}
std::ifstream In ("bmatrix.in");
std::ofstream Out("bmatrix.out");
void Citire() {
In >> N >> M;
char ch;
for (int i=1, j ; i<=N; ++i)
for (j=1; j<=M; ++j)
In >> ch, BMatrix[i][j] = ch - '0';
}
std::stack <int_pair> Stack;
void Rezolvare() {
for (int step=0, i, j, count; step<4; ++step, Rotate90()) {
for (j=1; j<=M; ++j)
Height[j] = 0;
for (i=1; i<=N; ++i) {
DP[step][i] = DP[step][i-1];
while (!Stack.empty()) Stack.pop();
for (j=1; j<=M; ++j) {
if (!BMatrix[i][j]) Height[j] ++;
else Height[j] = 0;
count = 0;
while (!Stack.empty() && Height[j] <= Stack.top().first) {
count += Stack.top().second;
DP[step][i] = std::max(DP[step][i], count * Stack.top().first);
Stack.pop();
} Stack.push({Height[j], count+1});
}
count = 0;
while (!Stack.empty()) {
count += Stack.top().second;
DP[step][i] = std::max(DP[step][i], count * Stack.top().first);
Stack.pop();
}
}
}
int Ans = 0;
for (int i=1; i<N; ++i)
Ans = std::max(Ans, DP[0][i] + DP[2][N-i]);
for (int i=1; i<M; ++i)
Ans = std::max(Ans, DP[1][i] + DP[3][M-i]);
Out << Ans << '\n';
}
int main()
{
Citire();
Rezolvare();
return 0;
}