Pagini recente » Cod sursa (job #1004702) | Cod sursa (job #3345513) | Cod sursa (job #2703085) | Cod sursa (job #3310459) | Cod sursa (job #3351173)
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const long long max_size = 2e2 + 20;
int a[max_size][max_size], h[max_size], st[max_size], dr[max_size];
stack <int> stk;
int solvesubmatrix (int x1, int y1, int x2, int y2)
{
int ans = 0;
for (int j = y1; j <= y2; j++)
{
h[j] = 0;
}
for (int i = x1; i <= x2; i++)
{
while (!stk.empty())
{
stk.pop();
}
for (int j = y1; j <= y2; j++)
{
if (a[i][j] == 0)
{
h[j]++;
}
else
{
h[j] = 0;
}
while (!stk.empty() && h[stk.top()] >= h[j])
{
stk.pop();
}
if (stk.empty())
{
st[j] = y1;
}
else
{
st[j] = stk.top() + 1;
}
stk.push(j);
}
while (!stk.empty())
{
stk.pop();
}
for (int j = y2; j >= y1; j--)
{
while (!stk.empty() && h[stk.top()] >= h[j])
{
stk.pop();
}
if (stk.empty())
{
dr[j] = y2;
}
else
{
dr[j] = stk.top() - 1;
}
stk.push(j);
ans = max(ans, h[j] * (dr[j] - st[j] + 1));
}
}
return ans;
}
void solve ()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
for (int j = 1; j <= m; j++)
{
a[i][j] = s[j - 1] - '0';
}
}
int ans = 0;
for (int i = 1; i < n; i++)
{
ans = max(ans, solvesubmatrix(1, 1, i, m) + solvesubmatrix(i + 1, 1, n, m));
}
for (int j = 1; j < m; j++)
{
ans = max(ans, solvesubmatrix(1, 1, n, j) + solvesubmatrix(1, j + 1, n, m));
}
cout << ans;
cout << '\n';
}
signed main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
#endif // LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long tt;
tt = 1;
//cin >> tt;
while (tt--)
{
solve();
}
return 0;
}