Cod sursa(job #1320212)

Utilizator vld7Campeanu Vlad vld7 Data 17 ianuarie 2015 18:35:54
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 0.91 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream in ("flip.in");
ofstream out ("flip.out");

int N, M, ans;
int A[20][20];
bool line[20];
int sum[20];

int go() {
	int Ret = 0;
	
	memset (sum, 0, sizeof(sum));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (line[i])
				sum[j] -= A[i][j];
			else
				sum[j] += A[i][j];
			
	for (int i = 0; i < M; i++)
		Ret += max (sum[i], -sum[i]);
	
	return Ret;
}

int main() {
	in >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			in >> A[i][j];
			ans += A[i][j];
		}
		
	int max_conf = (1 << N);
	for (int conf = 0; conf < max_conf; conf++) {
		for (int bit = 0; bit < N; bit++)
			if ((1 << bit) & conf)
				line[bit] = true;
		ans = max (ans, go());
		for (int bit = 0; bit < N; bit++)
			if ((1 << bit) & conf)
				line[bit] = false;
	}
	
	out << ans;
	
	return 0;
}