Cod sursa(job #2772431)

Utilizator pasqualePascale Radu-Ioan pasquale Data 1 septembrie 2021 10:08:30
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

int N, M;
long board[16][16];
long sum, maxsum = INT64_MIN;
bool col[16], row[16];

void sum_board() {
    sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (row[i] && !col[j]) {
                sum += -board[i][j];
            }
            else if (!row[i] && !col[j]) {
                sum += board[i][j];
            }
            else if (row[i] && col[j]){
                sum +=board[i][j];
            }
            else {
                sum += -board[i][j];
            }
        }
    }
    maxsum = max(sum, maxsum);
}

void bkt() {
    for (int i = 0; i < N; i++) {
        if (row[i]) continue;
        sum_board();
        row[i] = true;
        for (int j = 0; j < M; j++) {
            if (col[j]) continue;
            sum_board();
            col[j] = true;
            bkt();
            col[j] = false;
        }
        row[i] = false;
    }
}

int main() {
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }
    bkt();
    cout << maxsum << endl;
}