Pagini recente » Cod sursa (job #1610301) | Cod sursa (job #1743272) | Cod sursa (job #950171) | Cod sursa (job #1400911) | Cod sursa (job #2961612)
#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(vector<int> a)
{
stack<pair<int, int>> s;
for (int i = 0; i < a.size(); i++)
{
while (!s.empty() && s.top().first >= a[i])
{
s.pop();
}
int tmp = -1;
if (!s.empty() && s.top().first < a[i])
tmp = s.top().second;
s.push({a[i], i});
st[i] = tmp;
}
while (!s.empty())
s.pop();
for (int i = a.size() - 1; i >= 0; i--)
{
while (!s.empty() && s.top().first >= a[i])
{
s.pop();
}
int tmp = a.size();
if (!s.empty() && s.top().first < a[i])
tmp = s.top().second;
s.push({a[i], i});
dr[i] = tmp;
}
int res = 0;
for (int i = 0; i < a.size(); i++)
{
res = max(res, (dr[i] - st[i] - 1) * a[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 resa[nmax], resb[nmax];
memset(resa, 0, sizeof resa);
memset(resb, 0, sizeof resb);
for (int i = 1; i <= n; i++)
{
vector<int> a, b;
for (int j = 1; j <= m; j++)
a.push_back(sum[i][j]);
b.push_back(a.back());
a.pop_back();
while (!a.empty())
{
resa[a.size()] = max(maxarea(a), resa[a.size()]);
resb[b.size()] = max(maxarea(b), resb[b.size()]);
b.push_back(a.back());
a.pop_back();
}
}
int res = 0;
for (int i = 1; i < m; i++)
{
res = max(res, resa[i] + resb[m - i]);
}
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;
}