Cod sursa(job #553524)

Utilizator ioanabIoana Bica ioanab Data 14 martie 2011 09:39:13
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

priority_queue<int,vector<int>,greater<int> > h;

/*	priority_queue<pair<int,int> > h;
	priority_queue<int> h;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int > > > h;
*/

struct oaie
{
	int x,l;
};

const int N=100010;
int x[N];
int l[N];
oaie v[N];

int cmp(oaie a,oaie b)
{
	return a.x>b.x;
}

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	int n,X,L,i,t;
	long long cost=0;
	scanf("%d%d%d",&n,&X,&L);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&v[i].x,&v[i].l);
	}
	sort(&v[1],&v[n+1],cmp);
	t=0;
	for(i=1;i<=n;i++)
	{
		if(v[i].x+t*L<=X)
		{
			cost+=v[i].l;
			h.push(v[i].l);
			t++;
		}
		else
			if(v[i].l>h.top() && !h.empty())
			{
				cost-=h.top();
				h.pop();
				h.push(v[i].l);
				cost+=v[i].l;
			}
		
	}
		
	printf("%lld\n",cost);
	return 0;
}