Cod sursa(job #651202)

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

#include <bitset>

using namespace std;

#define MAX 16

bitset<2*MAX> bits;

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


void generate(int k) {
	if (k == N) {
		
		int32_t sum = 0;

		for (int j=0; j < M; j++) {
			
			int32_t column_sum = 0;
			for (int i=0; i < N; i++) {
				column_sum += (-2*bits[i]+1)*A[i][j];
			}
			if (column_sum < 0)
				sum -= column_sum;
			else
				sum += column_sum;
		}

		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);
	
	/*
	printf("16 16\n");
	for (int i=0; i < 16; i++) {
		for (int j = 0; j < 16; j++) {
			printf("%d ", (-2 * (i%2) + 1) * i);
		}
		printf("\n");
	}
	return 0;
	*/

	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("%d\n", max_sum);

	fclose(stdin);
	fclose(stdout);

	return 0;
}