Cod sursa(job #517790)

Utilizator crushackPopescu Silviu crushack Data 29 decembrie 2010 21:42:11
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 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] , m[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,j,p,l,ll,d,last=0,r,TMax=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;
		TMax= (a[i].d>TMax) ? a[i].d : TMax;
	}
	fclose(stdin);
	
	sort(a,a+N,cmp);
	
	/*for (p=0;p<N && a[p].d<=0;p++);
	
	for(r=0;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 && ll>0;i++,ll--)
		{
			s+= a[p].x;
			pop_heap(a+p,a+p+ll,cmp2);
		}
		for (;r>0 && ll>0;i++,ll--,r--)
		{
			s+= a[p].x;
			pop_heap(a+p,a+p+ll,cmp2);
		}
		r+= d-i;
	}*/
	
	for (l=0,i=N-1,p=TMax;i>0 && a[i].d>0 && p>0 ;p--)
	{
		for (; i>0 && a[i].d == p ;i--)
		{
			m[l++]=a[i];
			push_heap(m,m+l,cmp2);
		}
		if (l>0)
		{
			s+= m[0].x;
			pop_heap(m,m+l,cmp2);
			l--;
		}
	}
	
	freopen(OUT,"w",stdout);
	printf("%lld\n",s);
	fclose(stdout);
	
	return 0;
}