Cod sursa(job #1985091)

Utilizator vazanIonescu Victor Razvan vazan Data 26 mai 2017 21:13:29
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <set>
#include <queue>
#include <cstring>
using namespace std;
int main(){
	set<int> s;
	int ma[20][20];
	ifstream fin("flip.in");
	ofstream fout("flip.out");
	int n, m;
	fin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			fin >> ma[i][j];
	queue <int> var;
	var.push(0);
	long long max = -(1LL << 50);
	while(!var.empty()){
		int cp;
		cp = var.front();
		long long r = 0;	
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				int t = 1;
				if( cp & (1 << (i - 1)) )
					t *= -1;
				if( cp & (1 << (16 + j - 1)) )
					t *= -1;
				r += ma[i][j] * t;
				//fout << ma[i][j] << ' ';
			}
			//fout << endl;
		}
		//fout << endl;
		if(r > max)
			max = r;
		var.pop();

		int p;
		for(int i = 0; i < n; i++){
			if( !(cp & (1 << i)) ){
				p = cp | (1 << i);
				if(s.find(p) == s.end()){
					s.insert(p);
					var.push(p);
				}
			}
		}	
		for(int i = 0; i < m; i++){
			if( !(cp & (1 << (i + 16))) ){
				p = cp | (1 << (i + 16));
				if(s.find(p) == s.end()){
					s.insert(p);
					var.push(p);
				}
			}
		}

	}
	fout << max;
	return 0;
}