Pagini recente » Cod sursa (job #2487413) | Cod sursa (job #1087587) | Cod sursa (job #2425468) | Cod sursa (job #584689) | Cod sursa (job #2630121)
#include <bits/stdc++.h>
#define maxn 205
std::ifstream fin ("bmatrix.in");
std::ofstream fout ("bmatrix.out");
bool a[maxn][maxn];
int upRow[maxn], downRow[maxn], leftCol[maxn], rightCol[maxn];
int h[maxn];
std::stack <int> stack;
int main()
{
int n, m, i, j, max=0, index, height;
char chr;
fin >> n >> m;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++){
fin >> chr;
a[i][j] = chr - '0';
}
/// Up Row
memset (h, 0, sizeof h);
for (i=1; i<=n; i++){
for (j=1; j<=m; j++){
if (a[i][j] == 0)
h[j] ++;
else h[j] = 0;
}
while (stack.empty() == false)
stack.pop();
h[0] = -1;
h[m+1] = -1;
stack.push (0);
max = 0;
for (j=1; j<=m+1; j++){
//std::cout << stack.top() << '\n';
while (stack.empty() == false and h[stack.top()] >= h[j]){
height = h[stack.top()];
stack.pop();
if (stack.empty() == false)
max = std::max (max, height * (j-stack.top()-1));
}
stack.push (j);
}
upRow[i] = std::max(max, upRow[i-1]);
//fout << upRow[i] << '\n';
}
/// Down Row
memset (h, 0, sizeof h);
for (i=n; i>0; i--){
for (j=1; j<=m; j++){
if (a[i][j] == 0)
h[j] ++;
else h[j] = 0;
}
while (stack.empty() == false)
stack.pop();
h[0] = -1;
h[m+1] = -1;
stack.push (0);
max = 0;
for (j=1; j<=m+1; j++){
//std::cout << stack.top() << '\n';
while (stack.empty() == false and h[stack.top()] >= h[j]){
height = h[stack.top()];
stack.pop();
if (stack.empty() == false)
max = std::max (max, height * (j-stack.top()-1));
}
stack.push (j);
}
downRow[i] = std::max(max, downRow[i+1]);
//fout << downRow[i] << '\n';
}
///Left Column
memset (h, 0, sizeof h);
for (j=1; j<=m; j++){
for (i=1; i<=n; i++){
if (a[i][j] == 0)
h[i] ++;
else h[i] = 0;
}
while (stack.empty() == false)
stack.pop();
h[0] = -1;
h[n+1] = -1;
stack.push (0);
max = 0;
for (i=1; i<=n+1; i++){
//std::cout << stack.top() << '\n';
while (stack.empty() == false and h[stack.top()] >= h[i]){
height = h[stack.top()];
stack.pop();
if (stack.empty() == false)
max = std::max (max, height * (i-stack.top()-1));
}
stack.push (i);
}
leftCol[j] = std::max(max, leftCol[j-1]);
//fout << leftCol[j] << '\n';
}
///Right Column
memset (h, 0, sizeof h);
for (j=m; j>0; j--){
for (i=1; i<=n; i++){
if (a[i][j] == 0)
h[i] ++;
else h[i] = 0;
}
while (stack.empty() == false)
stack.pop();
h[0] = -1;
h[n+1] = -1;
stack.push (0);
max = 0;
for (i=1; i<=n+1; i++){
//std::cout << stack.top() << '\n';
while (stack.empty() == false and h[stack.top()] >= h[i]){
height = h[stack.top()];
stack.pop();
if (stack.empty() == false)
max = std::max (max, height * (i-stack.top()-1));
}
stack.push (i);
}
rightCol[j] = std::max(max, rightCol[j+1]);
//fout << rightCol[j] << '\n';
}
max = 0;
for (i=1; i<n; i++)
max = std::max (max, upRow[i] + downRow[i+1]);
for (i=1; i<m; i++)
max = std::max (max, leftCol[i] + rightCol[i+1]);
fout << max << '\n';
return 0;
}