Cod sursa(job #2073160)

Utilizator pSergiuPatras Sergiu pSergiu Data 22 noiembrie 2017 19:19:40
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ofstream fout("flip.out");

int n,m,a[20][20],sol[20];
int lc;
unsigned long long res;

void input(){
    ifstream fin("flip.in");
    fin>>n>>m;
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin>>a[i][j];
    fin.close();
}

void print(){
    int i,j;
    for(i=1;i<=n;i++,fout<<'\n')
        for(j=1;j<=m;j++)
            fout<<a[i][j]<<" ";
}

void flip(int x){
    int j;
    if(lc == n){
        for(j=1;j<=m;j++)
            a[x][j] = -a[x][j];
    }
    else {
        for(j=1;j<=n;j++)
            a[j][x] = -a[j][x];
    }
}

void getSum(){
    long long s = 0,ss = 0;
    int i,j;
    if(lc == n){
        for(i=1;i<=m;i++){
            ss = 0;
            for(j = 1; j<=n; j++)
                ss += a[j][i];
            s += abs(ss);
        }
    }
    else {
        for(i=1;i<=n;i++){
            ss = 0;
            for(j=1;j<=n;j++)
                ss += a[i][j];
            s += abs(ss);
        }
    }
  if(s > res)
    res = s;
}

void bk(int i){
    if(i == lc){
        return;
    }
    for(int j = i+1; j <= lc ;j++)
        if(j > sol[i]){
            sol[i+1] = j;
            flip(j);
            getSum();
            bk(i+1);
            flip(j);
        }
}

int main()
{
    input();
    lc = n > m ? m : n;
    bk(0);
   fout<<res;
    fout.close();
    return 0;
}