Cod sursa(job #2435746)

Utilizator Briana_NeaguNeagu Briana Briana_Neagu Data 4 iulie 2019 12:57:29
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include<bits/stdc++.h>
#define maxim 210


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


int n,m ;
char mat[maxim][maxim],aux[maxim][maxim];
int down[maxim] , max2[maxim];
int up[maxim];
int stiva[maxim];
int vf;


void start()
{


    for (int i=n; i>=1; i--) // cati de 0  sunt sub el ( inceputul unei matrice)
    {
        stiva[0]=stiva[1]=0;
        vf=1;
        for (int j=1; j<=m+1; j++)
        {
            if (mat[i][j]=='1' ||  j == m+1 )
                down[j]=0;
            else
                 down[j]++;


            if (down[stiva[vf]] == down[j])
                    stiva[vf]=j;
            else
            {
                while (vf && down[stiva[vf]] >  down[j])
                {
                    max2[i]=max(max2[i], down[stiva[vf]]*(j-stiva [ vf-1 ]-1));
                    vf--;
                }
                stiva[++vf]=j;
            }

        }
       // cout<<endl;
    }
   for (int i = n-1; i>=1; i-- )
       max2[i]=max(max2[i],max2[i+1]);  //  matrice de arie max  care incepe de la linia i in jos


   /*for (int i=1; i<=n ;i++)
       cout<<max2[i]<<'\n';
   cout<<endl<<'\n'; */

}


int solve()
{

    int ans=0;

    for (int i=1; i<=n; i++)
    {
        stiva[0]=stiva[1]=0;
        vf=1;
        int arie1=0;

        for (int j= 1; j<=m+1 ; j++)
        {
            if ( mat[i][j]=='1' || j == m+1 )
                up[j]=0;
            else
                up[j]++;

            if (up[stiva[vf]] == up[j])
                stiva[vf]=j;
            else
            {
                while (vf && up[stiva[vf]] > up[j])
                {
                    arie1=max(arie1, up[stiva[vf]]* ( j - stiva [ vf-1 ]-1 ) );
                    vf--;
                }
                stiva[++vf]=j;
            }


        }
        //cout<<i<<" "<<arie1<<endl;
        ans=max(ans,arie1+max2[i+1]);
    }
    return ans;
}


int main()
{

    int ANS=0;
    f>>n>>m;
    for (int i=1; i<=n ; i++)
        for (int j=1; j<=m; j++)
            f>>mat[i][j];
    start();
    ANS=solve();
    memset(max2, 0, sizeof(max2));

    for (int i=1 ; i<=m+1 ;i++)
        up[i]=down[i]=0;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            aux[j][i]=mat[n-i+1][j];

    swap(n,m);
    for(int i=1;i<=n;i++)
        for (int j = 1; j <= m; j++)
            mat[i][j] = aux[i][j];

    start();
    g<<max(ANS,solve());



}