Cod sursa(job #474409)

Utilizator mihai995mihai995 mihai995 Data 3 august 2010 18:26:30
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
using namespace std;

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

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

inline void down(int x)
{
	int q=x;
	oaie aux;
	if ((x<<1)<=m && v[x<<1].lana>v[q].lana)
		q=x<<1;
	if ((x<<1)<m && v[(x<<1)+1].lana>v[q].lana)
		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 && v[x>>1].lana<v[x].lana)
	{
		oaie aux=v[x];
		v[x]=v[x>>1];
		v[x>>1]=aux;
		up(x>>1);
	}
}		

int main()
{
	int n,X,L,x,y,s=0,i;
	in>>n>>X>>L;
	while (n--)
	{
		in>>x>>y;
		if (x<=X)
		{
			v[++m].dist=(X-x)/L+1;
			v[m].lana=y;
			up(m);
		}
	}
	for (i=1;m;i++)
	{
		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;
}