Cod sursa(job #334706)

Utilizator zbarniZajzon Barna zbarni Data 27 iulie 2009 18:16:42
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define pb push_back
#define mp make_pair
#define nx 100005
#define inf 
using namespace std;
vector <int> a[nx];
long long n,x,l,heap[nx],L,T;
long long sol;
void swap (long long &a,long long &b)
{
	long long c;
	c=a;
	a=b;
	b=c;
}

void upheap (int x)
{
	int aux;
	while (x/2 && heap[x]>heap[x/2])
	{
		swap(heap[x],heap[x/2]);
		x/=2;
	}
}
void downheap(int x)
{
	int y=0;
	while (y!=x)
	{
		y=x;
		if (y*2<=L && heap[y*2]>heap[x])
			x=y*2;
		if (y*2+1<=L && heap[y*2+1]>heap[x])
			x=y*2+1;
		swap(heap[x],heap[y]);
	}
}
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%lld%lld%lld",&n,&x,&l);
	long long i,p,q,j;
	for (i=1;i<=n;++i)
	{
		scanf("%lld%lld",&p,&q);
		if (p<=x)  
		{
			a[(x-p)/l+1].pb(q);
			if ((x-p)/l+1>T) T=(x-p)/l+1;
		}
	}
	for (;T>=1;T--) 
	{
		for (j=0;j<a[T].size();++j)
		{
			heap[++L]=a[T][j];
			upheap(L);
		}			
		if (L>0)
		{	
			sol+=heap[1];
			heap[1]=heap[L--];
			downheap(1);
		}
	}
	printf("%lld\n",sol);
	return 0;
}