Cod sursa(job #1189112)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 21 mai 2014 13:25:00
Problema BMatrix Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 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];
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);
                }
        }
    maxim=-1;
    for (i=2;i<=n-1;i++)
        maxim=max(maxim,dp[1][i]+dp[i][n]);
    fout<<maxim<<"\n";
}

int main()
{
    Citire();
    Preprocesare();
    DP();
    return 0;
}