Cod sursa(job #602130)

Utilizator smaraldaSmaranda Dinu smaralda Data 9 iulie 2011 11:59:38
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<stdlib.h>
struct TIP { int d,a;};
TIP oi[100010];
int num,h[100010];
int comp ( const void *a, const void *b)
{
	TIP *pa,*pb ;
	pa=(TIP *)a;
	pb=(TIP *)b;
	if(pa->d==pb->d)
			 return 0;
	if(pa->d>pb->d)
			 return 1;
	return -1;
}


void down ( int k )
{
	int fiu=0,aux;
	do
		{
		  fiu=0;
		  if(2*k<=num)
				fiu=2*k;
		  if(2*k+1<=num && h[2*k+1]>h[fiu])
				fiu=2*k+1;
		  if(h[fiu]>h[k])
				{
					aux=h[k];
					h[k]=h[fiu];
					h[fiu]=aux;
					k=fiu;
				}
		  else
				fiu=0;
		}while(fiu);
}

void up ( int k)
{
	int aux;

	while(k>1 && h[k]>h[k/2])
		{

			aux=h[k];
			h[k]=h[k/2];
			h[k/2]=aux;
			k=k/2;
		}
}


int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	int i,max,lana,n,lim,x,l;
	scanf("%d%d%d",&n,&x,&l);
	max=0;
	for(i=1;i<=n;i++)
			{
				scanf("%d%d",&oi[i].d,&oi[i].a);
				if(oi[i].d==0 && oi[i].a>max) max=oi[i].a;
			}
	qsort(oi+1,n,sizeof(oi[0]),comp);
	num=i=lana=0;
	lim=0;
	lana=max;
	do
		{
			i=i+1;
			while(i<=n && oi[i].d<=lim+l)
					 {
						h[++num]=oi[i].a;
						up(num);
						++i;
					 }

			lana=lana+h[1];
			h[1]=h[num];
			num--;
			down(1);
			lim=lim+l;
		}while(lim<=x && i<n);
	printf("%d\n",lana);
	return 0;
}