Cod sursa(job #234663)

Utilizator mist000000 mist Data 21 decembrie 2008 16:41:22
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>

using namespace std;

int main()
{
	int M, N;
	ifstream in("flip.in");
	in>>M>>N;

	long *tabla = new long[M * N];
	long *colSum = new long[max(M, N)];

	for (int i = 0; i < max(M, N); i++)
		colSum[i] = 0;

	// if M > N transpose matrix
	// we check 2^M line flips, so it should matter
	if (M < N) {
		for (int i = 0; i < M; i++)
			for (int j = 0; j < N; j++) {
				long val;
				in >> val;
				colSum[j] += val;
				tabla[i * N + j] = 2 * val;
			}
	} else {
		for (int j = 0; j < M; j++)
			for (int i = 0; i < N; i++) {
				long val;
				in >> val;
				colSum[j] += val;
				tabla[i * M + j] = 2 * val;
			}

		int tmp = M;
		M = N;
		N = tmp;
	}

	in.close();

	bool *flipLine = new bool[M], *flipCol = new bool[N];
	for (int i = 0; i < M; i++)
		flipLine[i] = false;
	for (int i = 0; i < N; i++)
		flipCol[i] = false;

	long maxSum;
	long crtSum;
	bool firstRun = true;

	do {
		// add column sums (absolute value)
		crtSum = 0;
		for (int i = 0; i < N; i++) {
			crtSum += abs(colSum[i]);
		}

		// compare crtSum with maxSum
		if (firstRun || crtSum > maxSum) {
			firstRun = false;
			maxSum = crtSum;
		}

		// increment flipLine binary number
		int crtLine = M - 1;
		bool transport = true;
		while (crtLine >= 0 && transport) {
			flipLine[crtLine] = !flipLine[crtLine];
			if (flipLine[crtLine]) {
				transport = false;
				for (int j = 0; j < N; j++)
					colSum[j] -= tabla[crtLine * N + j];
			}
			else {
				for (int j = 0; j < N; j++)
					colSum[j] += tabla[crtLine * N + j];
			}
			crtLine--;
		}
		if (crtLine < 0 && transport)
			break;
	} while (true);

	ofstream out("flip.out");
	out << maxSum << endl;
	out.close();

	return 0;
}