Cod sursa(job #651158)

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

#include <bitset>

using namespace std;

#define MAX 16

bitset<2*MAX> bits;

int64_t max_sum = -256000000;

void generate(int k, int32_t A[16][16], int32_t N, int32_t M) {
	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;
				if (bits.test(i) == true) {
					epsilon *= -1;
				} 
				if (bits.test(N+j) == true) {
					epsilon *= -1;
				}

				sum += epsilon*A[i][j];
			}
		}
		if (sum > max_sum) {
			max_sum = sum;
		}
		return;
	}

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


int main() {

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

	int32_t N, M;
	int32_t A[MAX][MAX];

	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, A, N, M);

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

	fclose(stdin);
	fclose(stdout);

	return 0;
}