Cod sursa(job #432724)

Utilizator filipbFilip Cristian Buruiana filipb Data 2 aprilie 2010 17:35:02
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.75 kb
#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

#define NMax 100005
#define t first
#define g second

int N, H, U, bst, end[NMax];
pair<int, int> v[NMax];
priority_queue<int> heap;

int main()
{
	int i, t;
	
	freopen("gutui.in", "r", stdin);
	freopen("gutui.out", "w", stdout);
	
	scanf("%d %d %d", &N, &H, &U);
	for (i = 1; i <= N; ++i)
		scanf("%d %d", &v[i].t, &v[i].g);
	sort(v+1, v+N+1);
	
	for (i = 1, end[N+1] = -1; i <= N; ++i)
		end[i] = (H-v[i].t) / U;
	
	for (i = 1; i <= N; )
	{
		for (t = end[i]; i <= N && end[i] == t; ++i)
			heap.push(v[i].g);
		
		for (t -= end[i]; t && !heap.empty(); --t)
		{
			bst += heap.top();
			heap.pop();
		}
	}

	printf("%d\n", bst);
	
	return 0;
}