Cod sursa(job #442580)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 14 aprilie 2010 20:30:05
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.18 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#define MAX 100001
using namespace std;
#include<queue>

typedef struct _gutuie{
	long int  h, g;
}gutuie;

//functia de comparare pentru sortare descrescatoare
bool compare (gutuie a, gutuie b)
{	
	return a.h>b.h;
}

int main()
{
//declarari, citiri si alocari
	FILE * in = fopen("gutui.in", "r");
	FILE * out = fopen("gutui.out", "w");
	long int N, H, U, i,x,y;
	unsigned nrgut;
	fscanf(in, "%ld %ld %ld", &N, &H, &U);

	vector<gutuie> gut (N);	
	priority_queue<long int> q;

	for(i = 0; i < N; i++)
	{
		fscanf(in,"%ld %ld", &x, &y);
		gut[i].h=x; gut[i].g=y;
	}	
	sort(gut.begin(),gut.end(),compare);

	q.push(-gut[0].g); //simulez un heap minim (maximul dintre -7 si -9 este -7, deci o sa am in coada -7, -9; cand afisez, scot minusul)
	
	for(i = 1; i < N; i++)
	{		
		nrgut = (H - gut[i].h) / U + 1;
		if(nrgut > q.size())
			q.push(-gut[i].g);
		else
		if(nrgut == q.size() && -q.top() < gut[i].g)	
		{
			q.pop();
			q.push(-gut[i].g);
		}
	}
	
	long int cont = 0;
	while(!q.empty())
	{
		cont+= -q.top();
		q.pop();
	}
	fprintf(out,"%ld\n", cont);
	return 0;
}