Cod sursa(job #517782)

Utilizator crushackPopescu Silviu crushack Data 29 decembrie 2010 21:19:00
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>
#include <algorithm>
#define NMax 100000
using namespace std;

const char IN[]="lupu.in",OUT[]="lupu.out";

int N,X,L;
struct oaie{
	int x,d;
} a[NMax];

bool cmp(oaie a,oaie b)
{
	return a.d<b.d;
}

bool cmp2(oaie a,oaie b)
{
	return a.x<b.x;
}

int main()
{
	int i,p,l,ll,d,last=0;
	long long s=0;
	freopen(IN,"r",stdin);
	scanf("%d%d%d",&N,&X,&L);
	for (i=0;i<N;i++)
	{
		scanf("%d%d",&a[i].d,&a[i].x);
		a[i].d= (X-a[i].d)/L + 1;
	}
	fclose(stdin);
	
	sort(a,a+N,cmp);
	
	for (p=0;p<N && a[p].d<=0;p++);
	
	for(;p<N;p+=l)
	{
		l=0;
		d= a[p].d - last;
		last= a[p].d;
		for(l=0;p+l<N && a[p+l].d==a[p].d;l++);
		make_heap(a+p,a+p+l,cmp2);
		for (i=0,ll=l;i<d;i++,ll--)
		{
			s+= a[p].x;
			pop_heap(a+p,a+p+ll,cmp2);
		}
	}
	
	freopen(OUT,"w",stdout);
	printf("%lld\n",s);
	fclose(stdout);
	
	return 0;
}