Cod sursa(job #1205344)

Utilizator alexandru.huleaAlexandru Hulea alexandru.hulea Data 6 iulie 2014 03:36:07
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>  
#include <utility> 

using namespace std;

int main() {

	int total = 0;
	ifstream in("flip.in");
	ofstream out("flip.out");
	int n,m;
	in >> n >> m;
	vector< pair<int, int > > sum;
	int* matrix = new int[m*n];
	for (int i = 0; i < n; i++) {
		int s = 0;
		for (int j = 0 ;  j< m; j++) {
			in >> matrix[i*m + j];
			s += matrix[i*m + j];
		}
		sum.push_back(make_pair(s, i));
		total += s;
	}
	for (int j = 0; j < m; j++) {
		int s = 0;
		for (int i = 0; i < n; i++) {
			s += matrix[i*m + j];
		}
		sum.push_back(make_pair(s, j + n));
		total += s;
	}

	total /= 2;
	sort(sum.begin(), sum.begin() + m + n);
	while (sum[0].first < 0) {
		total -= 2*sum[0].first;
		if (sum[0].second < n) { // flip linie
			for (int i = 1; i < n + m; i++) {
				if (sum[i].second >= n) {
					sum[i].second -= 2* matrix[sum[0].second*m+sum[i].second-n];
				}
			}
		}
		else { // flip coloana
			for (int i = 1; i < n + m; i++) {
				if (sum[i].second != -1 && sum[i].second < n) {
					sum[i].second -= 2* matrix[sum[i].second*m+sum[0].second-n];
				}
			}
		}
		sum[0].first = 0;
		sum[0].second = -1;
		sort(sum.begin(), sum.begin() + m + n);
	}

	out << total;
	in.close();
	out.close();
	return 0;
}