Cod sursa(job #2741799)

Utilizator N3ctar1eNectarie Tulea N3ctar1e Data 19 aprilie 2021 11:14:10
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#define NMAX 16

using namespace std;

ifstream cin("flip.in");
ofstream cout("flip.out");

int a[NMAX+1][NMAX+1],lin[NMAX+1];
struct ura
{
  int viz, el;
};
ura col[NMAX+1];
bool v[NMAX+1];


int main()
{
    int n,m,suma=0;
    cin>>n>>m;
    if(n>=m)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
                col[j].el+=a[i][j];
                suma+=a[i][j];
            }
    }
    else
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>a[j][i];
                col[j].el+=a[j][i];
                suma+=a[j][i];
            }
        swap(n,m);
    }
    int maxx=-1000000;
    for(int i=1;i<=(1<<m)-1;i++)
    {
        for(int j=1;j<=m;j++)
            col[j].viz=0;
        int s=suma;
        for(int j=0;j<m;j++)
            if((i>>j)&1)
            {
                s-=(2*col[j+1].el);
                col[j+1].viz=1;
            }

        if (s>maxx)
        {
            maxx=s;
            for(int j=1;j<=m;j++)
                if(col[j].viz)
                    v[j]=true;
                else
                    v[j]=false;
        }
    }
    suma=maxx;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(v[j]==true)
                lin[i]-=a[i][j];
            else
                lin[i]+=a[i][j];

    for(int i=1;i<=(1<<n)-1;i++)
    {
        int s=suma;
        for(int j=0;j<n;j++)
            if((i>>j)&1)
                s-=(2*lin[j+1]);
        if(s>maxx)
            maxx=s;
    }

    cout<<"\n"<<maxx;
    return 0;
}