Cod sursa(job #1189367)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 22 mai 2014 16:28:00
Problema BMatrix Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include<fstream>
using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

const int Nmax=205;

int n,m,sumepart[Nmax][Nmax],dp[Nmax][Nmax],M;
bool a[Nmax][Nmax];
char s[205];

inline void Citire()
{
    int i,j;
    fin>>n>>m;
    for (i=1;i<=n;i++)
        {
            fin>>(s+1);
            for (j=1;j<=m;j++)
                a[i][j]=s[j]-'0';
        }
}

inline void Preprocesare()
{
    int i,j,nr,maxim;
    for (j=1;j<=m;j++)
        for (i=1;i<=n;i++)
            {
                sumepart[i][j]=sumepart[i-1][j];
                if (a[i][j]) sumepart[i][j]++;
            }
    for (i=1;i<=n;i++)
        {
            j=1;maxim=0;
            while (j<=m)
                {
                    while (j<=m && a[i][j]) j++;
                    nr=0;
                    while (j<=m && !a[i][j]) {nr++;j++;}
                    if (nr>maxim) maxim=nr;
                }
            dp[i][i+1]=maxim;
        }
}

inline void DP()
{
    int i,j,nr=1,maxim,c;
    while (nr<=n-1)
        {
            nr++;
            for (i=1;i<=n-nr+1;i++)
                {
                    dp[i][i+nr]=max(dp[i+1][i+nr],dp[i][i+nr-1]);
                    j=1;maxim=0;
                    while (j<=m)
                        {
                            while (j<=m && sumepart[i+nr-1][j]>sumepart[i-1][j]) j++;
                            c=0;
                            while (j<=m && sumepart[i+nr-1][j]==sumepart[i-1][j]) {c+=nr;j++;}
                            if (c>maxim) maxim=c;
                        }
                    dp[i][i+nr]=max(dp[i][i+nr],maxim);
                }
        }
    for (i=2;i<=n-1;i++)
        M=max(M,dp[1][i]+dp[i][n]);
}

inline void Rotate()
{
    int i,j,k=0,l,aux[Nmax][Nmax];
    for (j=1;j<=m;j++)
        {
            k++;l=0;
            for (i=n;i>=1;i--)
                {
                    l++;
                    aux[k][l]=a[i][j];
                }
        }
    for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
            a[i][j]=aux[i][j];
    swap(n,m);
}

int main()
{
    Citire();
    Preprocesare();
    DP();
    Rotate();
    Preprocesare();
    DP();
    fout<<M<<"\n";
    return 0;
}