Cod sursa(job #910)

Utilizator damaDamaschin Mihai dama Data 12 decembrie 2006 08:39:02
Problema Lupul Urias si Rau Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct str
{
	int val, d;
};


void maxheapify(int* v,int pos);
void buildmaxheap(int* v);
bool cmp(str one, str two);



int n, x, l, heap[100001], heapsize, sol;
str a[100001];


int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);

	int i, tmp;
	
	scanf("%d%d%d",&n,&x,&l);
	

	
	for (i = 1; i <= n; ++i)
	{
		scanf("%d%d",&a[i].d,&a[i].val);
	}
	sort(a + 1, a + n + 1, cmp);
	
	tmp = 0;
	for (i = 1; i <= n && tmp <= x; ++i)
	{
		while(a[i].d <= tmp && i <= n)
		{
			heap[++heapsize] = a[i].val;
			++i;
		}
		buildmaxheap(heap);
		
		if(heapsize > 0)
		{
			sol += heap[1];
			heap[1] = heap[heapsize];
			--heapsize;
			maxheapify(heap,1);
		}
		--i;
		tmp += l;
	}
	
	printf("%d\n",sol);
	
	
	
	return 0;
}

void maxheapify(int* v,int pos)
{
	int l, r, largest = pos, temp ;
	l = 2 * pos;
	r = 2 * pos + 1;
	
	if(l <= heapsize && v[l] > v[largest])
		largest = l;
	if(r <= heapsize && v[r] > v[largest])
		largest = r;
	
	if(largest != pos)
	{
		temp = v[pos];
		v[pos] = v[largest];
		v[largest] = temp;
		maxheapify(v,largest);
	}
	
}

void buildmaxheap(int* v)
{
	int i;
	
	for (i = heapsize/2; i > 0; --i)
	{
		maxheapify(v,i);
	}
}

bool cmp(str one, str two)
{
	return  one.d < two.d;
}