Pagini recente » Cod sursa (job #1374008) | Cod sursa (job #1926502) | Cod sursa (job #1747235) | Cod sursa (job #2089939) | Cod sursa (job #2709620)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
const int N = 205;
int n, m, h[N][N], up[N], down[N], dr[N], st[N];
bool a[N][N];
int maxArea;
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';
}
}
void Rotate()
{
int b[N][N];
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n; i++)
b[j][i] = a[i][j];
swap(n, m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = b[i][j];
}
void Solve()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
h[i][j] = (a[i][j] ? 0 : h[i - 1][j] + 1);
for (int i = 1; i <= n; i++)
{
up[i] = up[i - 1];
///calculez dr[]
for (int j = 1; j <= m; 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()] = m + 1;
s.pop();
}
///calculez st[]
for (int j = m; 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 <= m; j++)
up[i] = max(up[i], h[i][j] * (dr[j] - st[j] - 1));
}
for (int i = n; i >= 1; i--)
for (int j = 1; j <= m; j++)
h[i][j] = (a[i][j] ? 0 : h[i + 1][j] + 1);
for (int i = n; i >= 1; i--)
{
down[i] = down[i + 1];
///calculez dr[]
for (int j = 1; j <= m; 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()] = m + 1;
s.pop();
}
///calculez st[]
for (int j = m; 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 <= m; j++)
down[i] = max(down[i], h[i][j] * (dr[j] - st[j] - 1));
}
for (int i = 1; i < n; i++)
maxArea = max(maxArea, up[i] + down[i + 1]);
}
int main()
{
Read();
Solve();
Rotate();
Solve();
fout << maxArea;
return 0;
}