Cod sursa(job #1727891)

Utilizator vladc096Vlad Cincean vladc096 Data 11 iulie 2016 20:40:54
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
//#include <limits>

using namespace std;

short n, m;

inline int sum(int** a, int b) {
	int ret = 0;
	for (int i = 0; i < n; i++) {
		int lineSum = 0; // sum of current line
		for (int j = 0; j < m; j++) {
			lineSum += (b & (1 << j)) ? -a[i][j] : a[i][j]; // is there a flip of column j?
		}
		ret += lineSum > 0 ? lineSum : -lineSum; // if lineSum is negative, then a flip on it would maximize de sum
	}
	return ret;
}

int main() {
	// input
	ifstream f("flip.in");
	f >> n >> m;
	int** a = new int*[n];
	for (int i = 0; i < n; i++) {
		a[i] = new int[m];
		for (int j = 0; j < m; j++) {
			f >> a[i][j];
		}
	}
	f.close();

	// solve
	int maxSum = INT_MIN;
	// generate all flip/no-flip states for columns
	for (int b = 0; b < (1 << m); b++) {
		int s = sum(a, b); // get sum of current configuration
		if (s > maxSum) {
			maxSum = s;
		}
	}

	// output
	ofstream g("flip.out");
	g << maxSum << "\n";
	g.close();

	// deallocate
	for (int i = 0; i < n; i++) {
		delete[] a[i];
	}
	delete[] a;

	return 0;
}