Cod sursa(job #3351173)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 17 aprilie 2026 13:26:36
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#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; 
}