Cod sursa(job #677354)

Utilizator vlad2901Vlad Berindei vlad2901 Data 10 februarie 2012 01:25:38
Problema BMatrix Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cstdio>
#include <algorithm>

#define NMAX 210

using namespace std;

struct elem {
    int poz, elm;
} v[NMAX];

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

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)
        {
            aux[i][j] = a[i][j] == '0' ? aux[i-1][j] + 1 : 0;
        }
    }

    int best = 0;

    for(int i=y1;i<=y2;++i)
    {
        v[0].elm = -1;
        v[0].poz = x1 - 1;
        int top = 0;

        for(int j=x1;j<=x2;++j)
        {
            while(aux[i][j] <= v[top].elm)
            {
                --top;
            }
            if(best < aux[i][j] * (j - v[top].poz))
            {
                best = aux[i][j] * (j - v[top].poz);
            }
            top++;
            v[top].elm = aux[i][j];
            v[top].poz = j;
        }
    }

    return best;
}

void reverse()
{
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=n>>1;++j)
        {
            swap(a[i][j], a[i][n-j+1]);
        }
    }
}

int solve()
{
    int best = 0, b, b1, b2;

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

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

    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)
    {
        char s[NMAX];
        scanf("%s", a[i]+1);
    }

    int best1 = solve();

    reverse();

    int best2 = solve();

    if(best1 > best2)
    {
        printf("%d\n", best1);
        return 0;
    }

    printf("%d\n", best2);
    return 0;

}