Cod sursa(job #3340394)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 14 februarie 2026 09:45:11
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>

using namespace std;

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

const int Nmax = 20;

int n, m;
long long sol;
int mat[Nmax][Nmax];
bool is_fliped[Nmax];

void citire(){
    fin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            fin >> mat[i][j];
        }
    }
}

void flip(){
    for(int i = 1; i <= n; i++){
        if(is_fliped[i]){
            for(int j = 1; j <= m; j++){
                mat[i][j] *= (-1);
            }
        }
    }
}

void verificare_suma(){
    long long sum, suma_coloana;

    flip();

    sum = 0;
    for(int j = 1; j <= m; j++){
        suma_coloana = 0;
        for(int i = 1; i <= n; i++){
            suma_coloana += mat[i][j];
        }

        if(suma_coloana < 0){
            sum -= suma_coloana;
        }
        else{
            sum += suma_coloana;
        }
    }

    sol = max(sol, sum);

    flip();
}

void backtracking(int poz){
    if(poz == n + 1){
        verificare_suma();
        return;
    }

    for(int fliped = 0; fliped <= 1; fliped++){
        is_fliped[poz] = fliped;
        backtracking(poz + 1);
    }
}

void afisare(){
    fout << sol;
}

int main(){
    citire();

    sol = 0;
    backtracking(1);

    afisare();

    return 0;
}