Cod sursa(job #629073)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 2 noiembrie 2011 17:00:57
Problema Gutui Scor 30
Compilator cpp Status done
Runda gc_practice Marime 0.72 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, c;
	for (i=1; i<=n; i++) scanf("%d %d", &v[i].h, &v[i].g);
	sort (v+1, v+n+1, cmp);
	for (i=1; i<=n; i++) v[i].h=(h-v[i].h)/u+1;
	i=1;
	for (c=v[1].h; c>0; c--)
	{
		if (!heap.empty())
		{
			sol+=heap.top();
			heap.pop();
		}
		for (; i<=n; i++) 
			if (v[i].h<=c) heap.push(v[i].g);
	}
	if (!heap.empty()) sol+=heap.top();
	printf("%d\n",sol);
}