Cod sursa(job #2204391)

Utilizator memecoinMeme Coin memecoin Data 15 mai 2018 17:45:16
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

#define MAXN 17

int board[MAXN][MAXN];
bool flips[MAXN];

int n, m;

int globalBest = 0;

int boardSum() {
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		int partialSum = 0;
		for (int j = 0; j < m; ++j) {
			partialSum += board[i][j] * (flips[j] ? 1 : -1);
		}
		sum += abs(partialSum);
	}
	return sum;
}

void solve(int lastIndex) {
	if (lastIndex == m) {
		globalBest = max(globalBest, boardSum());
		return;
	}
	
	flips[lastIndex] = false;
	solve(lastIndex + 1);
	flips[lastIndex] = true;
	solve(lastIndex + 1);
}

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

	scanf("%d %d", &n, &m);

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

	solve(0);
	printf("%d", globalBest);

	return 0;
}