Cod sursa(job #463165)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 17:59:31
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.77 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#define INF 100000

using namespace std;

bool minim(int i, int j)
{
	return (i > j);
}	

int partition(int *a, int *b, int p, int r)
{
	int i, j, x, y;
	x = a[r];
	y = b[r];
	i = p - 1;
	for(j = p; j < r; j++)
		if((a[j] > x) || (a[j] == x && b[j] > y))
		{
			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(int *a,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 crengile
	int nn, hh, ww;
	int i, min;
	int *weight, *height, *NrGutui, *Sol;
	vector<int> v;
	
	ifstream in("gutui.in");		
	ofstream out("gutui.out");
	in >> nn;
	in >> h;
	in >> u;
	
	weight = (int *)malloc(nn * sizeof(int));
	height = (int *)malloc(nn * sizeof(int));
	n = 0;
	
	for(i = 0; i < nn; i++)
	{
		in >> hh;		in >> ww;	
		if(hh <= h)
		{
			height[n] = hh;
			weight[n] = ww;
			n++;
		}	
	}
	
	// Sortez descrescator perechile (inaltime, greutate) dupa inaltime
	quicksort(height, weight, 0, n - 1);
	
	Sol = (int *)malloc(n * sizeof(int));
	NrGutui = (int*)malloc(n * sizeof(int));
	

	// sol[i] = greutatea maxima ce poate fi culeasa folosind primele i gutui in ordine descrescatoare a inaltimii
	// NrGutui[i] = numarul de gutui culese din primele i gutui in ordine descrescatoare a inaltimii
	Sol[0] = weight[0];
	NrGutui[0] = 1;
	v.push_back(weight[0]);
	
	make_heap(v.begin(), v.end(), minim);
	
	for(i = 1; i < n; i++)
	{
		// Gutuia i poate fi culeasa daca
		// inaltimea initiala la care se afla gutuia + cat s-a ridicat creanga dupa ce am cules NrGutui[i] gutui ( inaltimea la care a ajuns depaseste inaltimea maxima )
		// nu depaseste inaltimea la care poate ajunge Gigel
		if((height[i] + NrGutui[i - 1] * u) <= h)
		{
			Sol[i] = Sol[i - 1] + weight[i];
			NrGutui[i] = NrGutui[i - 1] + 1;
			v.push_back(weight[i]);
			push_heap(v.begin(), v.end(), minim);
		}
		else
		{
			// Gutuia i nu poate fi culeasa
			
			NrGutui[i] = NrGutui[i - 1];
			Sol[i] = Sol[i - 1];
					
			// Incerc sa renunt la una dintre gutuile culese pana la pasul i
			// astfel incat daca as renunta la ea si ai culege gutuia i, as avea o greutate totala culeasa mai mare
			
			// Gutuia cu greutatea cea mai mica dintre gutuile culese pana la pasul i
			min = v.front();
				
			if(min < weight[i])
			{
				Sol[i] = Sol[i - 1] - min + weight[i];
				
				pop_heap(v.begin(), v.end(), minim);
				v.pop_back();
				
				v.push_back(weight[i]);
				push_heap(v.begin(), v.end(), minim);
			}
		}
	}	
		
	// Greutatea maxima ce poate fi culeasa			
	out<<Sol[n - 1];				
				
	in.close();
	out.close();
	return 0;
}