Cod sursa(job #1189133)

Utilizator catalinrebegeaUNIBUC-Claudia Catarig catalinrebegea Data 21 mai 2014 15:52:59
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <algorithm>
#define Nmax 205

using namespace std;

int N,M,dp[Nmax][Nmax],s[Nmax][Nmax];
char a[Nmax][Nmax];

inline int LenMax(int a[], int n)
{
    int l=0,i,cnt=0;
    for(i=1;i<=n;++i)
        if(!a[i])
            ++l;
        else
        {
            cnt=max(cnt,l);
            l=0;
        }
    cnt=max(cnt,l);
    return cnt;
}

inline void Dinamic()
{
    int i,j,k,v[Nmax];
    for(i=1;i<=N;++i)
        for(j=1;j<=M;++j)
            s[i][j]=s[i-1][j]+a[i][j]-'0';
    for(i=N;i;--i)
        for(j=i;j<=N;++j)
        {
            for(k=1;k<=M;++k)
                v[k]=s[j][k]-s[i-1][k];
            dp[i][j]=LenMax(v,M)*(j-i+1);
            if(i<j)
                dp[i][j]=max(dp[i][j],dp[i+1][j]);
            if(i<j)
                dp[i][j]=max(dp[i][j],dp[i][j-1]);
        }
}

inline void Rotate()
{
    int i,j,aux;
    char b[Nmax][Nmax];
    for(i=1;i<=N;++i)
        for(j=1;j<=M;++j)
            b[j][N-i+1]=a[i][j];
    for(i=1;i<=M;++i)
        for(j=1;j<=N;++j)
            a[i][j]=b[i][j];
    aux=N; N=M; M=aux;
}

int main()
{
    int i,sol=0;
    freopen ("bmatrix.in","r",stdin);
    freopen ("bmatrix.out","w",stdout);
    scanf("%d%d", &N,&M);
    for(i=1;i<=N;++i)
        scanf("%s", (a[i]+1));
    Dinamic();
    for(i=1;i<=N;++i)
        sol=max(sol,dp[1][i]+dp[i+1][N]);
    Rotate();
    Dinamic();
    for(i=1;i<=N;++i)
        sol=max(sol,dp[1][i]+dp[i+1][N]);
    printf("%d\n", sol);
    return 0;
}