Cod sursa(job #270556)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 4 martie 2009 10:08:29
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<stdio.h>
#define nmax 100010
long h[nmax], ln[nmax], vz[nmax], n, x, l, nh;
FILE *f, *g;

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

void del(long k)
{	long z, m;
	z=h[k]; h[k]=h[nh]; h[nh]=z;
	z=ln[k]; ln[k]=ln[nh]; ln[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;
		z=ln[m]; ln[m]=ln[k]; ln[k]=z;
		k=m;
	}
}



int main()
{       long i, j, dist, lana, max, pmax, lg, nr;
	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", &dist, &lana);
		ins(dist, lana);
	}
	while(nh)
		del(1);
	i=1; lg=l; nr=0;
	while(i<=n)
	{	max=-1; pmax=-1;
		if(h[i]+lg-l<=x)
			if(h[i]+lg>x)
				while(h[i]+lg-l<=x && h[i]+lg>x && i<=n)
				{	if(ln[i]>max && vz[i]==0)
					{       if(pmax!=-1)
							vz[pmax]=0;
						max=ln[i];
						pmax=i;
						vz[pmax]=1;
					}
					i++;
				}
			else
			{       max=-1; pmax=-1;
				for(j=i; j<=n; j++)
					if(ln[j]>max && vz[j]==0)
					{       if(pmax!=-1)
							vz[pmax]=0;
						max=ln[j];
						pmax=j;
						vz[pmax]=1;
					}
			}
		if(max!=-1)
		{	nr+=max;
			lg+=l;
		}
		else
			i++;
	}
	fprintf(g, "%ld\n", nr);
	fclose(g);
	return 0;
}