Cod sursa(job #1262409)

Utilizator sunt_emoSunt emo sunt_emo Data 13 noiembrie 2014 10:02:29
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <vector>

std::vector<std::vector<int> > read_input()
{
	std::ifstream in("flip.in");
	int n, m;
	in >> n >> m;
	std::vector<std::vector<int> > ret(n);
	for (int i = 0; i < n; i++)
	{
		ret[i] = std::vector<int>(m);
		for (int j = 0; j < m; j++)
			in >> ret[i][j];
	}
	in.close();
	return ret;
}

void write_solution(int solution)
{
	std::ofstream out("flip.out");
	out << solution << '\n';
	out.close();
}

void compute(const std::vector<std::vector<int> > &data, std::vector<int> &coefs, int offset, std::vector<int> &sums, int &max)
{
	if (offset == coefs.size())
	{
		int s = 0;
		for (int i = 0; i < sums.size(); i++)
			s += std::max(sums[i], -sums[i]);
		max = std::max(max, s);
		return;
	}
	for (int k = -1; k <= 1; k += 2)
	{
		coefs[offset] = k;
		for (int i = 0; i < data.size(); i++)
			sums[i] += data[i][offset] * k;
		compute(data, coefs, offset + 1, sums, max);
		for (int i = 0; i < data.size(); i++)
			sums[i] -= data[i][offset] * k;
	}
}

int solution(const std::vector<std::vector<int> > &data)
{
	int max = -1000000000;
	std::vector<int> coefs(data[0].size(), -1), sums(data.size(), 0);
	compute(data, coefs, 0, sums, max);
	return max;
}

int main()
{
	std::vector<std::vector<int> > data = read_input();
	write_solution(solution(data));
}