Cod sursa(job #1319456)

Utilizator radudorosRadu Doros radudoros Data 17 ianuarie 2015 00:09:01
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 0.9 kb
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

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


struct duo{
	int d, l;
};
bool cmp(duo a,duo b)
{
	return (a.d > b.d || (a.d == b.d&&a.l > b.l));
}


duo v[100001];
int main()
{
	int n,x,l;
	fin >> n >> x >> l;
	int a, d;
	int aux = 0;
	for (int i = 1; i <= n; i++)
	{		
		fin >> d >> a;
		if (d <= x)
		{
			v[++aux].d = (x - d) / l + 1;
			v[aux].l = a;
		}
	}
	n = aux;
	sort(v + 1, v + n + 1,cmp);
	priority_queue<int> pq;
	int i = 1;
	int h = v[i].d;
	int pas = n;
	long long  sum = 0;
	bool ultim = 0;
	for (; pas;pas--)
	{
		while (i <= n&& v[i].d == h)
		{
			pq.push(v[i].l);
			i++;
		}
		if (i == n+1)
			ultim = 1;
		if (i <= n)
			h = v[i].d;
		if (!pq.empty())
		{
			sum += pq.top();
			pq.pop();
		}
		if (ultim)
			break;
	}
	fout << sum;

}