Cod sursa(job #2832781)

Utilizator daniel23Malanca Daniel daniel23 Data 14 ianuarie 2022 11:55:29
Problema Jocul Flip Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>

int n, m;
int arr[16][16];
int max;
int count = 0;
std::ifstream in("flip.in");
std::ofstream out("flip.out");

bool com[2][16];

void solve(int sum) {
    if (sum > max) max = sum;
    int schimbat[32];
    int l = 0;

    for (int i=0; i<n; i++) {
        if (com[0][i]) continue;

        int s = 0;
        for (int j=0; j<m; j++)
            s += arr[i][j];
        
        if (s < 0) {
            if (sum - 2*s <= max);
            for (int j=0; j<m; j++)
                arr[i][j] *= -1;   
            com[0][i] = 1;
            schimbat[l++] = i;
            solve(sum - 2*s);
            for (int j=0; j<m; j++)
                arr[i][j] *= -1;
        }

    }

    for (int i=0; i<m; i++) {
        if (com[1][i]) continue;

        int s = 0;
        for (int j=0; j<n; j++)
            s += arr[j][i];
        
        if (s < 0) {
            for (int j=0; j<n; j++)
                arr[j][i] *= -1;
            com[1][i] = 1;
            schimbat[l++] = 16 + i;
            solve(sum - 2*s);
            for (int j=0; j<n; j++)
                arr[j][i] *= -1;
        }

    }

    for (int i=0; i<l; i++) {
        (*(com[0] + schimbat[i])) = 0;
    }
}

int main() {
    in >> n >> m;

    int sum = 0;

    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            in >> arr[i][j],
            sum += arr[i][j];
            
    max = sum;
    solve(sum);

    out << max;
}