Cod sursa(job #464144)

Utilizator bora_marianBora marian bora_marian Data 18 iunie 2010 22:29:04
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#define DN 100001
using namespace std;

struct oaie {
	long long dist,cant;
}o[DN];

int  cmp(const oaie& a,const  oaie& b) { return (a.dist<b.dist); }

int main()
{
	long long n,x,l,i,dales,sol=0,val;
	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",&o[i].dist,&o[i].cant);
	sort(o+1,o+n+1,cmp);
	priority_queue<long long> heap;
	for(dales=0,i=1; dales<=x; dales+=l) {
        for(i=i; i<=n && o[i].dist<=dales; i++) heap.push(o[i].cant);
        if(!heap.empty()) {
            val=heap.top();
            sol+=val;
            heap.pop();
        }
    }
	printf("%lld\n",sol);
	return 0;
}