Cod sursa(job #1978858)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 8 mai 2017 22:54:27
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, s, smax;
int a[18][18];
int scol[18];

void coloane(int &ss)
{
    int i;
    for(i=1; i<=m; i++)
        if(scol[i]<0)
            ss-=2*scol[i];
}

void flip(int l, int &ss)
{
    int i;
    ss=s;
    for(i=1; i<=m; i++)
        a[l][i]*=(-1), ss+=2*a[l][i], scol[i]+=2*a[l][i];
}

int suma()
{
    int sss=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            sss+=a[i][j];
    return sss;
}

void bk(int p)
{
    int i, ss;
    for(i=1; i<=n; i++)
    {
        s=suma();
        flip(i, ss);
        coloane(ss);
        if(ss>smax)
            smax=ss;
        if(p<n)
            bk(p+1);
    }
}

int main()
{
    int i, j;
    fin>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            {
                fin>>a[i][j];
                s+=a[i][j];
                scol[j]+=a[i][j];
            }
    bk(1);
    fout<<smax<<'\n';
    return 0;
}