Cod sursa(job #1191176)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 26 mai 2014 19:08:27
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include<fstream>
using namespace std;

struct element
{
    int val,poz;
};

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

const int NMAX = 205;

int n,m,a[NMAX][NMAX],sumepart[NMAX][NMAX],dp[NMAX][NMAX],aux[NMAX][NMAX];
int b[NMAX],c[NMAX];
char s[NMAX];
int S;
int sumes[NMAX],sumej[NMAX];
element deq[NMAX];

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

inline void Preprocess()
{
    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;i--)
        for (j=1;j<=m;j++)
            if (!a[i][j]) dp[i][j]=dp[i+1][j]+1;
}

inline void D_E(int linia,int mat[NMAX][NMAX])
{
    int j,ul;
    for (j=0;j<=NMAX;j++) b[j]=c[j]=deq[j].val=deq[j].poz=0;

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

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

inline void Rezolva()
{
    int i,j;
    for (i=1;i<=n;i++)
        {
            D_E(i,sumepart);
            sumes[i]=sumes[i-1];
            for (j=1;j<=m;j++)
                sumes[i]=max(sumes[i],(c[j]-b[j]+1)*sumepart[i][j]);
        }
     for (i=n;i;i--)
        {
            D_E(i,dp);
            sumej[i]=sumej[i+1];
            for (j=1;j<=m;j++)
                sumej[i]=max(sumej[i],(c[j]-b[j]+1)*dp[i][j]);
        }
}

inline void Rotate()
{
    int i,j,l;
    for (j=1;j<=m;j++)
        for (i=n;i;i--)
            aux[j][n-i+1]=a[i][j];
    for (i=1;i<=n;i++)
        {
            sumes[i]=sumej[i]=0;
            for (j=1;j<=m;j++) sumepart[i][j]=dp[i][j]=0;
        }
    swap(n,m);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            a[i][j]=aux[i][j];
}

int main()
{
    int i;
    Citire();
    Preprocess();
    Rezolva();
    for (i=1;i<n;i++) S=max(S,sumes[i]+sumej[i+1]);
    Rotate();
    Preprocess();
    Rezolva();
    for (i=1;i<n;i++) S=max(S,sumes[i]+sumej[i+1]);
    fout<<S<<"\n";
    return 0;
}