Cod sursa(job #463123)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 17:04:35
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.35 kb
#include<stdio.h>
#include<stdlib.h>
#define MAX 100001
using namespace std;
#include<queue>

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

//functia de comparare pentru sortare descrescatoare
int compare (const void* a, const void* b)
{
	if((*(gutuie*)a).h == (*(gutuie*)b).h)
		return ((*(gutuie*)a).g - (*(gutuie*)b).g);
	else 
		return -((*(gutuie*)a).h - (*(gutuie*)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;
	fscanf(in, "%ld %ld %ld", &N, &H, &U);

	gutuie *gut;
	gut = (gutuie*) malloc (sizeof(gutuie) * N);
	priority_queue<long int> q;

	for(i = 0; i < N; i++)
		fscanf(in,"%ld %ld", &gut[i].h, &gut[i].g);
		
	qsort(gut, N, sizeof(gutuie), compare);

	unsigned int nrgut = (H - gut[0].h) / U + 1;

	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)

//explic algoritmul pas cu pas in Readme	
	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);
			}

	}
//adun valorile din q
	long int cont = 0;
	while(!q.empty())
	{
//		printf("%d\n", -q.top());
		cont+= -q.top();
		q.pop();
	}
	fprintf(out,"%ld\n", cont);
	return 0;
}