Pagini recente » Cod sursa (job #1851227) | Cod sursa (job #2666000) | Cod sursa (job #1564459) | Cod sursa (job #1248017) | Cod sursa (job #2709608)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
const int N = 201;
int n, m, h[N][N], st[N], dr[N];
bool a[N][N], mat[N][N];
int area, maxArea;
int lin, col;
stack <int> s;
void Read()
{
fin >> n >> m;
char s[N];
for (int i = 1; i <= n; i++)
{
fin >> s;
for (int j = 1; j <= m; j++)
a[i][j] = s[j - 1] - '0';
}
}
int largestArea()
{
int candArea = 0;
for (int i = 1; i <= lin; i++)
for (int j = 1; j <= col; j++)
h[i][j] = (mat[i][j] ? 0 : h[i - 1][j] + 1);
for (int i = 1; i <= lin; i++)
{
///calculez dr[]
for (int j = 1; j <= col; j++)
{
if (s.empty())
s.push(j);
else
{
int top = s.top();
if (h[i][j] < h[i][top])
{
while (h[i][j] < h[i][top])
{
dr[top] = j;
s.pop();
if (s.empty())
break;
top = s.top();
}
}
s.push(j);
}
}
while (!s.empty())
{
dr[s.top()] = col + 1;
s.pop();
}
///calculez st[]
for (int j = col; j >= 1; j--)
{
if (s.empty())
s.push(j);
else
{
int top = s.top();
if (h[i][j] < h[i][top])
{
while (h[i][j] < h[i][top])
{
st[top] = j;
s.pop();
if (s.empty())
break;
top = s.top();
}
}
s.push(j);
}
}
while (!s.empty())
{
st[s.top()] = 0;
s.pop();
}
///calculez aria
for (int j = 1; j <= col; j++)
candArea = max(candArea, h[i][j] * (dr[j] - st[j] - 1));
}
return candArea;
}
void Solve()
{
for (int lim = 1; lim < n; lim++)
{
for (int i = 1; i <= lim; i++)
for (int j = 1; j <= m; j++)
mat[i][j] = a[i][j];
lin = lim; col = m;
area = largestArea();
for (int i = lim + 1; i <= n; i++)
for (int j = 1; j <= m; j++)
mat[i - lim][j] = a[i][j];
lin = n - lim; col = m;
area += largestArea();
maxArea = max(area, maxArea);
}
for (int lim = 1; lim < m; lim++)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= lim; j++)
mat[i][j] = a[i][j];
lin = n; col = lim;
area = largestArea();
for (int i = 1; i <= n; i++)
for (int j = lim + 1; j <= m; j++)
mat[i][j - lim] = a[i][j];
lin = n; col = m - lim;
area += largestArea();
maxArea = max(area, maxArea);
}
}
int main()
{
Read();
Solve();
fout << maxArea;
return 0;
}