Cod sursa(job #330550)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 10 iulie 2009 14:54:56
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>

#define MAX_N 100000+1
int n,x,l,k,sol;
int T[MAX_N],D[MAX_N],A[MAX_N],Heap[MAX_N];
int T_MAX = -1;


void read(),solve(),heapUp(int),heapDown(int);
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	
	read();
	solve();
	printf("%d\n",sol);
	
	fclose(stdin); fclose(stdout);
	return 0;
}

void read()
{
	scanf("%d%d%d",&n,&x,&l);
	for(int i = 0; i < n; i++)
	{
		scanf("%d %d",&D[i],&A[i]);
		T[i] = (x-D[i])/l;
        T_MAX = T_MAX > T[i] ? T_MAX : T[i];		
	}
}


void solve()
{
	int i,j;
	for(i = 1; i <= T_MAX; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(T[j] == i)
			{
				Heap[++k] = A[j];
				heapUp(k);
			}
		}
		sol += Heap[1];		
		Heap[1] = Heap[--k];
		heapDown(1);
	}
}

void heapUp(int v)
{
	int key = Heap[v];
	while(v && key > Heap[v/2])
	{
		Heap[v/2] = Heap[v];
		v/=2;
	}
	Heap[v] = key;
}

void heapDown(int v)
{
	int w = v*2;
	while(v <= k)
	{
		if(w+1 <= k && Heap[w+1] > Heap[w]) w++;
		if(Heap[v] >= Heap[w]) return;
		
		Heap[w] ^= Heap[v] ^= Heap[w] ^= Heap[v];
		v = w;
		w *= 2;
	}
}