Cod sursa(job #1014158)

Utilizator ioanapopaPopa Ioana ioanapopa Data 22 octombrie 2013 11:20:42
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;
int compare(const void * a, const void * b)
{
	return (*(int*)a - *(int*)b);
}
class Matrice
{
	int **M, **M_duplicate;
	int n, m, r, c;
	int *viz;
	int *sol;
	int *sume;
	int s_max;
public:
	Matrice()
	{
		s_max = 0;
	}
	void Read()
	{
		ifstream f("elimin.in");
		f >> m >> n >> r >> c;
		
		if (m <= n)
		{

			M = new int*[m];
			for (int i = 0; i < m; i++)
				M[i] = new int[n];

			M_duplicate = new int*[m];
			for (int i = 0; i < m; i++)
				M_duplicate[i] = new int[n];
			for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				f >> M[i][j];
		}
		else
		{
			M = new int*[n];
			for (int i = 0; i < n; i++)
				M[i] = new int[m];

			M_duplicate = new int*[n];
			for (int i = 0; i < n; i++)
				M_duplicate[i] = new int[m];
			for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				f >> M[j][i];
			swap(n, m);
			swap(r, c);
		}


		sume = new int[n + 1];
		viz = new int[m + 1];
		sol = new int[m + 1];

		for (int i = 0; i < m; i++)
			viz[i] = 0;
		f.close();
			back(0);
	}
	void back(int k)
	{
		if (k == r)
		{
			Verificare();
			return;
		}
		else 
		for (int i = 0; i < m;i++)
		if (!viz[i] && sol[k - 1] < i)
		{
			viz[i] = 1;
			sol[k] = i;
			back(k + 1);
			viz[i] = 0;

		}
	}
	void Verificare()
	{
		for (int i = 0; i < n; i++)
			sume[i] = 0;
		for (int i = 0; i < m;i++)
			for (int j = 0; j < n; j++)
				M_duplicate[i][j] = M[i][j];
		int s=0;
		for (int i = 0; i < r; i++)
		{
			for (int j = 0; j < n; j++)
				M_duplicate[sol[i]][j] = 0;
		}
		for (int i = 0; i < n;i++)
			for (int j = 0; j < m; j++)
				sume[i] += M_duplicate[j][i];

		qsort(sume, n, sizeof(int), compare);

		for (int i = n-1; i >= c; i--)
			s+= sume[i];

		if (s>s_max)
			s_max = s;
	
	}
	void Afisare()
	{
		ofstream g("elimin.out");
		g << s_max;
		g.close();
	}
};
int main()
{
	Matrice M;
	M.Read();
	M.Afisare();
	return 0;
}