Cod sursa(job #3265596)

Utilizator RoBest69Muntean Claudiu RoBest69 Data 1 ianuarie 2025 14:00:54
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

int N, M;
vector<vector<int>> matrix;

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

    fin >> N >> M;
    matrix.resize(N, vector<int>(M));

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

    long long maxSum = 0;

    // Try all possible combinations for columns (2^M)
    for (int mask = 0; mask < (1 << M); mask++) {
        long long currentSum = 0;

        // For each row
        for (int i = 0; i < N; i++) {
            long long rowSum = 0;

            // Calculate sum for current row with current column flips
            for (int j = 0; j < M; j++) {
                int value = matrix[i][j];
                if (mask & (1 << j)) // if column j is flipped
                    value = -value;
                rowSum += value;
            }

            // Take maximum between flipped and non-flipped row
            currentSum += max(rowSum, -rowSum);
        }

        maxSum = max(maxSum, currentSum);
    }

    fout << maxSum;

    fin.close();
    fout.close();
    return 0;
}