Cod sursa(job #344762)

Utilizator irene_mFMI Irina Iancu irene_m Data 31 august 2009 15:31:26
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 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 long> T[MaxN];
long long D[MaxN],A[MaxN],X,L,n,heap[MaxN],N,S,T_max,s;

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

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

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

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

void downheap(long long nod)
{
	while((fs(nod)<=N && A[heap[nod]]<A[heap[fs(nod)]]) || (fd(nod)<=N && A[heap[nod]]<A[heap[fd(nod)]]))
		if(fd(nod)<=N)
		{
			if(A[heap[fs(nod)]]>A[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 long nod)
{
	heap[nod]=heap[N];
	heap[N]=0; N--;
	downheap(nod);
}

	
void sol()
{
	long 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+=A[heap[1]];
		if(N>0)
			erase(1);
	}
}

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

int main()
{
	cit();
	if(!L)
		S=s;
	else
		sol();
	afis();
	return 0;
}