Cod sursa(job #3251715)

Utilizator RoBest69Muntean Claudiu RoBest69 Data 26 octombrie 2024 16:28:55
Problema Jocul Flip Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int N, M;
vector<vector<int>> table;
long long maxSum = -1e18;

void calculateSum() {
    vector<vector<int>> temp = table;
    long long currentSum = 0;
    
    // Try all possible combinations of row flips (2^N possibilities)
    for (int rowMask = 0; rowMask < (1 << N); rowMask++) {
        // Try all possible combinations of column flips (2^M possibilities)
        for (int colMask = 0; colMask < (1 << M); colMask++) {
            // Reset the temporary table
            temp = table;
            
            // Flip rows according to rowMask
            for (int i = 0; i < N; i++) {
                if (rowMask & (1 << i)) {
                    for (int j = 0; j < M; j++) {
                        temp[i][j] *= -1;
                    }
                }
            }
            
            // Flip columns according to colMask
            for (int j = 0; j < M; j++) {
                if (colMask & (1 << j)) {
                    for (int i = 0; i < N; i++) {
                        temp[i][j] *= -1;
                    }
                }
            }
            
            // Calculate sum for current configuration
            currentSum = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    currentSum += temp[i][j];
                }
            }
            
            maxSum = max(maxSum, currentSum);
        }
    }
}

int main() {
    // Read input
    fin >> N >> M;
    table.resize(N, vector<int>(M));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            fin >> table[i][j];
        }
    }
    
    // Find maximum possible sum
    calculateSum();
    
    // Write output
    fout << maxSum;
    
    return 0;
}