Cod sursa(job #3278219)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 18 februarie 2025 20:03:26
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <math.h>

using namespace std;

#define NMAX 25

int bc[NMAX], solmax = 0;
int n, m, a[NMAX][NMAX], b[NMAX][NMAX];

void check() {
    for(int j = 1; j <= m; j++) {
        for(int i = 1; i <= n; i++) {
            if(bc[j] == 1) {
                b[i][j] = -a[i][j];
            }
            else {
                b[i][j] = a[i][j];
            }
        }
    }
    int sol = 0;
    for(int i = 1; i <= n; i++) {
        int sum = 0;
        for(int j = 1; j <= m; j++) {
            sum += b[i][j];
        }
        if(sum > 0) {
            sol += sum;
        }
        else {
            sol -= sum;
        }
    }

    solmax = max(solmax, sol);
}

void backtracking(int pos) {
    if(pos == m + 1) {
        check();
        return ;
    }

    for(int i = 0; i <= 1; i++) {
        bc[pos] = i;
        backtracking(pos + 1);
    }
}

int main() {
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
        }
    }

    backtracking(1);

    printf("%d\n", solmax);

    return 0;
}