Cod sursa(job #17462)

Utilizator crusRus Cristian crus Data 15 februarie 2007 22:06:11
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#define input "lupu.in"
#define output "lupu.out"
#define nmax 200002
struct oaie {long long d,c,t;} o[nmax],aux,s1[nmax],s2[nmax],vect[nmax];
long long n,x,l,sol,l1,l2,j,i1,i2,nl,pc,t,timp,nm;
void citire()
{
	long i;
	FILE *fin;
	fin=fopen(input,"r");
	fscanf(fin,"%lld %lld %lld",&n,&x,&l); nm=0;
	for (i=1;i<=n;i++)		
		{
		 nm++;
		 fscanf(fin,"%lld %lld",&o[nm].d,&o[nm].c);		
		 o[nm].t=1+(x-o[nm].d)/l;
		 if (o[nm].d>x) nm--;
		}
	fclose(fin);
}
void afisare()
{
	FILE *fout;
	fout=fopen(output,"w");
	fprintf(fout,"%lld",sol);
	fclose(fout);
}
void merge(long ls, long ld)
{
	if (ls<ld)
		{
		 long k=(ls+ld)/2,kk;
		 merge(ls,k);
		 merge(k+1,ld);
		 l1=0;
		 l2=0;
		 for (j=ls;j<=k;j++) s1[++l1]=o[j];
		 for (j=k+1;j<=ld;j++) s2[++l2]=o[j];
		 i1=1;
		 i2=1;
		 k=ls-1;
		 while (i1<=l1&&i2<=l2)
			 if (s1[i1].t<s2[i2].t) o[++k]=s2[i2++];
				else o[++k]=s1[i1++];
		 for (kk=i1;kk<=l1;kk++) o[++k]=s1[kk];
		 for (kk=i2;kk<=l2;kk++) o[++k]=s2[kk];
		}
}
void urca(long x)
{
	if (vect[x].c>vect[x/2].c&&x>1) 
	   {
	    aux=vect[x];
	    vect[x]=vect[x/2];
	    vect[x/2]=aux;
		urca(x/2);
	   }	
}
void adauga()
{
	vect[++nl]=o[pc];
	urca(nl);
}
void scoatecap(long k)
{
	if (((vect[2*k].c)||(vect[2*k+1].c))&&(k<=nl))
		if (vect[2*k+1].c>vect[2*k].c) 
			{
			aux=vect[k];
			vect[k]=vect[2*k+1];
			vect[2*k+1]=aux;
			scoatecap(2*k+1);
			}	
		else
			{
			aux=vect[k];
			vect[k]=vect[2*k];
			vect[2*k]=aux;
			scoatecap(2*k);
			}	
}
void solve()
{
	merge(1,n);	
	nl=0;
	timp=o[1].t; pc=1; sol=0;
	while (timp)
		  {
	    	while (o[pc].t==timp) {adauga(); pc++;}
			sol+=vect[1].c;
			vect[1].c=0;
			scoatecap(1);
			timp--;
		  } 		
}
int main()
{
	citire();
	solve();
	afisare();
	return 0;
}