Cod sursa(job #2832606)

Utilizator daniel23Malanca Daniel daniel23 Data 13 ianuarie 2022 23:01:33
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>

int n, m;
int arr[16][16];
int max = INT32_MIN;

std::ifstream in("flip.in");
std::ofstream out("flip.out");

bool com[2][16];

void solve(int sum, int k) {
    if (k > 2) return;
    if (sum > max) max = sum;

    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) k++;
            for (int j=0; j<m; j++)
                arr[i][j] *= -1;   
            com[0][i] = 1;
            solve(sum - 2*s, k);
            com[0][i] = 0;
            for (int j=0; j<m; j++)
                arr[i][j] *= -1;
            k--;
        }

    }

    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) {
            if (sum - 2*s < max) k++;
            for (int j=0; j<n; j++)
                arr[j][i] *= -1;
            com[1][i] = 1;
            solve(sum - 2*s, k);
            com[1][i] = 0;
            for (int j=0; j<n; j++)
                arr[j][i] *= -1;
            k--;
        }

    }
}

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];

    solve(sum,0);

    out << max;
}