Cod sursa(job #2716144)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 4 martie 2021 19:17:35
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>

#define NMAX 205
using namespace std;

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

int poz[NMAX], mat[NMAX][NMAX], vec[NMAX], whX, whY, n, m, lat, lung, maxUp[NMAX], maxDown[NMAX], maxLeft[NMAX], maxRight[NMAX];
deque<int> st;

int work(int val)
{
    vec[val + 1] = -(1 << 30);
    int Amax = 0;
    st.clear();
    for(int j = 1; j <= val + 1; ++j)
    {
        poz[j] = j;
        while(!st.empty() && vec[st.back()] >= vec[j])
        {
            poz[j] = poz[st.back()];
            int Arie = vec[st.back()] * (j - poz[st.back()]);
            if(Arie >= Amax)
                Amax = Arie;
            st.pop_back();
        }
        st.push_back(j);
    }
    return Amax;
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= n; ++i)
    {
        string s;
        fin >> s;

        for(int j = 0; j < m; ++j)
            mat[i][j + 1] = s[j] - '0';
    }

    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
            if(mat[i][j] == 0)
                vec[j]++;
            else vec[j] = 0;
        maxUp[i] = max(maxUp[i - 1], work(m));
    }
    memset(vec, 0, sizeof(vec));

    for(int i = n; i >= 1; --i)
    {
        for(int j = 1; j <= m; ++j)
            if(mat[i][j] == 0)
                vec[j]++;
            else vec[j] = 0;
        maxDown[i] = max(maxDown[i + 1], work(m));
    }

    memset(vec, 0, sizeof(vec));

    for(int j = 1; j <= m; ++j)
    {
        for(int i = 1; i <= n; ++i)
            if(mat[i][j] == 0)
                vec[i]++;
            else vec[i] = 0;
        maxLeft[j] = max(maxLeft[j - 1], work(n));
    }
    memset(vec, 0, sizeof(vec));

    for(int j = m; j >= 1; --j)
    {
        for(int i = 1; i <= n; ++i)
            if(mat[i][j] == 0)
                vec[i]++;
            else vec[i] = 0;
        maxRight[j] = max(maxRight[j + 1], work(n));
    }

    int rez = 0;
    for(int i = 1; i <= n; ++i)
        rez = max(rez, maxUp[i] + maxDown[i + 1]);

    for(int j = 1; j <= m; ++j)
        rez = max(rez, maxLeft[j] + maxRight[j + 1]);


    fout << rez << '\n';
    return 0;
}