Cod sursa(job #492861)

Utilizator marius21Petcu Marius marius21 Data 16 octombrie 2010 10:09:07
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <cstdlib>

FILE *fin=fopen("lupu.in","r");
FILE *fout=fopen("lupu.out","w");

int n,x,lu;
int d[100000];
int l[100000];
int hp[100000];
int hpn;

inline bool hp_compare(int a,int b)
{
	return l[hp[a]]>l[hp[b]];
}

inline void hp_swap(int a,int b)
{
	hp[a]=hp[a]^hp[b];
	hp[b]=hp[a]^hp[b];
	hp[a]=hp[a]^hp[b];
}

void hp_up(int i)
{
	while (i)
	{
		int pos = ((i+1)>>1)-1;
		if (hp_compare(pos, i)) break;
		hp_swap(pos, i);
		i=pos;
	}
}

void hp_down(int i)
{
	while (1)
	{
		int pos1 = (i<<1)+1;
		int pos2 = (i<<1)+2;
		int max = i;
		if ((pos1<hpn)&&(hp_compare(pos1, max)))
			max=pos1;
		if ((pos2<hpn)&&(hp_compare(pos2, max)))
			max=pos2;
		if (max==i) break;
		hp_swap(max, i);
		i=max;
	}
}

void hp_create(int n)
{
	hpn=n;
	for (int i=hpn-1; i>=hpn/2; i--)
		hp_up(i);
}

int hp_pop()
{
	int rt = hp[0];
	hp_swap(0, hpn-1);
	hpn--;
	hp_down(0);
	return rt;
}

int main (int argc, char * const argv[]) {
	fscanf(fin,"%d%d%d",&n,&x,&lu);
	for (int i=0; i<n; i++)
	{
		fscanf(fin,"%d%d",&d[i],&l[i]);
		hp[i]=i;
	}
	hp_create(n);
	long long s = 0;
	int dist = x;
	for (int i=0; i<n; i++)
	{
		int pos = hp_pop();
		if (d[pos]<=dist)
		{
			s+=l[pos];
			dist-=lu;
		}
	}
	fprintf(fout, "%lld\n",s);
	fclose(fin);
	fclose(fout);
    return 0;
}