Cod sursa(job #1744040)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 19 august 2016 10:50:56
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <cstdio>
#define MAXN 20
#define inf 0x3fffffff

using namespace std;

int a[MAXN][MAXN];
int sumc[MAXN];
int n, m, sol = -inf;

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

void check()
{
    int crt = 0;
    for (int i = 1; i <= m; i++)
		crt += abs(sumc[i]);
	if (crt > sol)
		sol = crt;
}

void flip(int k)
{
    for (int j = 1; j <= m; j++) {
        a[k][j] *= -1;
        sumc[j] += a[k][j] * 2;
    }
}

void bt(int k)
{
    if (k > n) {
        check();
        return;
    }
    bt(k+1);
    flip(k);
    bt(k+1);
    flip(k);
}

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

    citire();
    bt(1);
	printf("%d", sol);

    return 0;
}