Cod sursa(job #1736031)

Utilizator tavy14tIlie Octavian tavy14t Data 31 iulie 2016 22:18:46
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <bitset>
#include <limits.h>
#include <fstream>
using namespace std;

ifstream fin("flip.in");
ofstream fout("flip.out");
int n, m, a[16][16], maxSum = INT_MIN;
bitset<16> selected;

void readInput()
{
	fin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			fin >> a[i][j];
}

void reverseSelectedLines()
{
	for (int i = 0; i < n; i++)
		if (selected[i] == 1)
			for (int j = 0; j < m; j++)
				a[i][j] *= -1;
}

int computeSum()
{
	int result = 0;
	reverseSelectedLines();

	for (int j = 0; j < m; j++)
	{
		int sum = 0;
		for (int i = 0; i < n; i++)
			sum += a[i][j];

		if (sum < 0)
			result += -sum;
		else
			result += sum;
	}

	reverseSelectedLines();
	return result;
}

void back(int lvl)
{
	if ( lvl == n-1 )
	{
		int newSum = computeSum();
		if (maxSum < newSum)
			maxSum = newSum;
	}
	else
	{
		selected[lvl] = 0;
		back(lvl + 1);

		selected[lvl] = 1;
		back(lvl + 1);
	}	
}

int main()
{
	readInput();

	back(0);

	fout << maxSum;
}