Cod sursa(job #1319502)

Utilizator radudorosRadu Doros radudoros Data 17 ianuarie 2015 01:24:08
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 0.83 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 = n;
	int h = v[i].d;
	long long  sum = 0;
	bool ultim = 0;
	int timp = v[i].d;
	for (; timp; timp--)
	{
		while (i > 0 && v[i].d == timp)
		{
			pq.push(v[i].l);
			i--;
		}
		if (!pq.empty())
		{
			sum += pq.top();
			pq.pop();
		}
	}
	fout << sum;

}