Cod sursa(job #3143221)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 28 iulie 2023 10:51:39
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <climits>

using namespace std;

int n, m, a[20][20], sol = INT_MIN;
int subset[20], len;

void flip_line(int line) {
    for(int i = 1; i <= m; i++) {
        a[line][i] *= -1;
    }
}

void solve_subset() {
    for(int i = 1; i <= len; i++) {
        flip_line(subset[i]);
    }

    int total = 0;
    for(int col = 1; col <= m; col++) {
        int sum_col = 0;
        for(int lin = 1; lin <= n; lin++) {
            sum_col += a[lin][col];
        }
        total += abs(sum_col);
    }
    sol = max(sol, total);

    // undo:
    for(int i = 1; i <= len; i++) {
        flip_line(subset[i]);
    }
}

void backtrack(int nr) {
    // Am terminat de generat o submultime de linii:
    if(nr == n + 1) {
        solve_subset();
        return;
    }
    // Caz 1: nu il iau pe nr in submultimile pe care le generez next
    backtrack(nr + 1);

    // Caz 2: Il iau pe nr in submultimile pe care le generez next
    subset[++len] = nr;
    backtrack(nr + 1);
    --len; // undo
}

int main() {
    ifstream fin("flip.in");
    ofstream fout("flip.out");
    fin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            fin >> a[i][j];
        }
    }
    backtrack(1);
    fout << sol << "\n";
    return 0;
}