Cod sursa(job #1314346)

Utilizator acomAndrei Comaneci acom Data 11 ianuarie 2015 19:39:38
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n,m,maxim,sum,sus[205],jos[205],D[205][205];
char a[205][205],aux[205][205];
void roteste()
{
    int i,j;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            aux[j][i]=a[i][j];
    i=m, m=n, n=i;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            a[i][j]=aux[i][j];
}
int main()
{
    int i,j,k;
    fin>>n>>m; fin.get();
    for (i=1;i<=n;++i)
    {
        fin>>(a[i]+1);
        fin.get();
    }
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            if (a[i][j]=='0')
                D[i][j]=1+D[i-1][j];
    for (i=1;i<=n;++i)
        for (j=i;j<=n;++j)
        {
            sum=0;
            for (k=1;k<=m;++k)
                if (D[j][k]-D[i-1][k]==j-i+1)
                    sum+=j-i+1;
                else if (sum)
                {
                    sus[j]=max(sus[j],sum);
                    jos[i]=max(jos[i],sum);
                    sum=0;
                }
            sus[j]=max(sus[j],sum);
            jos[i]=max(jos[i],sum);
        }
    for (i=2;i<=n;++i)
        sus[i]=max(sus[i],sus[i-1]);
    for (j=n-1;j>0;--j)
        jos[i]=max(jos[i],jos[i+1]);
    for (i=0;i<=n;++i)
        maxim=max(maxim,sus[i]+jos[i+1]);
    roteste();
    memset(sus,0,sizeof(sus));
    memset(jos,0,sizeof(jos));
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            if (a[i][j]=='0')
                D[i][j]=1+D[i-1][j];
            else
                D[i][j]=0;
    for (i=1;i<=n;++i)
        for (j=i;j<=n;++j)
        {
            sum=0;
            for (k=1;k<=m;++k)
                if (D[j][k]-D[i-1][k]==j-i+1)
                    sum+=j-i+1;
                else if (sum)
                {
                    sus[j]=max(sus[j],sum);
                    jos[i]=max(jos[i],sum);
                    sum=0;
                }
            sus[j]=max(sus[j],sum);
            jos[i]=max(jos[i],sum);
        }
    for (i=2;i<=n;++i)
        sus[i]=max(sus[i],sus[i-1]);
    for (j=n-1;j>0;--j)
        jos[i]=max(jos[i],jos[i+1]);
    for (i=0;i<=n;++i)
        maxim=max(maxim,sus[i]+jos[i+1]);
    fout<<maxim<<"\n";
    return 0;
}