Cod sursa(job #1751226)

Utilizator fsx1073Alex Toma fsx1073 Data 31 august 2016 22:55:55
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <climits>

using namespace std;

int m, n, maxSum = 0, game[20][20];

inline int max(int x1, int x2) {
	return x1 > x2 ? x1 : x2;
}

void backtrack(int start) {
	// base case
	if (start == m) {
		int sum = 0;

		for (int i = 0; i < n; i++) {
			int rowSum = 0;
			for (int j = 0; j < m; j++) { 
				rowSum += game[i][j];
			}
			sum += abs(rowSum);
		}

		maxSum = max(maxSum, sum);
		return;
	}

	backtrack(start + 1);
	
	for (int i = 0; i < n; i++) {
		game[i][start] *= -1;
	}

	backtrack(start + 1);	
}

int main() {
	ifstream f("flip.in");
	ofstream g("flip.out");

	f >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			f >> game[i][j];
			maxSum += game[i][j];
		}
	}

	backtrack(0);

	g << maxSum;

	return 0;
}