Cod sursa(job #2930393)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 28 octombrie 2022 12:31:52
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.9 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("bmatrix.in");
ofstream out("bmatrix.out");

int n,m,a[205][205],h[205][205],up[205],down[205];
int st[205],dr[205];
int ans;
int aux[205][205];

int main()
{
    in >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char ch;
            in >> ch;
            if (ch == '1')
                a[i][j] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 1)
                h[i][j] = 0;
            else
                h[i][j] = 1 + h[i - 1][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        stack<int>s;
        for (int j = 1; j <= m; j++)
        {
            while (!s.empty() and h[i][s.top()] > h[i][j])
                dr[s.top()] = j - 1,s.pop();
            s.push(j);
        }
        while (!s.empty())
            dr[s.top()] = m,s.pop();
        for (int j = m; j >= 1; j--)
        {
            while (!s.empty() and h[i][s.top()] > h[i][j])
                st[s.top()] = j + 1,s.pop();
            s.push(j);
        }
        while (!s.empty())
            st[s.top()] = 1,s.pop();
        int amax = 0;
        for (int j = 1; j <= m; j++)
            amax = max(amax,h[i][j] * (dr[j] - st[j] + 1));
        up[i] = max(up[i - 1],amax);
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 1)
                h[i][j] = 0;
            else
                h[i][j] = 1 + h[i + 1][j];
        }
    }
    for (int i = n; i >= 1; i--)
    {
        stack<int>s;
        for (int j = 1; j <= m; j++)
        {
            while (!s.empty() and h[i][s.top()] > h[i][j])
                dr[s.top()] = j - 1,s.pop();
            s.push(j);
        }
        while (!s.empty())
            dr[s.top()] = m,s.pop();
        for (int j = m; j >= 1; j--)
        {
            while (!s.empty() and h[i][s.top()] > h[i][j])
                st[s.top()] = j + 1,s.pop();
            s.push(j);
        }
        while (!s.empty())
            st[s.top()] = 1,s.pop();
        int amax = 0;
        for (int j = 1; j <= m; j++)
            amax = max(amax,h[i][j] * (dr[j] - st[j] + 1));
        down[i] = max(down[i + 1],amax);
    }
    for (int i = 1; i <= n; i++)
        ans = max(ans,up[i] + down[i + 1]);
    for (int i = 1; i <= 200; i++)
        for (int j = 1; j <= 200; j++)
            h[i][j] = 0;
    for (int i = 1; i <= 200; i++)
        up[i] = down[i] = 0;
    for (int i = 1; i <= 200; i++)
        st[i] = dr[i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            aux[j][i] = a[i][j];
    swap(n,m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = aux[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 1)
                h[i][j] = 0;
            else
                h[i][j] = 1 + h[i - 1][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        stack<int>s;
        for (int j = 1; j <= m; j++)
        {
            while (!s.empty() and h[i][s.top()] > h[i][j])
                dr[s.top()] = j - 1,s.pop();
            s.push(j);
        }
        while (!s.empty())
            dr[s.top()] = m,s.pop();
        for (int j = m; j >= 1; j--)
        {
            while (!s.empty() and h[i][s.top()] > h[i][j])
                st[s.top()] = j + 1,s.pop();
            s.push(j);
        }
        while (!s.empty())
            st[s.top()] = 1,s.pop();
        int amax = 0;
        for (int j = 1; j <= m; j++)
            amax = max(amax,h[i][j] * (dr[j] - st[j] + 1));
        up[i] = max(up[i - 1],amax);
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 1)
                h[i][j] = 0;
            else
                h[i][j] = 1 + h[i + 1][j];
        }
    }
    for (int i = n; i >= 1; i--)
    {
        stack<int>s;
        for (int j = 1; j <= m; j++)
        {
            while (!s.empty() and h[i][s.top()] > h[i][j])
                dr[s.top()] = j - 1,s.pop();
            s.push(j);
        }
        while (!s.empty())
            dr[s.top()] = m,s.pop();
        for (int j = m; j >= 1; j--)
        {
            while (!s.empty() and h[i][s.top()] > h[i][j])
                st[s.top()] = j + 1,s.pop();
            s.push(j);
        }
        while (!s.empty())
            st[s.top()] = 1,s.pop();
        int amax = 0;
        for (int j = 1; j <= m; j++)
            amax = max(amax,h[i][j] * (dr[j] - st[j] + 1));
        down[i] = max(down[i + 1],amax);
    }
    for (int i = 1; i <= n; i++)
        ans = max(ans,up[i] + down[i + 1]);
    out << ans;
    return 0;
}