Pagini recente » Borderou de evaluare (job #981299) | Cod sursa (job #2942331) | Borderou de evaluare (job #1061662) | Cod sursa (job #2161269) | Cod sursa (job #3351197)
#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];
stack <pair <int, 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++)
{
for (int j = y1; j <= y2; j++)
{
if (a[i][j] == 0)
{
h[j]++;
}
else
{
h[j] = 0;
}
while (!stk.empty() && h[stk.top().first] >= h[j])
{
ans = max(ans, h[stk.top().first] * (j - stk.top().second));
stk.pop();
}
stk.push({j, stk.empty() ? y1 : stk.top().first + 1});
}
while (!stk.empty())
{
ans = max(ans, h[stk.top().first] * (y2 - stk.top().second + 1));
stk.pop();
}
}
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;
}