Cod sursa(job #432673)

Utilizator filipbFilip Cristian Buruiana filipb Data 2 aprilie 2010 16:51:55
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.99 kb
#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

#define NMax 100005
#define PII pair<int, int>
#define t first
#define g second

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

bool operator< (const PII& a, const PII& b)
{
	return (H-a.t) / U > (H-b.t) / U;
}

int main()
{
	int i, j;
	
	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; ++i)
	{
		// adaugam in heap costurile noilor intervale
		for (j = i; j <= N && end[i] == end[j]; ++j)
			heap.push(v[j].g);
		i = j-1;
		
		// scoatem din heap pana la intalnirea unui nou eveniment
		for (j = end[j-1] - end[j]; j && !heap.empty(); --j)
		{
			bst += heap.top();
			heap.pop();
		}
	}

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