Cod sursa(job #428257)

Utilizator escu.victorPopescu Victor escu.victor Data 29 martie 2010 02:45:49
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.4 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define INF 100000
using namespace std;

int partition(vector<int> &a, vector<int> &b, int p, int r)
{
	int i, j, x;
	x = a[r];
	i = p - 1;
	for(j = p; j < r; j++)
		if(a[j] >= x)
		{
			i++;
			swap(a[i], a[j]);
			swap(b[i], b[j]);
		}
	swap(a[i+1], a[r]);
	swap(b[i+1], b[r]);	
	return (i + 1);	
}	

void quicksort(vector<int> &a, vector<int> &b, int p, int r)
{
	if(p < r)
	{
		int q = partition(a, b, p, r);
		quicksort(a, b, p, q - 1);
		quicksort(a, b, q + 1, r);
	}
}		


int main()
{
	int n, h, u;	// nr. gutui, inaltime maxima, cu cat se ridica
	int i, j, hh, ww, maxim = -INF;
	vector<int> weight, height, NrGutui, Sol;
	vector<int>::iterator it;
	
	ifstream in("gutui.in");		
	ofstream out("gutui.out");
	in >> n;
	in >> h;
	in >> u;
	
	for(i = 0; i < n; i++)
	{
		in >> hh;	height.push_back(hh);
		in >> ww;	weight.push_back(ww);
	}
	
	// sortat descrescator dupa inaltime
	quicksort(height, weight, 0, n - 1);
	
	for(i = 0; i < n; i++)
	{
		if(height[i] > h)
			Sol.push_back(-INF);
		else
		{	
			Sol.push_back(weight[i]);
			NrGutui.push_back(1);
			for(j = 0; j < i; j++)
				if( ( (height[i] + NrGutui[j] * u) <= h) && (Sol[i] <= Sol[j] + weight[i]) )
				{
					Sol[i] = Sol[j] + weight[i];
					NrGutui[i] = NrGutui[j] + 1;
				}
			if(Sol[i] > maxim)
				maxim = Sol[i];
		}	
	}
	out << maxim;
	in.close();
	out.close();
	return 0;
}