Cod sursa(job #1280181)

Utilizator A63N7pTudor Nazarie A63N7p Data 1 decembrie 2014 15:56:10
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
using namespace std;

// #define MAXS -99999999

int max_sum = -99999999;
int n, m;
int mat[20][20], sgn[20];

int getSum();
void backtrackSgn(int);

int main(int argc, char *argv[])
{
	freopen("flip.in", "r", stdin);
	freopen("flip.out", "w", stdout);
	scanf("%d %d", &n, &m);
	if (n >= m) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				scanf("%d", &mat[i][j]);
			}
		}
	} else {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				scanf("%d", &mat[j][i]);
			}
		}
		int aux = n;
		n = m;
		m = aux;
	}
	backtrackSgn(0);
	printf("%d\n", max_sum);
	return 0;
}

int getSum()
{
	int ret = 0;
	for (int i = 0; i < n; i++){
		int s = 0;
		for (int j = 0; j < m; ++j)
			s += sgn[j] * mat[i][j];
		if (s < 0)
			s *= -1;
		ret += s;
	}
	return ret;
}


void backtrackSgn(int poz)
{
	if (poz < m) {
		sgn[poz] = 1;
		backtrackSgn(poz + 1);
		sgn[poz] = -1;
		backtrackSgn(poz + 1);
	} else {
		// int currentSum = getSum();
		max_sum = getSum() > max_sum ? getSum() : max_sum;
	}
}