Cod sursa(job #823043)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 24 noiembrie 2012 15:28:12
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <stack>
#define NM 210

using namespace std;

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

int N,M;
int i,j;
int l,c;
int A[NM][NM];
int H[NM][NM];
int L[NM],R[NM];
string I;
int ANS;
stack<int> S;

int GetSubmatrix (int L1, int C1, int L2, int C2)
{
    int ANS=0;
    for (i=L1; i<=L2; i++)
    {
        for (j=C1; j<=C2; j++)
        {
            while (!S.empty() && H[i][S.top()]>=H[i][j])
            {
                R[S.top()]=j-1;
                S.pop();
            }
            if (!S.empty())
                L[j]=S.top()+1;
            else
                L[j]=C1;

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

        for (j=C1; j<=C2; j++)
            ANS=max(ANS,min(H[i][j],i-L1+1)*(R[j]-L[j]+1));
    }

    return ANS;
}

int main ()
{
    f >> N >> M;
    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';
            H[i][j]=(H[i-1][j]+1)*(1-A[i][j]);
        }
    }

    for (l=1; l<N; l++)
        ANS=max(ANS,GetSubmatrix(1,1,l,M)+GetSubmatrix(l+1,1,N,M));

    for (c=1; c<M; c++)
        ANS=max(ANS,GetSubmatrix(1,1,N,c)+GetSubmatrix(1,c+1,N,M));

    g << ANS << '\n';

    f.close();
    g.close();

    return 0;
}