Cod sursa(job #1167640)

Utilizator Kerriganamihut Kerrigan Data 5 aprilie 2014 16:36:33
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
/******************************************************************************************
*           .--.																		  *
* ::\`--._,'.::.`._.--'/::			@author Ana M. Mihut	@course InfoArena Tryout	  *
* ::::. `  __::__ ' .:::::			@alias  LT-Kerrigan		@date   05.04.2014			  *
* ::::::-:.`'..`'.:-::::::			@link   http://infoarena.ro/problema/flip		      *
* ::::::::\ `--' /::::::::			@detail Flip Game on an NxM board					  *
*																						  *
*******************************************************************************************/

#include <iostream>
#include <fstream>
#include <algorithm>

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

int n, m;
long smax, a[20][20], sc[20];

void Computation(){
	long num, sum = 0;
	
	for (int i = 1; i <= n; i++) {
		num = 0;
		
		for (int j = 1; j <= m; j++)
			num += a[i][j] * sc[j];

		sum = sum + std::max(num, -num);
	}
	
	smax = std::max(smax, sum);
}

void BK(int k)
{
	if (k == m+1){
		Computation(); 
		return; 
	}

	sc[k] = -1;
	BK(k + 1);
	sc[k] = 1;
	BK(k + 1);
}

int main(){
	in >> n >> m;
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			in >> a[i][j];
	
	BK(1);
	
	out << smax;
	return 0;
}