Cod sursa(job #271025)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 4 martie 2009 20:14:14
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
#define nmax 100010
long h[nmax], d[nmax], ln[nmax], n, x, l, nh, t, tmax, nr;
struct elem
{	long t, i;
	elem *urm;
}	*snt, *u, *q, *w;
FILE *f, *g;

void ins(long lana)
{	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(long k)
{	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;
	}
}


int main()
{       long i, j;
	f=fopen("lupu.in", "r");
	g=fopen("lupu.out", "w");
	fscanf(f, "%ld%ld%ld", &n, &x, &l);
	u=snt;
	for(i=1; i<=n; i++)
	{	fscanf(f, "%ld%ld", &d[i], &ln[i]);
		if(x-d[i]>=0)
		{	t=(x-d[i])/l+1;
			if(t>tmax)
				tmax=t;
			if(!u || u->t>=t)
			{	w=new elem;
				u->urm=w;
				w->t=t; w->i=i; w->urm=NULL;
				u=w;
			}
			else
			{	for(q=snt; q->urm; q=q->urm)
					if(q->urm->t<=t)
					{       w=new elem;
						w->t=t; w->i=i; w->urm=q->urm;
						q->urm=w; break;
					}
			}
		}
	}
	q=snt->urm;
	for(j=tmax; j>=1; j--)
	{       while(q->t==j && q)
		{	ins(ln[q->i]);
			q=q->urm;
		}
		if(nh>0)
		{	nr+=h[1];
			del(1);
		}
	}
	fprintf(g, "%ld\n", nr);
	fclose(g);
	return 0;
}