Cod sursa(job #1019476)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 31 octombrie 2013 09:59:04
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>


const static int NMAX = 7294;

using namespace std;

int nr_linii , nr_coloane , matrix[NMAX][NMAX];
int R , C;

int solutie[NMAX];

int sum_linii[NMAX] , aux_sum_linii[NMAX];
int sum_matrix = 0;
int max_suma = -1;

ifstream input("elimin.in");
ofstream output("elimin.out");


void backtrack(int pos)
{
	if (pos > C)
	{
		int sum = 0;
		
		memset(aux_sum_linii , 0 , sizeof(int) * nr_linii);

		for (int j = 1;j<pos;j++)
			for (int i = 0;i<nr_linii;i++)
			{
				sum += matrix[i][solutie[j]];
				aux_sum_linii[i] += matrix[i][solutie[j]];
			}
		for (int i = 0;i<nr_linii;i++)
			aux_sum_linii[i] = sum_linii[i] - aux_sum_linii[i];

		sort(aux_sum_linii , aux_sum_linii + nr_linii);

		for (int i = 0;i<R;i++)
			sum += aux_sum_linii[i];

		if (sum_matrix - sum > max_suma)
			max_suma = sum_matrix - sum;		

	}
	else
	{
		for (int i = solutie[pos-1] + 1;i<nr_coloane;i++)
		{
			solutie[pos] = i;
			backtrack(pos+1);
		}
	}
}



int main(int argc , char ** argv)
{
	input >> nr_linii >> nr_coloane >> R >> C;

	if (nr_linii > nr_coloane)
	{

		for (int i = 0;i<nr_linii;i++)
			for (int j = 0;j<nr_coloane;j++)
				input >> matrix[i][j];
	}
	else
	{
		for (int i = 0;i<nr_linii;i++)
			for (int j = 0;j<nr_coloane;j++)
				input >> matrix[j][i];

		swap(nr_linii , nr_coloane);
		swap(R , C);
	}


	int sum = 0;
	for (int i = 0;i<nr_linii;i++)
	{
		sum = 0;
		for (int j = 0;j<nr_coloane;j++)
		{
			sum_matrix += matrix[i][j];
			sum += matrix[i][j];
		}
		sum_linii[i] += sum;
	}


	solutie[0] = -1;

	backtrack(1);

	output << max_suma;

	input.close();
	output.close();

	return 0;
}