Cod sursa(job #1259019)

Utilizator CostinVFMI CostinVictorGabriel CostinV Data 9 noiembrie 2014 17:13:10
Problema Lupul Urias si Rau Scor 24
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 0.94 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

bool comp (pair<long, long> x, pair<long, long> y)
{
	if(x.first < y.first || x.first > y.first)
		return x.first>y.first;
	
	return x.second>y.second;
}

class compq
{
	public:
	bool operator()(pair<long, long> &x, pair<long, long> &y)
	{
		return x.second<y.second;
	}
};

int main()
{
	ifstream in ("lupu.in");
	ofstream out ("lupu.out");

	int  n;
	long cl=0, x, l, D, L, i, tm=0;
	in>>n>>x>>l;
	vector<pair<long, long> > oi;
	priority_queue <pair<long, long>, vector<pair<long, long> >, compq> que;

	for (i=0; i<n; i++)
	{
		in>>D>>L;
		if(D <= x)
		{
			oi.push_back(make_pair((x-D)/l, L));
			if ((x-D)/l > tm)
				tm = (x-D)/l;
		}

	}

	sort(oi.begin(), oi.end(), comp);

	long j=0;
	for(i=tm; i>=0; i--)
	{
		while(oi[j].first == i)
			que.push(oi[j++]);

		if(!que.empty())
		{
			cl+=que.top().second;
			que.pop();
		}
	}

	out<<cl;

	
	return 0;
}