Cod sursa(job #2703387)

Utilizator Nitr0genVlad Ioan Nitr0gen Data 8 februarie 2021 15:00:01
Problema Jocul Flip Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;


int n, m, a[16][16], ans = 0;
bool sol[40];


int sum() {
	int aa[16][16];

	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			aa[i][j] = a[i][j];

	for(int i = 0; i < n; i++) {
		if(sol[i]) {
			for(int j = 0; j < m; j++) {
				aa[i][j] *= -1;
			}
		}
	}

	for(int j = n; j < n + m; j++) {
		if(sol[j]) {
			for(int i = 0; i < n; i++) {
				aa[i][j - n] *= -1;
			}
		}
	}

	int sum = 0;

	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			sum += aa[i][j];

	return sum;
}


void backt(int pos) {
	if(pos == n + m) {
		ans = max(ans, sum());
		return;
	}

	for(int i = 0; i < 2; i++) {
		sol[pos] = i;
		backt(pos + 1);
	}
}


int main() {
	freopen("flip.in", "r", stdin);
	freopen("flip.out", "w", stdout);

	cin >> n >> m;

	sol[0] = 0;

	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> a[i][j];

	backt(0);

	cout << ans << '\n';
}