Cod sursa(job #629131)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 2 noiembrie 2011 18:02:39
Problema Gutui Scor 100
Compilator cpp Status done
Runda gc_practice Marime 0.73 kb
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define nmax 100010

priority_queue <int> heap;

struct gutui
{
	int h, g;
} v[nmax];

int n, h, u, sol;

int cmp(gutui x, gutui y)
{
	return x.h<y.h;
}

int main()
{
	freopen("gutui.in","r",stdin);
	freopen("gutui.out","w",stdout);
	scanf("%d %d %d",&n, &h, &u);
	int i, k;
	for (i=1; i<=n; i++) scanf("%d %d", &v[i].h, &v[i].g);
	sort (v+1, v+n+1, cmp);
	k=h;
	while (k-u>=v[1].h) k-=u;
	i=1;
	while (1)
	{
		if (v[i].h>k || i>n)
		{
			if (!heap.empty())
			{
			sol+=heap.top();
			heap.pop();
			}
			k+=u;
			if (k>h) break;
		} 
		if (v[i].h<=k && i<=n)
		{
			heap.push(v[i].g);
			i++;
		}
	}
	printf("%d\n",sol);
}