Cod sursa(job #3311504)

Utilizator corvinus2003Corvin Ghita corvinus2003 Data 22 septembrie 2025 19:17:52
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <iostream>
#include <fstream>

using namespace std;

void helloWorld() {

    const auto lang = "C++";
    cout << "Hello and welcome to " << lang << "!\n";

    for (int i = 1; i <= 5; i++) {

        cout << "i = " << i << endl;
    }
}

/*
 *FLIP: inmulteste linii, coloane cu -1 asa incat sa ajungi la suma cea mai mare
 *
 *problema: pot strica toate nr de pe prima linie si sa reintorc semnu la primu numar daca inmultesc
 *coloana 1
 *
 *
*/

ifstream fin;
ofstream fout;

int n, m;
//matricea de semne
int s[17][17];

int a[17][17];
//status per lin daca a fost flipped sau nu
int r[17], c[17];

int sum_max;

void update_sum() {

    //stim ca c[j] e semnul de la suma randului
    //fac de m ori suma matricei si la fiecare linie imi iese

    for (int j = 1; j <= m; ++j) {
        int sum_temp = 0;
        for (int i = 1; i <= n; ++i) {
            sum_temp += a[i][j] * r[i];
        }
        c[j] = sum_temp > 0 ? 1 : sum_temp == 0 ? 0 : -1;
    }

    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            sum += a[i][j] * r[i] * c[j];
        }
    }
    sum_max = sum > sum_max ? sum : sum_max;
}

void pb_read() {
    fin.close();
    fin.open("flip.in");
    fout.close();
    fout.open("flip.out");
}

int main() {

    fin.open("text.in");
    fout.open("text.out");
    pb_read();
    fin >> n >> m;
    //matricea de semne + prima linie pe care am macar un nr nenul
    int k = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            fin >> a[i][j];
            s[i][j] = a[i][j] > 0 ? 1 : a[i][j] == 0 ? 0 : -1;
            if (!k && a[i][j] != 0) k = i;
        }
    }
    //daca toata matricea e 0 am inchis
    if (!k) {
        fout << 0 << '\n';
        return 0;
    }
    //backtracking pentru toate combinatiile de -1 si 1 pentru r[i]
    for (int i = 0; i < (1 << n); ++i) {    //mergem de la 0 la 2^n - 1
        for (int j = 0; j < n; ++j) {       //daca bit-ul j de la i este 0 atunci il face 1 altfel 0
            r[j + 1] = (i & (1 << j)) ? -1 : 1;
        }
        update_sum();
    }

    fout << sum_max << '\n';

    return 0;
}