Cod sursa(job #717069)

Utilizator rayvianPricope Razvan rayvian Data 19 martie 2012 17:09:44
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <fstream>
#include <bitset>
#include <iostream>
#include <cmath>
using namespace std;
bitset<16> what_to_flip;
/** This is where our elements will be stored */
int matrix[16][16]; 
int lin,col;

ostream& operator << (ostream &out,const bitset<16> &bit)
{
	out<<bit.to_string<char,char_traits<char>,allocator<char> >();
	return out;
}

void add_1()
{
	int i=0;
	while(what_to_flip[i]==1)
		what_to_flip[i++]=0;
	what_to_flip[i]=1;
}


inline void flip_line(int line)
{
	for(int i=0; i<col; i++)
		matrix[line][i]*=(-1);
}
inline int get_sum()
{
	int sum=0;
	for(int i=0; i<lin; i++)
		for(int j=0; j<col; j++)
			sum+=matrix[i][j];
	return sum;
}

/** Will traverse every column and check if sum is negative. If it is negative, flip the column and add the result
		@param this_sum - sum calculated without flipping columns
		@return - maximum sum for this configuration
*/
inline int get_minimum_sum(int this_sum)
{
	for(int i=0; i<col; i++)
	{
		int sumcol=0;
		for(int j=0; j<lin; j++)
			sumcol+=matrix[j][i];
		if(sumcol<0)
		{
			this_sum-=sumcol;
			sumcol*=-1;
			this_sum+=sumcol;
		}
	}
	return this_sum;
}

int main()
{
	ifstream fin("flip.in");
	ofstream fout("flip.out");
	fin>>lin>>col;
	/** Maximum sum is here */
	int summax=0x80000000; 

	for(int i=0; i<lin; i++)
		for(int j=0; j<col; j++)
			fin>>matrix[i][j];
	int flips=pow(2,lin);
	
	/** We now make flips to these lines*/
	for(int i=0; i<flips; i++)
	{
		/**Flip the specified lines*/
		for(int i=0; i<lin; i++)
			if(what_to_flip[i]==1)
				flip_line(i);

		int temp_sum=0;
		temp_sum=get_sum();	
		temp_sum=get_minimum_sum(temp_sum);
		if(temp_sum>summax)
			summax=temp_sum;
		
		/** Flip them back */
		for(int i=0; i<lin; i++)
			if(what_to_flip[i]==1)
				flip_line(i);
		add_1();
	}
	fout<<summax;
	return 0;
}