Cod sursa(job #1961848)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 11 aprilie 2017 13:37:10
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <vector>
#include <cstring>
#define Nmax 201
using namespace std;

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

int mx,n,m,nr[Nmax],N[Nmax],S[Nmax],E[Nmax],V[Nmax];
char mat[Nmax][Nmax];

int hist(int V[],int n)
{
    int mx=0;
    vector<int> st;
    for(int i=1;i<=n;i++)
    {
        while(!st.empty() && V[st.back()]>=V[i])
            st.pop_back();
        int lst;
        if (st.empty())
            lst = 1;
        else
            lst = st.back()+1;
        mx = max(mx,(i-lst+1) * V[i]);
        st.push_back(i);
    }
    for (int i=1;i<st.size();i++)
        mx = max(mx,(n-st[i]+1) * V[st[i]]);
    return mx;
}

int main()
{
    f>>n>>m;
    for (int i=1;i<=n;i++)
        f>>mat[i]+1;

    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if (mat[i][j]=='1')
                nr[j] = 0;
            else
                nr[j]++;
        }
        N[i] = max(N[i-1],hist(nr,m));
    }

    memset(nr,0,sizeof(nr));
    for (int i=n;i>=1;i--)
    {
        for (int j=1;j<=m;j++)
        {
            if (mat[i][j]=='1')
                nr[j] = 0;
            else
                nr[j]++;
        }
        S[i] = max(S[i+1],hist(nr,m));
    }

    memset(nr,0,sizeof(nr));
    for (int j=1;j<=m;j++)
    {
        for (int i=1;i<=n;i++)
        {
            if (mat[i][j]=='1')
                nr[i] = 0;
            else
                nr[i]++;
        }
        V[j] = max(V[j-1],hist(nr,n));
    }

    memset(nr,0,sizeof(nr));
    for (int j=m;j>=1;j--)
    {
        for (int i=1;i<=n;i++)
        {
            if (mat[i][j]=='1')
                nr[i] = 0;
            else
                nr[i]++;
        }
        E[j] = max(E[j+1],hist(nr,n));
    }

    for (int i=1;i<n;i++)
        mx = max(mx,N[i]+S[i+1]);

    for (int i=1;i<m;i++)
        mx = max(mx,V[i]+E[i+1]);

    g<<mx<<'\n';

    return 0;
}