Cod sursa(job #342978)

Utilizator irene_mFMI Irina Iancu irene_m Data 24 august 2009 15:27:29
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <vector>
#define MaxN 100009
#define t(x)	((x)/2)
#define fs(x)	((x)*2)
#define fd(x)	((x)*2+1)

using namespace std;

vector <long> T[MaxN];
long D[MaxN],A[MaxN],X,L,n,heap[MaxN],N,S,T_max;

void cit()
{
	long x;
	freopen("lupu.in","r",stdin);
	scanf("%ld%ld%ld",&n,&X,&L);
	for(long i=1;i<=n;i++)
	{
		scanf("%ld%ld",&D[i],&A[i]);
		if(D[i]<=X)
		{
			x=(X-D[i])/L+1;
			T[x].push_back(i);
			if(x>T_max)
				T_max=x;
		}
	}
}

void swap(long x,long y)
{
	long aux=heap[x]; heap[x]=heap[y]; heap[y]=aux;
}

void upheap(long nod)
{
	while(nod>1 && heap[nod]>heap[t(nod)])
		swap(nod,t(nod)), nod=t(nod);
}

void add(long p)
{
	N++;
	heap[N]=A[p];
	upheap(N);
}

void downheap(long nod)
{
	while((fs(nod)<=N && heap[nod]<heap[fs(nod)]) || (fd(nod)<=N && heap[nod]<heap[fd(nod)]))
		if(fd(nod)<=N)
		{
			if(heap[fs(nod)]>heap[fd(nod)])
				swap(nod,fs(nod)), nod=fs(nod);
			else
				swap(nod,fd(nod)), nod=fd(nod);
		}
		else
			swap(nod,fs(nod)), nod=fs(nod);
}

void erase(long nod)
{
	heap[nod]=heap[N];
	heap[N]=0; N--;
	if(N>1)
		downheap(nod);
}

	
void sol()
{
	long i,j,max,p;
	for(i=T_max;i>=1;i--)
	{
		max=0;
		for(j=0;j<T[i].size();j++)
		{
			p=T[i][j];
			add(p);
		}
		S+=heap[1];
		if(N>0)
			erase(1);
	}
}

void afis()
{
	freopen("lupu.out","w",stdout);
	printf("%ld",S);
}

int main()
{
	cit();
	sol();
	afis();
	return 0;
}