Cod sursa(job #823049)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 24 noiembrie 2012 15:33:40
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 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];
string I;
int ANS;
int cc;
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])
            {
                cc=S.top();
                S.pop();

                ANS=max(ANS,min(H[i][cc],i-L1+1)*(j-L[cc]));
            }
            if (!S.empty())
                L[j]=S.top()+1;
            else
                L[j]=C1;

            S.push(j);
        }
        while (!S.empty())
        {
            cc=S.top();
            S.pop();

            ANS=max(ANS,min(H[i][cc],i-L1+1)*(C2-L[cc]+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/2; l++)
        ANS=max(ANS,GetSubmatrix(1,1,l,M)+GetSubmatrix(l+1,1,N,M));

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

    g << ANS << '\n';

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

    return 0;
}