Cod sursa(job #692555)

Utilizator vlad2901Vlad Berindei vlad2901 Data 26 februarie 2012 17:08:36
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 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], b[NMAX][NMAX];
int best[NMAX][4];

int best_dr(int l) //cel mai mare dreptunghi cu baza de jos pe linia l
{
    v[0].elm = -1;
    v[0].poz = 0;
    int top = 0, best = 0;

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

    return best;
}

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

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);
    }

    for(int j=0;j<4;++j)
    {
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=n;++j)
            {
                aux[i][j] = a[i][j] == '0' ? aux[i-1][j] + 1 : 0;
            }
            best[i][j] = max(best_dr(i), best[i-1][j]);
        }
        if(j<3)
        {
            rotate90();
        }
    }

    int max = -1;

    for(int j=1;j<=m;++j)
    {
        if(max < best[j][0] + best[n-j][2])
        {
            max = best[j][0] + best[n-j][2];
        }
    }

    for(int j=1;j<=m;++j)
    {
        if(max < best[j][1] + best[m-j][3])
        {
            max = best[j][1] + best[m-j][3];
        }
    }


    printf("%d", max);

    return 0;

}