Cod sursa(job #2228408)

Utilizator 12222Fendt 1000 Vario 12222 Data 3 august 2018 16:39:05
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 205;
int n, m, ans;
int a[Nmax][Nmax], b[Nmax][Nmax], sume1[Nmax][Nmax], sume2[Nmax][Nmax];
int lin[Nmax], lin1[Nmax], lin2[Nmax], stg[Nmax], drp[Nmax];
stack<int> st;

inline int Dreptunghi_max()
{
    stg[1] = 1;
    st.push(1);

    for(int i = 2; i <= m; i++)
    {
        stg[i] = 1;
        while(!st.empty() && lin[i] <= lin[st.top()])
        {
            stg[i] += stg[st.top()];
            st.pop();
        }
        st.push(i);
    }

    while(!st.empty())
        st.pop();

    drp[m] = 1;
    st.push(m);

    for(int i = m - 1; i >= 1; i--)
    {
        drp[i] = 1;
        while(!st.empty() && lin[i] <= lin[st.top()])
        {
            drp[i] += drp[st.top()];
            st.pop();
        }
        st.push(i);
    }


    while(!st.empty())
        st.pop();

    int dr_max = 0;

    for(int i = 1; i <= m; i++)
        dr_max = max(dr_max, (stg[i] + drp[i] - 1) * lin[i]);

    return dr_max;
}

void Rezolvare(int a[Nmax][Nmax])
{
    for(int i = 1; i <= n; i++)
        lin1[i] = lin2[i] = 0;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(a[i][j] == 0)sume1[i][j] = sume1[i - 1][j] + 1;
            else sume1[i][j] = 0;

    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= m; j++)
            if(a[i][j] == 0)sume2[i][j] = sume2[i + 1][j] + 1;
            else sume2[i][j] = 0;

    int dr;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            lin[j] = sume1[i][j];

        dr = Dreptunghi_max();
        lin1[i] = max(lin1[i-1], dr);
    }


    for(int i = n; i >= 1; i--)
    {
        for(int j = 1; j <= m; j++)
            lin[j] = sume2[i][j];

        dr = Dreptunghi_max();
        lin2[i] = max(lin2[i+1], dr);
    }

    for(int i = 1; i <= n; i++)
        ans = max(ans, lin1[i] + lin2[i + 1]);
}

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

    char ch;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            fin >> ch;
            b[j][i] = a[i][j] = ch - '0';
        }

    Rezolvare(a);
    swap(n, m);
    Rezolvare(b);

    fout << ans << "\n";
    fin.close();
    fout.close();
    return 0;
}