Cod sursa(job #313784)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 9 mai 2009 18:24:14
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 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);
		v[i].t=(x-d)/l;
		//printf("%d ",v[i].t);
	}
	qsort(v+1,n,sizeof(v[0]),compar);
	/*for (int i=1; i<=n; ++i)
		printf("%d ",v[i].t);*/
}
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;
		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()
{
	/*
	for (int i=1; i<n; ++i)
	{
		while (v[i].t==v[i+1].t&&i<=n)
		{
			heap(i);
			++i;
		}
		if (i<=n)
		{
			if (v[i-1].t!=v[i].t&&v[i].t!=v[i+1].t)
			{
				s+=v[i].l;
				for (int j=1; j<=nr;++j)
				{
					--v[j].t;
					if (v[j].t<0)
						del(j);
				}
			}
			else
			{
				s+=h[1];
				del(1);
				for (int j=1; j<=nr;++j)
				{
					--v[j].t;
					if (v[j].t<0)
						del(j);
				}
			}
		}
	}
	*/
	int j=1;
	for(int i=v[1].t ; i>=0 ; --i)
	{
		while(j<=n && v[j].t==i)
		{
			heap(j);
			++j;
		}
		s+=h[1];
		del(1);
	}
	//s+=h[1];
	//del(1);
	printf("%lld\n",s);
}
int main()
{
	citire();
	build();
	return 0;
}