Cod sursa(job #2223630)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 20 iulie 2018 21:07:32
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<fstream>
#include<queue>
using namespace std;
ifstream fi("bmatrix.in");
ofstream fo("bmatrix.out");
int n,m,i,j,A[205][205],H[205],Pst[205],pdr,rez,Dp[5][205],vr,Aux[205][205];
char S[205];
deque<int> Q;

void rotateA()
{
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            Aux[j][n-i+1]=A[i][j];
    for(i=1; i<=m; i++)
        for(j=1; j<=n; j++)
            A[i][j]=Aux[i][j];
    swap(n,m);
}

int main()
{
    fi>>n>>m;
    for(i=1; i<=n; i++)
    {
        fi>>S;
        for(j=0; j<m; j++)
            A[i][j+1]=S[j]-'0';
    }
    for(vr=1; vr<=4; vr++)
    {
        for(i=1; i<=m; i++)
            H[i]=0;
        for(i=1; i<=n; i++)
        {
            Dp[vr][i]=Dp[vr][i-1];
            for(j=1; j<=m; j++)
                H[j]=(A[i][j]==0)?(H[j]+1):0;
            Q.clear();
            for(j=1; j<=m; j++)
            {
                while(!Q.empty() && H[Q.back()]>=H[j])
                    Q.pop_back();
                if(Q.empty())
                    Pst[j]=j-1;
                else
                    Pst[j]=j-Q.back()-1;
                Q.push_back(j);
            }
            Q.clear();
            for(j=m; j>=1; j--)
            {
                while(!Q.empty() && H[Q.back()]>=H[j])
                    Q.pop_back();
                if(Q.empty())
                    pdr=m-j+1;
                else
                    pdr=Q.back()-j;
                Dp[vr][i]=max(Dp[vr][i],H[j]*(Pst[j]+pdr));
                Q.push_back(j);
            }
        }
        rotateA();
    }
    for(i=1; i<n; i++)
        rez=max(rez,Dp[1][i]+Dp[3][n-i]);
    for(i=1; i<m; i++)
        rez=max(rez,Dp[2][i]+Dp[4][m-i]);
    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}