Cod sursa(job #2072414)

Utilizator pSergiuPatras Sergiu pSergiu Data 21 noiembrie 2017 20:27:33
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ofstream fout("flip.out");

int n,m,a[18][18],sol[18];
int lc;
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;
    int c = max(m,n);
    if(lc == m){
        for(i=1;i<=c;i++){
            ss = 0;
            for(j=1;j<=lc;j++)
                ss += a[i][j];
            s += abs(ss);
        }
    }
    else {
        for(i=1;i<=c;i++){
            ss = 0;
            for(j = 1; j<=lc; j++)
                ss += a[j][i];
            s += abs(ss);
        }
    }
  res = max(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();
    if(n < m)
        lc = n;
    else
        lc = m;
    bk(0);
   fout<<res;
    fout.close();
    return 0;
}