Cod sursa(job #3279132)

Utilizator chris2sixkPerciun Cristiano chris2sixk Data 21 februarie 2025 21:57:24
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

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

    int N, M;
    fin >> N >> M;
    
    vector<vector<int>> board(N, vector<int>(M));
    
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            fin >> board[i][j];

    int maxSum = -INF;
    
    // Parcurgem toate combina?iile de liniile care pot fi inversate (2^N posibilita?i)
    for (int mask = 0; mask < (1 << N); mask++) {
        vector<vector<int>> temp = board;
        
        // Aplicam inversarea liniilor conform bitmask-ului
        for (int i = 0; i < N; i++) {
            if (mask & (1 << i)) { // Linia i trebuie inversata
                for (int j = 0; j < M; j++) {
                    temp[i][j] *= -1;
                }
            }
        }

        // Decidem optim asupra coloanelor
        int sum = 0;
        for (int j = 0; j < M; j++) {
            int colSum = 0;
            for (int i = 0; i < N; i++) {
                colSum += temp[i][j];
            }

            // Daca suma coloanei este negativa, o inversam
            if (colSum < 0) {
                colSum *= -1;
            }

            sum += colSum;
        }

        // Actualizam suma maxima
        maxSum = max(maxSum, sum);
    }

    fout << maxSum << "\n";
    return 0;
}