Cod sursa(job #1985103)

Utilizator vazanIonescu Victor Razvan vazan Data 26 mai 2017 21:37:31
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 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, col;	
		for(int j = 1; j <= m; j++){
			col = 0;
			int t;
			for(int i = 1; i <= n; i++){
				t = 1;
				if( cp & (1 << (i - 1)) )
					t = -1;
				col += ma[i][j] * t;
			}
			if(col < 0)
				col *= -1;
			r += col;
		}
		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);
				}
			}
		}
	}
	fout << max;
	return 0;
}