Cod sursa(job #1514375)

Utilizator tudorcomanTudor Coman tudorcoman Data 31 octombrie 2015 09:25:49
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M;
long long maxSum;
int mat[20][20], aux[20][20];

long long computeSum() {
	long long Ans = 0;
	for(register int i = 1; i <= N; ++ i)
		for(register int j = 1; j <= M; ++ j)
			Ans += aux[i][j];
	return Ans;
}

void comuteCol(int col) {
	for(register int i = 1; i <= N; ++ i)
		aux[i][col] *= -1;
}

void comuteLine(int lin) {
	for(register int i = 1; i <= M; ++ i)
		aux[lin][i] *= -1;
}

void Combinations(int n, int k, int size = 0, int last = 0, int inComb = 0) {
	if(size == k) {
		for(register int i = 1; i <= n; ++ i)
			if(inComb & (1 << i)) {
				if(i > M) comuteLine(i - M);
				else comuteCol(i);
				//fprintf(stderr, "%d ", i);
			}
		//fprintf(stderr, "\n");
		maxSum = max(maxSum, computeSum());
		memcpy(aux, mat, sizeof(mat));
	} else {
		for(register int i = last + 1; i <= n; ++ i)
			Combinations(n, k, size + 1, i, inComb xor (1 << i));
	}
}

void backtracking() {
	memcpy(aux, mat, sizeof(mat));
	// for(register int i = 1; i <= N; ++ i, fprintf(stderr, "\n"))
	// 	for(register int j = 1; j <= M; ++ j)
	// 		fprintf(stderr, "%d ", aux[i][j]);

	maxSum = computeSum();
	for(register int i = 1; i <= N + M; ++ i)
		Combinations(N + M, i);
}

int main(void) {
	freopen("flip.in", "r", stdin);
	freopen("flip.out", "w", stdout);
	scanf("%d %d", &N, &M);
	for(register int i = 1; i <= N; ++ i)
		for(register int j = 1; j <= M; ++ j)
			scanf("%d", &mat[i][j]);
	backtracking();
	printf("%lld\n", maxSum);
	return 0;
}