Cod sursa(job #2908239)

Utilizator baragan30Baragan Andrei baragan30 Data 2 iunie 2022 11:47:50
Problema Jocul Flip Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in("flip1.in");
ofstream out("flip.out");

int **matrix;
int *colSwitch;
int n,m;
int maxSum = 0;

void read(){
    in >> n>>m;
    matrix = new int*[n];
    for(int i = 0 ; i < n ;i ++){
        matrix[i] = new int[m];
        for(int j = 0 ; j < m ; j ++){
            in >> matrix[i][j];

        }
    }
    colSwitch = new int[m];
}
int solve(){
    int sum = 0 ;
    for(int i = 0 ; i < n ; i ++){
        int rowSum = 0;
        for(int j = 0 ; j < m ; j ++){
            rowSum += colSwitch[j] * matrix[i][j];
        }
        // max(+/- colsum) = abs (rowSum)
        int x = abs(rowSum);
        sum+=x;

    }
    return sum;
}

void backtrack(int row){
    if(row == m){
        int sum = solve();
//        for(int i = 0 ; i < m; i ++)
//            cout<<colSwitch[i]<<' ';
//        cout<<'\n'<<sum<<"\n\n";
        if(sum > maxSum)
            maxSum = sum;
    }else{
        colSwitch[row] = 1;
        backtrack(row + 1);
        colSwitch[row] = -1;
        backtrack(row + 1);
    }
}
void write(){
    out << maxSum;
    for(int i = 0 ; i < n ; i++)
        delete[] matrix[i];
    delete[] matrix;
    delete[] colSwitch;
}

int main() {
    read();
    backtrack(0);
    write();

    return 0;
}