Cod sursa(job #821200)

Utilizator axnsanCristi Vijdea axnsan Data 21 noiembrie 2012 21:04:56
Problema Lupul Urias si Rau Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
//#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
struct oaie { 
	int d,p; 
} oi[100010];
void qsort (oaie *v, int li, int ls);
//void adg(int *v, int &n, int x);
//int extr(int *v, int &n);
int main()
{
	int n,x,l,a;
	long long s(0);
	ifstream f("lupu.in");
	f >> n >> x >> l;
	for (int i = 1;i <= n;++i)
	{
		f >> a >> oi[i].p;
		oi[i].d = (x-a)/l + 1;
	}
	qsort(oi,1,n);
	/*for (int i = 1;i <= n;++i)
		cout << oi[i].d << " " << oi[i].p << endl;
	cout << endl;*/

	priority_queue<int> fav;
	int /*fav[100010], k(0),*/ pas(oi[1].d), i(1);
	while (pas)
	{
		while (oi[i].d == pas && i <= n)
		{
			fav.push(oi[i].p);
			++i;
		}
		if (!fav.empty())
		{
			s += fav.top();
			fav.pop();
		}
		--pas;
	}

	ofstream g("lupu.out");
	g << s << endl;

	/*for (int i = 1;i <= k;++i)
		cout << fav[i] << " ";
	cout << endl << s;
	cin.get();*/
}

int poz (oaie *v, int li, int ls)
{
	int i=li, j=ls, i1=0, j1=-1,iaux;
	oaie aux;
	while (i<j)
	{
		if (v[i].d < v[j].d)
		{
			aux=v[i];
			v[i]=v[j];
			v[j]=aux;
			iaux=i1;
			i1=-j1;
			j1=-iaux;
		}
		i=i+i1;
		j=j+j1;
	}
	return i;
}
void qsort (oaie *v, int li, int ls)
{
	int k;
	if (li<ls)
	{
		k=poz (v,li, ls);
		qsort (v,li, k-1);
		qsort (v,k+1, ls);
	}
}
//void adg(int *v, int &n, int x)
//{
//	if (n == 0)
//	{
//		v[1] = x;
//		++n;
//		return;
//	}
//	++n;
//	int li(1), ls(n), m((n+1)/2);
//	while (m != li)
//	{
//		if (x > v[m])
//			li = m;
//		else ls = m;
//		m = (li+ls)/2;
//	}
//	if (x > v[li])
//		++li;
//	for (int i = n;i >= li;--i)
//		v[i+1] = v[i];
//	v[li] = x;
//}
//int extr(int *v, int &n)
//{
//	if (n > 0)
//	{
//		--n;
//		return v[n+1];
//	}
//	return 0;
//}