Cod sursa(job #3162221)

Utilizator catalinmarincatalinmarin catalinmarin Data 28 octombrie 2023 16:51:24
Problema Jocul Flip Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int mat[21][21];
int suma_coloane[17];
int vector_bkt[17];
int n, m;
int answer = -1 * (1 << 31);
void test_suma(){
    int rasp_temp = 0;
    vector<int> indici_flipped;
    for (int i = 1; i <= n; i++){
        if (vector_bkt[i] == 1) {
            indici_flipped.push_back(i);
        }
    }
    for (int i = 1; i <= m; i++){
        int sum = suma_coloane[i];
        bool flipped = false;
        if (sum < 0) {
            sum *= -1;
            flipped = true;
        }
        for (int j = 0; j < indici_flipped.size(); j++){
            if (flipped == false)
                sum += (mat[indici_flipped[j]][i] * -1) * 2;
            else
                sum += (mat[indici_flipped[j]][i]) * 2;
        }
        rasp_temp += sum;
    }
    answer = max(answer, rasp_temp);
}
void backtracking(int poz){
    if (poz == n + 1){
        test_suma();
        return;
    }
    for (int i = 0; i <= 1; i++){
        vector_bkt[poz] = i;
        backtracking(poz + 1);
    }
}
int main(){
    fin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            fin >> mat[i][j];
            suma_coloane[j] += mat[i][j];
        }
    }
    backtracking(1);
    fout << answer;
    return 0;
}