Cod sursa(job #841122)

Utilizator danalex97Dan H Alexandru danalex97 Data 23 decembrie 2012 20:03:05
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#include <stack>
#include <cstring>
using namespace std;

const int Nmax = 210;

int Hmax[Nmax][2],Sol,Act;
int Right[Nmax],Left[Nmax];
int L[Nmax][Nmax][2];
int N,M,A[Nmax][Nmax];

ifstream F("bmatrix.in");
ofstream G("bmatrix.out");

#define FOR(i,start,stop,inc) for (int i=start;i!=stop;i+=inc)

stack<int> St;

void Solve()
{
    memset(L,0,sizeof(L));
    memset(Hmax,0,sizeof(Hmax));

    FOR(i,1,N+1,+1) FOR(j,1,M+1,+1) L[i][j][0]= ( L[i-1][j][0]+1 ) * ( 1-A[i][j] );
    FOR(i,N,0,-1) FOR(j,1,M+1,+1) L[i][j][1]= ( L[i+1][j][1]+1 ) * ( 1-A[i][j] );

    for (int i=1;i<=N;++i)
        for (int x=0;x<2;++x)
        {
            for (int j=1;j<=M;++j)
            {
                for ( ; St.size() && L[i][St.top()][x] >= L[i][j][x] ; St.pop() )
                    Right[ St.top() ] = j-1;
                Left[j]= St.size() ? St.top()+1 : 1;
                St.push(j);
            }
            for ( ; St.size() ; St.pop() )
                Right[St.top()]=M;

            Act=0;
            for (int j=1;j<=M;++j)
                Act=max(Act,L[i][j][x]*(Right[j]-Left[j]+1));
            Hmax[i][x]=max(Hmax[i-(x==0 ? 1 : -1)][x],Act);
        }

    for (int i=1;i<N;++i)
        Sol=max(Sol,Hmax[i][0]+Hmax[i+1][1]);
}

void Rotate()
{
    int B[Nmax][Nmax];
    memcpy(B,A,sizeof(B));

    FOR(i,1,N+1,+1) FOR(j,1,M+1,+1) A[j][i]=B[i][j];

    swap(N,M);
}

#undef FOR

string Str;

int main()
{
    F>>N>>M;
    getline(F,Str);

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

    Solve();
    Rotate();
    Solve();

    G<<Sol<<'\n';
}