Cod sursa(job #2908232)

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

using namespace std;
ifstream fin("flip.fin");
ofstream fout("flip.out");

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

void read(){
    fin >> 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 ++){
            fin >> matrix[i][j];
        }
    }
    colSwitch = new int[n];
}
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 bckt(int row){
    if(row == n){
        int m = solve();
        if(m > maxSum)
            maxSum = m;
    }else{
        colSwitch[row] = 1;
        bckt(row + 1);
        colSwitch[row] = -1;
        bckt(row + 1);
    }
}
void write(){
    fout << maxSum;
    for(int i = 0 ; i < n ; i++)
        delete[] matrix[i];
    delete[] matrix;
    delete[] colSwitch;
}

int main() {
    read();
    bckt(0);
    write();
    return 0;
}