Cod sursa(job #2198942)

Utilizator GarboteialexGarbotei Alex Garboteialex Data 25 aprilie 2018 21:53:57
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("flip.in");
ofstream fout("flip.out");

int n,m,flip[40],Q;  // matricea flip tine 1 - 17 : linii, de la 18 -> tine coloane
int matrix[17][17];
bool used[33];
int sum,maxsum;
int initial[40],final[40];

void bkt(int poz) {
	if(poz == Q + 1) {
		maxsum = max(sum, maxsum);
		return;
	} else {
		for(int i = flip[poz - 1]; i <= n + m; i++) {
			if(!used[i]) {
				flip[poz] = i;
				sum -= initial[i];
				sum += final[i];
				used[i] = true;
				bkt(poz + 1);   //de aici in jos reinitializem tot, inclusiv suma.
				sum += initial[i];
				sum -= final[i];
				used[i] = false;
			}
		}
	}
}

int main() {
	fin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			fin >> matrix[i][j];
			sum += matrix[i][j];
		}
	}

	maxsum = sum;

	int k = 0;
	for(int i = 1; i <= n; i++) {
		k++;
		for(int j = 1; j <= m; j++) {
			initial[k] += matrix[i][j];
			final[k] += (matrix[i][j] * (-1));
		}
	}
	for(int j = 1; j <= m; j++) {
		k++;
		for(int i = 1; i <= n; i++) {
			initial[k] += matrix[i][j];
			final[k] += (matrix[i][j] * (-1));
		}
	}

	flip[0] = 1;
	for(Q = 1; Q <= n + m; Q++) {
		bkt(1);
	}

	fout << maxsum;
}