Cod sursa(job #1191115)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 26 mai 2014 17:18:41
Problema BMatrix Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<fstream>
using namespace std;

struct nod
{
    int val,nivel;
};

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

const int Nmax=205;

int n,m,sumepart[Nmax][Nmax],dp[Nmax][Nmax],dr[Nmax],st[Nmax],M;
bool a[Nmax][Nmax];
char s[205];
nod deq[Nmax];

inline void Citire()
{
    int i,j;
    fin>>n>>m;
    for (i=1;i<=n;i++)
        {
            fin>>(s+1);
            for (j=1;j<=m;j++)
                a[i][j]=s[j]-'0';
        }
}

inline void Preprocesare()
{
    int i,j;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (!a[i][j]) sumepart[i][j]=sumepart[i-1][j]+1;
    for (i=n;i>=1;i--)
        for (j=1;j<=m;j++)
            if (!a[i][j]) dp[i][j]=dp[i+1][j]+1;
}

inline void DEQ(int lin,int mat[Nmax][Nmax])
{
    int j,ul;
    for (j=0;j<=Nmax;j++) st[j]=dr[j]=deq[j].val=deq[j].nivel=0;

    ul=0;
    for (j=1;j<=m;j++)
        if (mat[lin][j])
        {
            while (ul>=1 && mat[lin][j]<=deq[ul].val) ul--;
            deq[++ul].val=mat[lin][j];
            deq[ul].nivel=j;
            st[j]=deq[ul-1].nivel+1;
        }
        else {ul=0;deq[0].nivel=j;}

    ul=0;deq[0].nivel=m+1;
    for (j=m;j;j--)
        if (mat[lin][j])
        {
            while (ul>=1 && mat[lin][j]<=deq[ul].val) ul--;
            deq[++ul].val=mat[lin][j];
            deq[ul].nivel=j;
            dr[j]=deq[ul-1].nivel-1;
        }
        else {ul=0;deq[0].nivel=j;}
}

inline void Rezolva()
{
    int i,j,m1,m2;
    for (i=1;i<n;i++)
        {
            m1=m2=0;
            DEQ(i,sumepart);
            for (j=1;j<=m;j++)
                m1=max(m1,(dr[j]-st[j]+1)*sumepart[i][j]);
            DEQ(i+1,dp);
            for (j=1;j<=m;j++)
                m2=max(m2,(dr[j]-st[j]+1)*dp[i+1][j]);
            //fout<<m1<<" "<<m2<<"\n";
            M=max(M,m1+m2);
        }
}

int main()
{
    Citire();
    Preprocesare();
    Rezolva();
    fout<<M<<"\n";
    return 0;
}