Cod sursa(job #2948450)

Utilizator Vasile_AndreiVasile Andrei Calin Vasile_Andrei Data 27 noiembrie 2022 18:43:05
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>

using namespace std;

constexpr size_t LIM = 18;
int N, M, i, j, mat[LIM][LIM];
int ans, st[18];

static inline void read() {
	ifstream fin("flip.in");
	fin >> N >> M;
	for (i = 1; i <= N; i++)
		for (j = 1; j <= M; j++)
			fin >> mat[i][j];
	fin.close();
}

static inline void write() {
	ofstream fout("flip.out");
	fout << ans;
	fout.close();
}

static inline void update() {
	int total = 0;
	for (j = 1; j <= M; j++) {
		int sum = 0;
		for (i = 1; i <= N; i++)
			sum += st[i] * mat[i][j];
		total += max(sum, -sum);
	}
	ans = max(total, ans);
}

static void backtracking(int k) {
	st[k] = -1;
	if (k == N) update();
	else backtracking(k + 1);

	st[k] = 1;
	if (k == N) update();
	else backtracking(k + 1);
}

int main() {
	read();
	backtracking(1);
	write();
	return 0;
}