Cod sursa(job #821203)

Utilizator axnsanCristi Vijdea axnsan Data 21 noiembrie 2012 21:08:37
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
//#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
struct oaie { 
	int d,p; 
} oi[100010];
//void qsort (oaie *v, int li, int ls);
bool cmp(oaie o1, oaie o2)
{
	return (o1.d > o2.d);
}
//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;
	}
	sort(oi+1, oi+n+1, cmp);
	/*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;
//}