Cod sursa(job #1503291)

Utilizator ialexia_ioanaAlexia Ichim ialexia_ioana Data 15 octombrie 2015 20:58:24
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <cstdio>
#include <cstring>
const int  DIM=256;
const int  INF=2000000000;
using namespace std;

FILE *fin = fopen("bmatrix.in" ,"r");
FILE *fout= fopen("bmatrix.out","w");

int D[DIM][DIM];
char S[DIM];
int best[5][DIM],A[DIM][DIM];
int E[3][DIM], d, maxim, aux;
int N, M, i, j, k, C[DIM][DIM];
int poz;

void rotare_matrice()
{
    for(i=1; i<=N; i++)
        for(j=1; j<=M; j++)
            C[j][N-i+1]=A[i][j];
    aux=N;
    N=M;
    M=aux;
    for(i=1; i<=N; i++)
    {
        for(j=1; j<=M; j++)
            A[i][j]=C[i][j];
    }
}

void parti()
{
    memset(D, 0, sizeof(D));
    for(i=1; i<=N; i++)
    {
        for(j=1; j<=M; j++)
        {
            if(A[i][j]==0)
                D[i][j]=D[i-1][j]+1;
            else
                D[i][j]=0;
        }
    }
}
void bmatrix()
{
    for(d=1; d<=4; d++)
    {
        parti();
        for(i=1; i<=N; i++)
        {
            maxim=0;
            k=0;
            for(j=1; j<=M+1; j++)
            {
                if(D[i][j]>E[1][k])
                {
                    k++;
                    E[1][k]=D[i][j];
                    E[2][k]=j;
                }
                else
                {
                    while(D[i][j]<=E[1][k] && k>0)
                    {
                        if(maxim<E[1][k]*(j - E[2][k]))
                            maxim=E[1][k]*(j - E[2][k]);
                        poz=E[2][k];
                        k--;
                    }
                    if(D[i][j] != 0)
                    {
                        k++;
                        E[1][k]=D[i][j];
                        E[2][k]=poz;
                    }
                }
            }
            best[d][i]=maxim;
        }
        rotare_matrice();
    }
}

void refacere()
{
    maxim=0;
    for(i=1; i<=N; i++)
    {
        if(maxim<best[1][i])
            maxim=best[1][i];
        best[1][i]=maxim;
    }
    maxim=0;
    for(j=1; j<=M; j++)
    {
        if(maxim<best[2][j])
            maxim=best[2][j];
        best[2][j]=maxim;
    }
    maxim=0;
    for(i=1; i<=N; i++)
    {
        if(maxim<best[3][i])
            maxim=best[3][i];
        best[3][i]=maxim;
    }
    maxim=0;
    for(j=1; j<=M; j++)
    {
        if(maxim<best[4][j])
            maxim=best[4][j];
        best[4][j]=maxim;
    }
}

void terminare()
{
    maxim=0;
    for(i=1; i<N; i++)
    {
        if(maxim<best[1][i]+best[3][N-i])
            maxim=best[1][i]+best[3][N-i];
    }
    for(j=1; j<M; j++)
    {
        if(maxim<best[2][j]+best[4][M-j])
            maxim=best[2][j]+best[4][M-j];
    }
    printf("%d", maxim);
}

int main()
{
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for(i=1; i<=N; i++)
    {
        scanf("%s", &S);
        for(j=0; j<M; j++)
            A[i][j+1]=S[j]-'0';
    }
    bmatrix();
    refacere();
    terminare();
    return 0;
}