Cod sursa(job #1280714)

Utilizator Iulia12345Pavel Iulia Iulia12345 Data 2 decembrie 2014 12:50:16
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
using namespace std;

// #define MAXS -99999999

int max_sum = -99999999;
int n, m;
int mat[20][20], sgn[20];

int getSum();
void backtrackSgn(int);

int main(int argc, char *argv[])
{
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);
    scanf("%d %d", &n, &m);
    if (n >= m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &mat[i][j]);
            }
        }
    } else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &mat[j][i]);
            }
        }
        int aux = n;
        n = m;
        m = aux;
    }
    backtrackSgn(0);
    printf("%d\n", max_sum);
    return 0;
}

int getSum()
{
    int ret = 0;
    for (int i = 0; i < n; i++){
        int s = 0;
        for (int j = 0; j < m; ++j)
            s += sgn[j] * mat[i][j];
        if (s < 0)
            s *= -1;
        ret += s;
    }
    return ret;
}


void backtrackSgn(int poz)
{
    if (poz < m) {
        sgn[poz] = 1;
        backtrackSgn(poz + 1);
        sgn[poz] = -1;
        backtrackSgn(poz + 1);
    } else {
        // int currentSum = getSum();
        max_sum = getSum() > max_sum ? getSum() : max_sum;
    }
}