Cod sursa(job #416406)

Utilizator funkydvdIancu David Traian funkydvd Data 12 martie 2010 18:15:19
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <set>
using namespace std;
ifstream f1 ("lupu.in");
ofstream f2 ("lupu.out");
multiset<int> h;
struct l {int x, y;};
l t[100005];
int a[100005],b[100005],tmax;
int compar (const void *p, const void *q)
{
	l x=*(l*)p, y=*(l*)q;
	if (x.x>y.x) return 1;
	if (x.x<y.x) return -1;
	return 0;
}
int main()
{
	int n,x1,l,i,j,poz;
	long long sol=0;
	f1>>n>>x1>>l;
	for (i=1; i<=n; i++) 
	{
		f1>>b[i]>>a[i];
		if (x1>=b[i]) {t[i].x=(x1-b[i])/l+1; t[i].y=i;}
		if (t[i].x>tmax) tmax=t[i].x;
	}
	qsort (t+1,n,sizeof(t[0]),compar);
	poz=n;
	for (j=tmax; j>=1; j--)
	{
		if (poz>0) while (t[poz].x==j && poz>0) {h.insert(a[t[poz].y]); poz--;}
		multiset<int>:: reverse_iterator it;
		if (h.size()!=0){
		it=h.rbegin();
		sol+=*it;
		i=*it;
		h.erase(h.find(i));}
	}
	f2<<sol<<"\n";
	return 0;
}