Cod sursa(job #3251716)

Utilizator RoBest69Muntean Claudiu RoBest69 Data 26 octombrie 2024 16:30:06
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

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

int N, M;
vector<vector<int>> table;
long long maxSum = 0;

void solve() {
    // For each column, we'll determine if it's better to flip it
    for (int j = 0; j < M; j++) {
        // Count positive and negative sums for this column after row flips
        long long posSum = 0, negSum = 0;
        for (int i = 0; i < N; i++) {
            // If the element is already positive after row flips, add to posSum
            // otherwise add to negSum
            if (table[i][j] > 0) {
                posSum += table[i][j];
                negSum -= table[i][j];
            }
            else {
                posSum -= table[i][j];
                negSum += table[i][j];
            }
        }
        // Choose the better sum for this column
        maxSum += max(posSum, negSum);
    }
}

int main() {
    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];
        }
    }

    // First, make all rows have maximum absolute values
    for (int i = 0; i < N; i++) {
        int negCount = 0;
        for (int j = 0; j < M; j++) {
            if (table[i][j] < 0) negCount++;
        }
        // If more than half elements are negative, flip the row
        if (negCount > M / 2) {
            for (int j = 0; j < M; j++) {
                table[i][j] *= -1;
            }
        }
    }

    solve();
    fout << maxSum;

    return 0;
}