Cod sursa(job #673839)

Utilizator vlad2901Vlad Berindei vlad2901 Data 4 februarie 2012 22:43:20
Problema BMatrix Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <cstdio>
#include <stack>

#define NMAX 200

using namespace std;

int aux[NMAX][NMAX], a[NMAX][NMAX],m , n;

int best_dr(int x1, int y1, int x2, int y2) //stanga sus, dreapta jos
{
    for(int i=x1;i<=x2;++i)
    {
        aux[y1-1][i] = 0;
    }

    for(int i=y1;i<=y2;++i)
    {
        for(int j=x1;j<=x2;++j)
        {
            if(a[i][j] == 0)
            {
                aux[i][j] = aux[i-1][j] + 1;
            }
            else
            {
                aux[i][j] = 0;
            }
        }
    }

    int best = 0;

    for(int i=y1;i<=y2;++i)
    {
        stack<pair<int, int> >S;
        S.push(make_pair(x1-1,-1));

        for(int j=x1;j<=x2;++j)
        {
            while(aux[i][j] <= S.top().second)
            {
                S.pop();
            }
            if(best < aux[i][j] * (j - S.top().first))
            {
                best = aux[i][j] * (j - S.top().first);
            }
            S.push(make_pair(j, aux[i][j]));
        }

        stack<pair<int, int> >S2;
        S2.push(make_pair(x2+1,-1));

        for(int j=x2;j>=x1;--j)
        {
            while(aux[i][j] <= S2.top().second)
            {
                S2.pop();
            }
            if(best < aux[i][j] * (S2.top().first - j))
            {
                best = aux[i][j] * (S2.top().first - j);
            }
            S2.push(make_pair(j, aux[i][j]));
        }
    }

    return best;

}

int main()
{
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);

    scanf("%d %d", &m, &n);

    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=n;++j)
        {
            scanf(" %c ", &a[i][j]);
            a[i][j] -= '0';
        }
    }

    int best = 0, b;

    for(int i=1;i<n;++i)
    {
        b = best_dr(1,1,i,m);
        b += best_dr(i+1,1,n,m);
        if(b > best)
        {
            best = b;
        }
    }

    for(int i=1;i<m;++i)
    {
        b = best_dr(1,1,n,i);
        b += best_dr(1,i+1,n,m);
        if(b > best)
        {
            best = b;
        }
    }

    printf("%d", best);




    return 0;
}