Cod sursa(job #3128708)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 10 mai 2023 16:30:19
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int MAX_N = 20;

int n, m;
int board[MAX_N][MAX_N];
vector <int> flippedX;
int maxSum;

void HandleInput() {
    fin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            fin >> board[i][j];
        }
    }
}

void Flip(int x) {
    for (int j = 0; j < m; j++) {
        board[x][j] = -board[x][j];
    }
}

void ComputeSum() {
    for (int x : flippedX) {
        Flip(x);
    }

    int sum = 0;
    for (int j = 0; j < m; j++) {
        int sumCol = 0;
        for (int i = 0; i < n; i++) {
            sumCol += board[i][j];
        }

        sum += abs(sumCol);
    }
    maxSum = max(sum, maxSum);

    for (int x : flippedX) {
        Flip(x);
    }
}

void Backtracking(int x) {
    if (x == n - 1) {
        ComputeSum();
        return;
    }

    flippedX.push_back(x);
    Backtracking(x + 1);
    flippedX.pop_back();
    Backtracking(x + 1);
}

void HandleOutput() {
    fout << maxSum << '\n';
}

int main() {
    HandleInput();
    Backtracking(0);
    HandleOutput();

    return 0;
}