Cod sursa(job #789887)

Utilizator ady8raduRadu Adrian Leonard ady8radu Data 19 septembrie 2012 18:37:49
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#define DIM 16
#define MAX_DIM 1000001

struct MPos
{
	int min, pos;

	MPos(int min, int pos):min(min), pos(pos) {}
};

inline MPos findMin(int v[], int n)
{
	MPos res(MAX_DIM, 0);
	for(int i = 0; i < n; ++i) {
		if (v[i] < res.min) {
			res.min = v[i];
			res.pos = i;
		}
	}

	return res;
}

int main(void)
{
	std::ifstream f("flip.in");
	std::ofstream g("flip.out");

	int N, M, sum = 0, dim;
	int a[DIM][DIM], *sums;
	MPos minim(-1, -1);

	f >> N >> M;
	dim = M + N;

	sums = new int[N + M];

	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < M; ++j) {
			f >> a[i][j];
			sums[i] += a[i][j];
			sums[N + j] += a[i][j];
		}
		sum += sums[i];
	}

	minim = findMin(sums, dim);

	while(minim.min < 0) {
		if(minim.pos < N) {
			for (int j = 0; j < M; ++j) {
				int aux = a[minim.pos][j];	
				a[minim.pos][j] *= -1;
				int diff = a[minim.pos][j] - aux;
				sums[N + j] += diff;
				sums[minim.pos] += diff;
				sum += diff;
			}
		} else {
			for (int i = 0; i < N; ++i) {
				int pos = minim.pos - N;
				int aux = a[i][pos];
				a[i][pos] *= -1;
				int diff = a[i][pos] - aux;
				sums[N + pos] += diff;
				sums[i] += diff;
				sum += diff;
			}
		}
		minim = findMin(sums, dim);
	}

	g << sum;

	return 0;
}