Cod sursa(job #2729498)

Utilizator trucker4lifeMoraru Radu-Andrei trucker4life Data 24 martie 2021 19:57:49
Problema Jocul Flip Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

vector<vector<int>> arr;
int r, c;
int ans = -2000000000;

void flip_coloane(int j) {
    if (j == c) {
        int temp_sum = 0;
        for (int i = 0; i < r; i++) {
            for (int k = 0; k < c; k++)
                temp_sum += arr[i][k];
        }
        ans = max(ans, temp_sum);
    }
    else {
        int suma = 0;
        for (int i = 0; i < r; i++)
            suma += arr[i][j];
        if (suma < 0) {
            for (int i = 0; i < r; i++)
                arr[i][j] *= -1;
            flip_coloane(j+1);
            for (int i = 0; i < r; i++)
                arr[i][j] *= -1;
        }
        flip_coloane(j+1);
    }
}

void flip_linii(int i) {
    if (i == r) {
        flip_coloane(0);
    }
    else {
        int suma = 0;
        for (int j = 0; j < c; j++)
            suma += arr[i][j];
        if (suma < 0) {
            for (int j = 0; j < c; j++)
                arr[i][j] *= -1;
            flip_linii(i+1);
            for (int j = 0; j < c; j++)
                arr[i][j] *= -1;
        }
        flip_linii(i+1);
    }
}

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

    fin >> r >> c;

    arr = vector<vector<int>>(r, vector<int>(c));

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            fin >> arr[i][j];
        }
    }

    flip_linii(0);

    fout << ans;
}