Cod sursa(job #614242)

Utilizator capryStefan capry Data 5 octombrie 2011 21:35:48
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
# include <iostream>
# include <cstdio>
# include <vector>
# include <string>

using namespace std;

void init(const string& fname)
{	
	freopen( (fname + ".in").c_str(), "r", stdin);
	freopen( (fname + ".out").c_str(), "w", stdout);
}

int getMin(const vector<int>& vec)
{	
	int Min = 0;
	for(int i=1; i<vec.size(); ++i)
	{
		if (vec[Min] > vec[i]) Min = i;
	}
	
	return Min;
}

int main()
{
	init("flip");
	
	int N,M; cin >> N >> M;
	vector<int> line(N, 0), column(M,0);
	vector<vector<int> > table(N, vector<int>(M) );
	for(int i=0; i<N; ++i)
	{
		for(int k=0; k<M; ++k)
		{
			scanf("%d", &table[i][k]);
			line[i] += table[i][k];
			column[k] += table[i][k];			
		}
	}
	
	int l = getMin(line), c = getMin(column);
	while(line[l] < 0 || column[c] < 0)
	{
		if (line[l] < column[c])
		{
			for(int i=0; i<M; ++i)
			{
				column[i] -= table[l][i];
				table[l][i] = - table[l][i];
				column[i] += table[l][i];
			}
			line[l] = -line[l];
		}
		else
		{
			for(int i=0; i<N; ++i)
			{
				line[i] -= table[i][c];
				table[i][c] = -table[i][c];
				line[i] += table[i][c];
			}
			column[c] = -column[c];
		}
		
		l=getMin(line), c=getMin(column);
	}
	
	int sum = 0;
	for(int i=0; i<N; ++i)
	{
		for(int k=0; k<M; ++k)
		{
			sum += table[i][k];
		}
	}
	
	cout << sum;
	return 0;
}