Pagini recente » Cod sursa (job #980124) | Cod sursa (job #3249367) | Cod sursa (job #1654694) | Cod sursa (job #2195124) | Cod sursa (job #2961632)
#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], dr[nmax];
int n, m;
int maxarea(int l, int a, int b)
{
stack<pair<int, int>> s;
for (int i = a; i <= b; i++)
{
while (!s.empty() && s.top().first >= sum[l][i])
{
s.pop();
}
int tmp = a - 1;
if (!s.empty() && s.top().first < sum[l][i])
tmp = s.top().second;
s.push({sum[l][i], i});
st[i] = tmp;
}
while (!s.empty())
s.pop();
for (int i = b; i >= a; i--)
{
while (!s.empty() && s.top().first >= sum[l][i])
{
s.pop();
}
int tmp = b + 1;
if (!s.empty() && s.top().first < sum[l][i])
tmp = s.top().second;
s.push({sum[l][i], i});
dr[i] = tmp;
}
int res = 0;
for (int i = a; i <= b; i++)
{
res = max(res, (dr[i] - st[i] - 1) * sum[l][i]);
}
// out << "\nv: ";
// for (int i = a; i <= b; i++)
// {
// out << sum[l][i] << ' ';
// }
// out << "\nst: ";
// for (int i = a; i <= b; i++)
// {
// out << st[i] << ' ';
// }
// out << "\ndr: ";
// for (int i = a; i <= b; i++)
// {
// out << dr[i] << ' ';
// }
return res;
}
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];
}
}
int res = 0;
for (int i = 1; i < m; i++)
{
int resa, resb;
resa = resb = 0;
for (int j = 1; j <= n; j++)
{
resa = max(resa, maxarea(j, 1, i));
resb = max(resb, maxarea(j, i + 1, m));
}
res = max(res, resa + resb);
// out << i << ' ' << resa << ' ' << resb << '\n';
}
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;
}