Cod sursa(job #474617)

Utilizator mihai995mihai995 mihai995 Data 4 august 2010 13:46:16
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
using namespace std;

struct oaie{int lana,dist;} v[1<<17],a[1<<17];
int m;

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

inline bool cmp(oaie a,oaie b)
{
	return a.lana>b.lana || a.lana==b.lana && a.dist<b.dist;
}

inline void down(int x)
{
	int q=x;
	oaie aux;
	if ((x<<1)<=m && cmp(v[x<<1],v[q]))
		q=x<<1;
	if ((x<<1)<m && cmp(v[(x<<1)+1],v[q]))
		q=(x<<1)+1;
	if (x!=q)
	{
		aux=v[x];
		v[x]=v[q];
		v[q]=aux;
		down(q);
	}
}

inline void up(int x)
{
	if (x>1 && cmp(v[x],v[x>>1]))
	{
		oaie aux=v[x];
		v[x]=v[x>>1];
		v[x>>1]=aux;
		up(x>>1);
	}
}

bool comp(oaie a,oaie b)
{
	return a.dist>b.dist;
}

int main()
{
	int n,X,L,x,y,i,j,q=0,T=-1;
	long long s=0;
	in>>n>>X>>L;
	while (n--)
	{
		in>>x>>y;
		if (x<=X)
		{
			a[++q].dist=(X-x)/L+1;
			a[q].lana=y;
			T=max(T,a[q].dist);
		}
	}
	sort(a+1,a+q+1,comp);
	for (i=T,j=1;i;i--)
	{
		for (;j<=q && a[j].dist==i;j++)
		{
			v[++m]=a[j];
			up(m);
		}
		while (m && v[1].dist<i)
		{
			v[1]=v[m--];
			down(1);
		}
		if (m)
		{
			s+=v[1].lana;
			v[1]=v[m--];
			down(1);
		}
	}
	out<<s<<"\n";
	return 0;
}