Cod sursa(job #553543)

Utilizator HoriaClementHoriaC HoriaClement Data 14 martie 2011 09:45:34
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <algorithm>
#include<queue>

using namespace std;

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

ifstream in("lupu.in");
ofstream out("lupu.out");

const int N=1<<17;

int n,x,l,cost,timp;


struct lup
{
	int dist,lana;
};

lup v[N];

bool cmp(lup a,lup b)
{
	return a.dist>b.dist;
}

void lupu()
{
	timp=0;
	for(int i=1;i<=n;++i)
	{
		if(v[i].dist+timp*l<=x)
		{
			cost+=v[i].lana;
			h.push(v[i].lana);
			++timp;
		}
		else
		{
			if(!h.empty() && v[i].lana>h.top())
			{
				cost+=v[i].lana-h.top();
				h.pop();
				h.push(v[i].lana);
			}
		}
	}
	out<<cost<<"\n";
}
void rez()
{
	in>>n>>x>>l;
	for(int i=1;i<=n;++i)
		in>>v[i].dist>>v[i].lana;
	sort(v+1,v+n+1,cmp);
	lupu();
}
int main()
{
	rez();
	return 0;
}