Cod sursa(job #555775)

Utilizator RegeleUmbrelorPopescu Mihai RegeleUmbrelor Data 15 martie 2011 19:23:50
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 100005;

//priority_queue<int> h;
priority_queue<int,vector<int>,greater<int> > h;
struct oaie
{
	int lana,dist;
};

oaie v[N];

int n,r,d;

void citire()
{
	scanf("%d%d%d",&n,&r,&d);
	for(int i=1 ; i<=n ; i++)
		scanf("%d%d",&v[i].dist,&v[i].lana);
}

bool cmp(oaie x,oaie y)
{
	if(x.dist>y.dist)
		return true;
	if(x.dist<y.dist)
		return false;
	return x.lana<y.lana;
}

long long calcul()
{
	long long dist = 0,total = 0;
	for(int i=1 ; i<=n ; i++)
	{
		if(v[i].dist + dist <= r)
		{
			total += v[i].lana;
			h.push(v[i].lana);
			dist += d;
			continue;
		}
		if(!h.empty() && v[i].lana > h.top())
		{
			total += v[i].lana - h.top();
			h.pop();
			h.push(v[i].lana);
		}
	}
	return total;
}

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	citire();
	sort(&v[1],&v[n+1],cmp);
	printf("%lld\n",calcul());
	return 0;
}