Cod sursa(job #3367411)

Utilizator daviddxmqStan David Andrei daviddxmq Data 7 octombrie 2026 17:09:28
Problema Jocul Flip Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 20;

int mat[MAXN][MAXN];
int sumaComutare[2 * MAXN];
vector<int> comutLin;
int n, m;
long long sumMax = -1e18, suma;

void flip(int pas, long long sum) {
    if (pas == n + m) {
        if (sumMax < sum)
            sumMax = sum;
        return;
    }

    flip(pas + 1, sum);

    if (pas < n) {
        comutLin.push_back(pas);
        sumaComutare[pas] = -sumaComutare[pas];
        flip(pas + 1, sum + 2 * sumaComutare[pas]);
        sumaComutare[pas] = -sumaComutare[pas];
        comutLin.pop_back();
    }
    else {
        int col = pas - n;
        for (int i : comutLin)
            sumaComutare[pas] -= 2 * mat[i][col];

        sumaComutare[pas] = -sumaComutare[pas];

        flip(pas + 1, sum + 2 * sumaComutare[pas]);

        sumaComutare[pas] = -sumaComutare[pas];
        for (int i : comutLin)
            sumaComutare[pas] += 2 * mat[i][col];
    }
}

int main() {
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);

    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> mat[i][j];
            sumaComutare[i] += mat[i][j];
            suma += mat[i][j];
        }
    }

    for (int j = 0; j < m; ++j)
        for (int i = 0; i < n; ++i)
            sumaComutare[n + j] += mat[i][j];

    flip(0, suma);

    cout << sumMax;

    return 0;
}