Cod sursa(job #823076)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 24 noiembrie 2012 16:08:40
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
#include <cstring>
#include <stack>
#define NM 210

using namespace std;

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

int N,M;
int i,j;
int A[NM][NM];
int HUp[NM][NM],HDown[NM][NM];
int HMaxUp[NM],HMaxDown[NM];
int L[NM],R[NM];
int ANS;
int CANS;
stack<int> S;

void Read ()
{
    f >> N >> M;
    string I;
    getline(f,I);

    for (i=1; i<=N; i++)
    {
        getline(f,I);
        for (j=1; j<=M; j++)
            A[i][j]=I[j-1]-'0';
    }

    f.close();
    return;
}

void Print ()
{
    g << ANS << '\n';

    g.close();
    return;
}

void Rotate ()
{
    int B[NM][NM];
    memcpy(B,A,sizeof(B));
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
            A[j][i]=B[i][j];

    swap(N,M);

    return;
}

void Solve ()
{
    memset(HUp,0,sizeof(HUp));
    memset(HDown,0,sizeof(HDown));
    memset(HMaxUp,0,sizeof(HMaxUp));
    memset(HMaxDown,0,sizeof(HMaxDown));

    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
            HUp[i][j]=(HUp[i-1][j]+1)*(1-A[i][j]);

    for (i=N; i>=1; i--)
        for (j=1; j<=M; j++)
            HDown[i][j]=(HDown[i+1][j]+1)*(1-A[i][j]);

    for (i=1; i<=N; i++)
    {
        for (j=1; j<=M; j++)
        {
            while (!S.empty() && HUp[i][S.top()]>=HUp[i][j])
            {
                R[S.top()]=j-1;
                S.pop();
            }
            if (!S.empty())
                L[j]=S.top()+1;
            else
                L[j]=1;

            S.push(j);
        }
        while (!S.empty())
        {
            R[S.top()]=M;
            S.pop();
        }

        CANS=0;
        for (j=1; j<=M; j++)
            CANS=max(CANS,HUp[i][j]*(R[j]-L[j]+1));
        HMaxUp[i]=max(HMaxUp[i-1],CANS);

        for (j=1; j<=M; j++)
        {
            while (!S.empty() && HDown[i][S.top()]>=HDown[i][j])
            {
                R[S.top()]=j-1;
                S.pop();
            }
            if (!S.empty())
                L[j]=S.top()+1;
            else
                L[j]=1;

            S.push(j);
        }
        while (!S.empty())
        {
            R[S.top()]=M;
            S.pop();
        }

        CANS=0;
        for (j=1; j<=M; j++)
            CANS=max(CANS,HDown[i][j]*(R[j]-L[j]+1));
        HMaxDown[i]=max(HMaxDown[i+1],CANS);
    }

    for (i=1; i<N; i++)
        ANS=max(ANS,HMaxUp[i]+HMaxDown[i+1]);

    return;
}

int main ()
{
    Read();
    Solve();
    Rotate();
    Solve();
    Print();

    return 0;
}