Cod sursa(job #640796)

Utilizator balakraz94abcd efgh balakraz94 Data 26 noiembrie 2011 15:22:19
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<cstdio>
#include<algorithm>
#define infile "lupu.in"
#define outfile "lupu.out"
#define n_max 100005
#define ls(i) i<<1
#define rs(i) (i<<1) + 1
#define f(i) i>>1
using namespace std;

struct oaie
{ int dist, cost; } a[n_max];

int H[n_max];

int N;

int n, d, l;

int sol;



inline bool mycmp( const oaie &a, const oaie &b)
{ return a.dist > b.dist; }



void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d %d",&n,&d,&l);
	
	for(int i=1;i<=n;i++)
		scanf("%d %d",&a[i].dist,&a[i].cost);

	fclose(stdin);
}



void sift(int k)
{
	int son = k, l = ls(k), r =rs(k);
	
	if(l<=N && H[son] > H[l] )
		son = l;
	if(r<=N && H[son] > H[r] )
		son = r;
	if(son!=k)
	{
		swap(H[son], H[k]);
		sift(son);
	}
}



int get_max_heap()
{
	if(!N)
		return 0;
	
	int maxim = H[1];
	
	H[1] = H[N--];
	
	sift(1);
	
	return maxim;
}



void percolate(int k)
{
	while(k>1 && H[f(k)] > H[k] )
	{
		swap(H[k], H[f(k)]);
		k = f(k);
	}
}



void insert(int x)
{
	H[++N] = x;
	percolate(N);
}



void rezolva()
{
	sort(a+1,a+n+1,mycmp);
	
	for(int i=1;i<=n;i++)
	{
		if(!N)
		{
			insert(a[i].cost);
			d-=l;
			sol+=a[i].cost;
			continue;
		}
		
		if(a[i].dist <= d)
		{
			insert(a[i].cost);
			sol+=a[i].cost;
			d-=l;
			continue;
		}
		
		if(H[1] < a[i].cost)
		{
			sol-= get_max_heap();
			sol+=a[i].cost;
			insert(a[i].cost);
		}
	}
}
	


void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",sol);

	fclose(stdout);
}



int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}