Cod sursa(job #2587925)

Utilizator ana_valeriaAna Valeria Duguleanu ana_valeria Data 23 martie 2020 19:46:58
Problema Jocul Flip Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <fstream>

using namespace std;
ifstream cin ("flip.in");
ofstream cout ("flip.out");
int a[20][20],lin[20],col[20];
int main()
{
    long long n,m,i,j,ii,jj,s,maxx,S,suma1,suma2,suma3,suma4;
    cin>>n>>m;
    S=0;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
        {
            cin>>a[i][j];
            S=S+a[i][j];
        }
    for (i=1; i<=n; i++)
    {
        s=0;
        for (j=1; j<=m; j++)
            s=s+a[i][j];
        lin[i]=s;
    }
    for (j=1; j<=m; j++)
    {
        s=0;
        for (i=1; i<=n; i++)
            s=s+a[i][j];
        col[j]=s;
    }
    maxx=-260000000;
    for (i=1; i<=(1<<n/2); i++)
    {
        suma1=suma2=suma3=suma4=S;
        for (ii=0; ii<n; ii++)
            if (((i>>ii)&1)==1)
            {
                suma1=suma1-2*lin[ii+1];
                suma2=suma2-2*lin[ii+1];
                for (j=1; j<=(1<<m/2); j++)
                    for (jj=0; jj<m; jj++)
                        if (((j>>jj)&1)==1)
                        {
                            suma1=suma1-2*col[jj+1];
                            suma1=suma1+4*a[ii+1][jj+1];
                            if (suma1>maxx)
                                maxx=suma1;
                        }
                        else
                        {
                            suma2=suma2-2*col[jj+1];
                            suma2=suma2+4*a[ii+1][jj+1];
                            if (suma2>maxx)
                                maxx=suma2;
                        }
            }
            else
            {
                suma3=suma3-2*lin[ii+1];
                suma4=suma4-2*lin[ii+1];
                for (j=1; j<=(1<<m/2); j++)
                    for (jj=0; jj<m; jj++)
                        if (((j>>jj)&1)==1)
                        {
                            suma3=suma3-2*col[jj+1];
                            suma3=suma3+4*a[ii+1][jj+1];
                            if (suma3>maxx)
                                maxx=suma3;
                        }
                        else
                        {
                            suma4=suma4-2*col[jj+1];
                            suma4=suma4+4*a[ii+1][jj+1];
                            if (suma4>maxx)
                                maxx=suma4;
                        }
            }
    }
    cout<<maxx;
    return 0;
}