Cod sursa(job #3036426)

Utilizator adelina_15InfoAdelina Radoi adelina_15Info Data 24 martie 2023 12:18:27
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <cmath>

using namespace std;

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

vector<int> submultime;
int n, m, sol = INT_MIN;
int a[20][20];

void flip_linie(int lin)
{
    for(int i = 1; i <= m; i++)
        a[lin][i] *= -1;
}

void backtracking(int lin)
{
    if(lin == n)
    {
        for(int i = 0; i < submultime.size(); i++)
            flip_linie(submultime[i]);
        int total = 0;
        for(int j = 1; j <= m; j++)
        {
            int sumCol = 0;
            for(int i = 1; i <= n; i++)
                sumCol += a[i][j];
            total += abs(sumCol);
        }
        sol = max(sol, total);
        for(int i = 0; i < submultime.size(); i++)
            flip_linie(submultime[i]);
        return;
    }
    submultime.push_back(lin);
    backtracking(lin+1);
    submultime.pop_back();
    backtracking(lin+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 << sol;
    return 0;
}