Cod sursa(job #542825)

Utilizator c_adelinaCristescu Adelina c_adelina Data 27 februarie 2011 00:17:02
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

priority_queue <int> h;

struct nod
{long long  d,l;} v[100002];



int cmp(const nod &x,const nod &y)
{	 return x.d<=y.d; }

int main()
{
	
	long long n,i,nr=0,x,l,d=0,sol=0;
	
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%lld %lld %lld",&n,&x,&l);
	for (i=1;i<=n;++i)
	{
		scanf("%lld %lld",&v[nr+1].d,&v[nr+1].l);
		if (v[nr+1].d<=x) ++nr;
	}
	sort(v+1,v+nr+1,cmp);
	for (i=1;i<=nr&&d<=x;d+=l)
	{
		while ((i<=n) && (v[i].d<=d))
			h.push(v[i].l),++i;
		if (h.size())
		{
			sol+=h.top();
			h.pop();
		}
		
	}
	printf("%lld",sol);
	return 0;
}