Cod sursa(job #3303844)

Utilizator sonosigmaAlexandru Achille Flueraru sonosigma Data 18 iulie 2025 13:00:54
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int a[16][16];

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

    fin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            fin >> a[i][j];

    int max_sum = INT32_MIN;

    // Iterăm peste toate subseturile de linii de flipat (2^n posibilități)
    for (int mask = 0; mask < (1 << n); ++mask) {
        // copiem matricea și aplicăm flip pe liniile din mască
        int temp[16][16];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                temp[i][j] = a[i][j];

        // flip liniile selectate în mask
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i)) {
                for (int j = 0; j < m; ++j)
                    temp[i][j] *= -1;
            }

        // pentru fiecare coloană, decidem dacă o flipăm sau nu
        int total = 0;
        for (int j = 0; j < m; ++j) {
            int col_sum = 0;
            for (int i = 0; i < n; ++i)
                col_sum += temp[i][j];

            // putem alege să flipăm coloana dacă suma negativă e mai mare
            total += max(col_sum, -col_sum);
        }

        max_sum = max(max_sum, total);
    }

    fout << max_sum << "\n";

    return 0;
}