Cod sursa(job #651166)

Utilizator eduEduard Gabriel Bazavan edu Data 19 decembrie 2011 23:17:58
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>

#include <bitset>

using namespace std;

#define MAX 16

bitset<2*MAX> bits;

int64_t max_sum = -256000000;
int32_t A[16][16];
int N, M;


void generate(int k) {
	if (k == N+M) {
		int64_t sum = 0;
		for (int i=0; i < N; i++) {
			for (int j=0; j < M; j++) {
				
				int32_t epsilon=1;
				/*
				// Rather slow 
				if (bits.test(i) == true) {
					epsilon *= -1;
				} 
				if (bits.test(N+j) == true) {
					epsilon *= -1;
				}
				*/
				epsilon = epsilon * (-2*bits[i] + 1) * (-2*bits[N+j] + 1);
				
				sum += epsilon*A[i][j];
			}
		}
		if (sum > max_sum) {
			max_sum = sum;
		}
		return;
	}

	bits.set(k, 1);
	generate(k+1);
	bits.set(k, 0);
	generate(k+1);
}


int main() {

	freopen("flip.in", "rt", stdin);
	freopen("flip.out", "wt", stdout);

	scanf("%d %d\n", &N, &M);
	for (int i=0; i < N; i++) {
		for (int j=0; j < M; j++) {
		scanf("%d", &A[i][j]);
		}
	}

	generate(0);

	printf("%lld\n", max_sum);

	fclose(stdin);
	fclose(stdout);

	return 0;
}