Cod sursa(job #2897082)

Utilizator dfettiDaniel Fetti dfetti Data 2 mai 2022 13:57:45
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define MAX_SIZE 17

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

int N, M, max_sum;
int A[MAX_SIZE][MAX_SIZE];

int line_sign[MAX_SIZE];

void check()
{
    int current_max_sum = 0;

    for (int j = 1; j <= M; ++j)
    {
        int current_column = 0;
        for (int i = 1; i <= N; ++i)
        {
            current_column += line_sign[i] * A[i][j];
        }

        current_max_sum += max(current_column, (-1 * current_column));
    }

    max_sum = max(max_sum, current_max_sum);
}

void backtracking(int step)
{
    if (step == N + 1)
    {
        check();
        return;
    }

    line_sign[step] = -1;
    backtracking(step + 1);

    line_sign[step] = 1;
    backtracking(step + 1);
}

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
                fin >> A[i][j];

    backtracking(1);
    fout << max_sum;

    return 0;
}