Cod sursa(job #2155383)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 7 martie 2018 20:22:21
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 205;

void calculeazadreptunghi(char x[NMAX][NMAX],int n,int m,int maxx[NMAX][NMAX])
{
    int inaltime[NMAX][NMAX];
    for(int i=1;i<=m;i++)
    {
        inaltime[0][i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(x[i][j]=='0')
                inaltime[i][j]=inaltime[i-1][j]+1;
            else
                inaltime[i][j]=0;
        }
    }
    int good[NMAX];

    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            for(int c=1;c<=m;c++)
            {
                if(inaltime[j][c]>=j-i+1)
                    good[c]=1;
                else
                    good[c]=0;
            }
            int k=0,maxim=0;
            for(int c=1;c<=m;c++)
            {
                if(good[c]==1)
                {
                    k++;
                }
                else
                {
                    k=0;
                }
                if(k>maxim)
                    maxim=k;
            }
            maxx[i][j]=maxim*(j-i+1);
        }
    }


}

int Calculeaza(char x[NMAX][NMAX],int n,int m)
{
    int maxx[NMAX][NMAX],dp[NMAX],dp2[NMAX];
    calculeazadreptunghi(x,n,m,maxx);
    for(int i=1;i<=n;i++)
    {
        dp[i]=0;
        dp2[i]=0;
        for(int x=1;x<=i;x++)
        {
            for(int y=x;y<=i;y++)
            {
                if(maxx[x][y]>=dp[i])
                    dp[i]=maxx[x][y];
            }
        }
        for(int x=i;x<=n;x++)
        {
            for(int y=x;y<=n;y++)
            {
                if(maxx[x][y]>=dp2[i])
                    dp2[i]=maxx[x][y];
            }
        }
    }
    int solutie=0;
    for(int i=1;i<n;i++)
    {
        if(dp[i]+dp2[i+1]>solutie)
            solutie=dp[i]+dp2[i+1];
    }
    return solutie;
}

int main()
{
    int n,m;
    fin >> n >> m;
    char x[NMAX][NMAX],inv[NMAX][NMAX];
    for(int i=1;i<=n;i++)
    {
        fin >> (x[i]+1);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            inv[i][j]=x[j][i];
        }
    }
    ///fout << calculeazadreptunghi(x,n,m) << '\n';
    fout << max(Calculeaza(x,n,m),Calculeaza(inv,m,n));
    return 0;
}