Cod sursa(job #826611)

Utilizator Detrol2kGuianu Leon Detrol2k Data 30 noiembrie 2012 22:03:32
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
using namespace std;

int a[100][100], st[100], sum = -1<<30, n, m, i, j;

void computeSum()
{
	int aux[100] = {0}, auxSum = 0;
	
	for(i=1; i<=m; i++)
		for(j=1; j<=n; j++)
			aux[i] += a[j][i]*st[j];
	for(i=1; i<=m; i++)
		if(st[i] > 0)
			auxSum += aux[i];
		else
			auxSum += aux[i]*-1;
	if(auxSum > sum)
		sum = auxSum;
}

void backtracking(int k)
{
	if(k == n+1)
		computeSum();
	else
	{
		st[k] = 1;
		backtracking(k+1);
		st[k] = -1;
		backtracking(k+1);
	}
}

int main()
{
	ifstream f("flip.in");
	ofstream g("flip.out");
	
	//Read
	f>>n>>m;
	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			f>>a[i][j];
			
	//Compute
	backtracking(1);
	
	//Print
	g<<sum;
}