Cod sursa(job #292323)

Utilizator crawlerPuni Andrei Paul crawler Data 31 martie 2009 00:29:20
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <stdio.h>

#define Nmax 256

char a[Nmax][Nmax], b[Nmax][Nmax];
short A[Nmax][Nmax], B[Nmax][Nmax];
short sa[Nmax][Nmax], ja[Nmax][Nmax];
short sb[Nmax][Nmax], jb[Nmax][Nmax];
short msa[Nmax], mja[Nmax];
short msb[Nmax], mjb[Nmax];
short n,m;

int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    
    scanf("%d%d\n", &n,&m);
    
    for (int i=1;i<=n;++i,scanf("\n"))
    for (int j=1;j<=m;++j)
    {
        char c;
        scanf("%c", &c);
        a[i][j] = b[j][i] = c-48;    
    }
    
    for (int i=1;i<=n;++i)
    for (int j=1;j<=m;++j)
    {
        if (a[i][j] == 1) A[i][j] = 0;
                    else  A[i][j] = A[i][j-1] + 1;
        if (b[j][i] == 1) B[j][i] = 0;
                    else  B[j][i] = B[j][i-1] + 1;
    }
    
    for (int i=1;i<=n;++i)
    for (int j=1;j<=m;++j)
    {
        int min = A[i][j], arie;
        for (int k = 1;i-k+1>0;++k)
        {
            if (A[i-k+1][j] < min) min = A[i-k+1][j];
            arie = k*min;
            if (arie > sa[i][j]) sa[i][j] = arie;    
        }
        min = A[i][j];
        for (int k = 1;i+k-1<=n;++k)
        {
            if (A[i+k-1][j] < min) min = A[i+k-1][j];
            arie = k*min;
            if (arie > ja[i][j]) ja[i][j] = arie;    
        }            
    }
    
    for (int i=1;i<=m;++i)
    for (int j=1;j<=n;++j)
    {
        int min = B[i][j], arie;
        for (int k = 1;i-k+1>0;++k)
        {
            if (B[i-k+1][j] < min) min = B[i-k+1][j];
            arie = k*min;
            if (arie > sb[i][j]) sb[i][j] = arie;    
        }
        min = B[i][j];
        for (int k = 1;i+k-1<=m;++k)
        {
            if (B[i+k-1][j] < min) min = B[i+k-1][j];
            arie = k*min;
            if (arie > jb[i][j]) jb[i][j] = arie;    
        }            
    }
    
    for (int i=1;i<=n;++i)
    {
        msa[i] = msa[i-1];
        for (int j=1;j<=m;++j)
        if (sa[i][j] > msa[i])
        msa[i] = sa[i][j];
    }
    
    for (int i=n;i>=1;--i)
    {
        mja[i] = mja[i+1];
        for (int j=1;j<=m;++j)
        if (ja[i][j] > mja[i])
        mja[i] = ja[i][j];    
    }
    
    for (int i=1;i<=m;++i)
    {
        msb[i] = msb[i-1];
        for (int j=1;j<=n;++j)
        if (sb[i][j] > msb[i])
        msb[i] = sb[i][j];   
    }
    
    for (int i=m;i>=1;--i)
    {
        mjb[i] = mjb[i+1];
        for (int j=1;j<=n;++j)
        if (jb[i][j] > mjb[i])
        mjb[i] = jb[i][j];    
    }
    
    int ret = 0;
    
    for (int i=1;i<n;++i)
    if (msa[i] + mja[i+1] > ret) ret = msa[i] + mja[i+1];
    
    for (int i=1;i<m;++i)
    if (msb[i] + mjb[i+1] > ret) ret = msb[i] + mjb[i+1];
    
    printf("%d\n", ret);
    
    return 0;    
}