Cod sursa(job #1539661)

Utilizator oana.fercheoana maria oana.ferche Data 1 decembrie 2015 11:57:29
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>

using namespace std;

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

bool u[16];
int n, m, sol;
int a[16][16], sumc[16];

int suma(){
    int result = 0;
    for (int j = 0; j < m; j++){
        if (sumc[j] > 0){
            result += sumc[j];
        } else {
            result -= sumc[j];
        }
    }
    return result;
}

void sumac(){
    for (int j = 0; j < m; j++){
        sumc[j] = 0;
        for (int i = 0; i < n; i++){
            sumc[j] += (u[i] == 1 ? 1 : -1) * a[i][j];
        }
    }
}

void backtrack(int k){
    if (k == n){
        sumac();
        sol = max(sol, suma());
    } else {
        for (int i = 0; i <= 1; i++){
            u[k] = i;
            backtrack(k+1);
        }
    }
}

int main(){

    fin >> n >> m;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            fin >> a[i][j];
        }
    }

    backtrack(0);
    fout << sol << "\n";

    return 0;
}