Cod sursa(job #2745203)

Utilizator MciprianMMciprianM MciprianM Data 26 aprilie 2021 00:23:16
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <algorithm>
#include <fstream>
#include <limits>

static constexpr int MAXD = 16;

void transpose(int a[][MAXD], int n, int m)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < m; j++)
		{
			std::swap(a[i][j], a[j][i]);
		}
	}
}

int val(int a[][MAXD], int i, int j, int s)
{
	if (s & (1 << j))
	{
		return -a[i][j];
	}
	return a[i][j];
}

int get_max_sum(int a[][MAXD], int n, int m, int s)
{
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		int line_sum = 0;
		for (int j = 0; j < m; j++)
		{
			line_sum += val(a, i, j, s);
		}
		if (line_sum < 0)
		{
			line_sum = -line_sum;
		}
		sum += line_sum;
	}
	return sum;
}

int main()
{
	std::ifstream f("flip.in");
	int n, m;
	int a[MAXD][MAXD];
	f >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			f >> a[i][j];
		}
	}
	f.close();
	if (n < m)
	{
		transpose(a, n, m);
		std::swap(n, m);
	}
	int max_sum = std::numeric_limits<int>::min();
	int p = (1 << m);
	for (int s = 0; s < p; s++)
	{
		max_sum = std::max(max_sum, get_max_sum(a, n, m, s));
	}
	std::ofstream g("flip.out");
	g << max_sum << std::endl;
	return 0;
}