Pagini recente » Cod sursa (job #2014688) | Cod sursa (job #1024976) | Cod sursa (job #981043) | Cod sursa (job #1171243) | Cod sursa (job #2961749)
#include <bits/stdc++.h>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int nmax = 205;
bool v[nmax][nmax];
int tmp[nmax][nmax];
int sum[nmax][nmax];
int st[nmax][nmax], dr[nmax][nmax];
int n, m;
void calcStDr(int l)
{
stack<pair<int, int>> s;
for (int i = 1; i <= m; i++)
{
while (!s.empty() && s.top().first >= sum[l][i])
{
s.pop();
}
int tmp = 0;
if (!s.empty() && s.top().first < sum[l][i])
tmp = s.top().second;
s.push({sum[l][i], i});
st[l][i] = tmp;
}
while (!s.empty())
s.pop();
for (int i = m; i >= 1; i--)
{
while (!s.empty() && s.top().first >= sum[l][i])
{
s.pop();
}
int tmp = m + 1;
if (!s.empty() && s.top().first < sum[l][i])
tmp = s.top().second;
s.push({sum[l][i], i});
dr[l][i] = tmp;
}
}
int solve()
{
memset(sum, 0, sizeof sum);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
sum[i][j] = (!v[i][j]) * sum[i - 1][j] + !v[i][j];
}
}
for (int l = 1; l <= n; l++)
{
calcStDr(l);
// for (int i = 1; i <= m; i++)
// {
// out << sum[l][i] << ' ';
// }
// out << '\n';
// for (int i = 1; i <= m; i++)
// {
// out << st[l][i] << ' ';
// }
// out << '\n';
// for (int i = 1; i <= m; i++)
// {
// out << dr[l][i] << ' ';
// }
// out << '\n';
}
int res = 0;
for (int i = 1; i < m; i++)
{
int resA = 0, resB = 0;
for (int l = 1; l <= n; l++)
{
for (int a = 1; a <= i; a++)
{
resA = max(resA, (min(i + 1, dr[l][a]) - st[l][a] - 1) * sum[l][a]);
}
for (int b = i + 1; b <= m; b++)
{
resB = max(resB, (dr[l][b] - max(i, st[l][b]) - 1) * sum[l][b]);
}
}
res = max(res, resA + resB);
}
return res;
}
void rotate()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
tmp[i][j] = v[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
v[j][n - i + 1] = tmp[i][j];
}
}
swap(n, m);
}
int main()
{
in >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
char c;
in >> c;
v[i][j] = (c == '1');
}
}
int res = solve();
for (int i = 0; i < 3; i++)
{
rotate();
res = max(res, solve());
}
out << res;
}