Cod sursa(job #313801)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 9 mai 2009 18:49:49
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100005
struct lupu{int t,l;}v[N];
int n,x,l,h[N],nr;
long long s;
int compar(const void*p,const void*q)
{
	lupu pp=*(lupu*)p,qq=*(lupu*)q;
	if (pp.t<qq.t) return 1;
	if (pp.t>qq.t) return -1;
	return 0;
}
void citire()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d%d%d",&n,&x,&l);
	for (int i=1; i<=n; ++i)
	{
		int d;
		scanf("%d%d",&d,&v[i].l);
		if(x==0 && d)
			v[i].t=-1;
		else
			v[i].t=(x-d)/l;
		//printf("%d ",v[i].t);
	}
	qsort(v+1,n,sizeof(v[0]),compar);
}
void cobor(int k)
{
	int y=h[k];
	while (k>1&&y>h[k/2])
	{
		h[k]=h[k/2];
		k/=2;
	}
	h[k]=y;
}
void heap(int k)
{
	h[++nr]=v[k].l;
	cobor(nr);
}
void urc(int k)
{
	int f=k;
	while (true)
	{
		if (2*k<=nr && h[2*k]>h[f])
			f=2*k;
		if (2*k+1<=nr && h[2*k+1]>h[f])
			f=2*k+1;
		if (f==k)
			return;
		int aux=h[k];
		h[k]=h[f];
		h[f]=aux;
		k=f;
		
	}
}
void del(int k)
{
	h[k]=h[nr];
	--nr;
	if (k>1&& h[k]>h[k/2])
		cobor(k);
	else 
		urc(k);
}
void build()
{
	int j=1;
	for(int i=v[1].t ; i>=0 ; --i)
	{
		while(j<=n && v[j].t==i)
		{
			heap(j);
			++j;
		}
		if(nr)
		{
			s+=h[1];
			del(1);
		}
	}
	
	printf("%lld\n",s);
}
int main()
{
	citire();
	build();
	return 0;
}