Cod sursa(job #991)

Utilizator damaDamaschin Mihai dama Data 12 decembrie 2006 13:32:35
Problema Lupul Urias si Rau Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct str
{
	int d, val;
};

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


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

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	
	int i, tmp = 0;
	
	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);
	
	v[0] = 1000000;
	
	for(i = 1; i <= n && tmp <= x; ++i)
	{
		while(a[i].d <= tmp && i <= n)
		{
			v[++heapsize] = a[i].val;
			riseup(heapsize);
			++i;
		}
		if(heapsize)
		{
			sol += v[1];
			v[1] = v[heapsize];
			--heapsize;
			maxheapify(1);
		}
		tmp += l;
		--i;
	}
	
	printf("%d\n",sol);
	
	return 0;
}

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

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

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

void riseup(int pos)
{
	int tmp;
	
	if(v[pos] > v[pos / 2])
	{
		tmp = v[pos];
		v[pos] = v[pos / 2];
		v[pos / 2] = tmp;
		riseup(pos / 2);	
	}
}