Cod sursa(job #1191108)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 26 mai 2014 16:50:14
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 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],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;
}

inline void DEQ(int lin)
{
    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 (sumepart[lin][j])
        {
            while (ul>=1 && sumepart[lin][j]>=deq[ul].val) ul--;
            deq[++ul].val=sumepart[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 (sumepart[lin][j])
        {
            while (ul>=1 && sumepart[lin][j]>=deq[ul].val) ul--;
            deq[++ul].val=sumepart[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;
    for (i=1;i<=n;i++)
        {
            DEQ(i);
            for (j=1;j<=m;j++)
                M=max(M,(dr[j]-st[j]+1)*sumepart[i][j]);
        }
}

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