Cod sursa(job #274261)

Utilizator cameleonGeorgescu Dan cameleon Data 9 martie 2009 16:18:04
Problema Lupul Urias si Rau Scor 76
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<stdio.h>
#define nmax 100010
struct timp 
{
	unsigned long t,ti;}a[nmax],c[nmax];
unsigned long h[nmax], d[nmax], ln[nmax], n, x, l, nh, tmax, nr, nt;
FILE *f, *g;

void ins(unsigned long lana)
{	unsigned long k, z;
	h[++nh]=lana;
	k=nh;
	while(h[k/2]<h[k] && k>1)
	{       z=h[k]; h[k]=h[k/2]; h[k/2]=z;
		k=k/2;
	}
}

void del(unsigned long k)
{	unsigned long z, m;
	z=h[k]; h[k]=h[nh]; h[nh]=z;
	nh--;
	while(( (h[2*k]>h[k] && 2*k<=nh) ||
		(h[2*k+1]>h[k] && 2*k+1<=nh) )	&& k<nh)
	{       if(2*k==nh)			m=2*k;
		else	if(h[2*k]>h[2*k+1])	m=2*k;
			else			m=2*k+1;
		z=h[m]; h[m]=h[k]; h[k]=z;
		k=m;
	}
}
void intercls(unsigned long p,unsigned long mj,unsigned long u)
{
	unsigned long i=p,j=mj+1,k=0;
	while(i<=mj && j<=u)
	    if(a[i].t>a[j].t)c[++k]=a[i++];
		else c[++k]=a[j++];
	while(i<=mj)c[++k]=a[i++];
	while(j<=u)c[++k]=a[j++];
	for(i=1;i<=k;i++)a[i+p-1]=c[i];
}
void sort (unsigned long p,unsigned long u)
{
	if(p<u)
	{
		unsigned long mj=(p+u)/2;
		sort(p,mj);
		sort(mj+1,u);
		intercls(p,mj,u);
	}
}

int main()
{   unsigned long i, j,nt=0;;
	f=fopen("lupu.in", "r");
	g=fopen("lupu.out", "w");
	fscanf(f, "%ld%ld%ld", &n, &x, &l);
	for(i=1; i<=n; i++)
	{	fscanf(f, "%ld%ld", &d[i], &ln[i]);
	
		if(x>=d[i]){	
			a[i].t=(x-d[i])/l+1;a[i].ti=i;
			if((x-d[i])/l+1>tmax)
				tmax=(x-d[i])/l+1;nt++;
		}
		
	}
	n=nt;
    sort(1,n);
	i=1;
	for(j=tmax; j>=1; j--)
	{	while(a[i].t==j && i<=n)
		{	ins(ln[a[i].ti]);
			i++;
		}
		if(nh>0)
		{	nr+=h[1];
			del(1);
		}
	}
	fprintf(g, "%ld\n", nr);
	
	fclose(g);
	return 0;
}