Cod sursa(job #601991)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 8 iulie 2011 17:21:46
Problema Lupul Urias si Rau Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
#include<algorithm>


using namespace std;



struct sheep
{int d,p;};


sheep oi[100005];


bool comp(sheep a,sheep b)
{
	if(a.d<b.d)
		return 1;
	if(a.d>b.d)
		return 0;
	if(a.p>b.p)
		return 1;
	return 0;
}


void down(int n, int k)
{
	int fiu;
	sheep temp;
	do
	{
		fiu=0;
		if(2*k<=n)
		{
			fiu=2*k;
			if(2*k+1<=n&&oi[2*k+1].p>oi[fiu].p)
				fiu=2*k+1;
		}
		if(fiu)
			if(oi[fiu].p>oi[k].p)
			{
				temp.p=oi[k].p;
				oi[k].p=oi[fiu].p;
				oi[fiu].p=temp.p;
				temp.d=oi[k].d;
				oi[k].d=oi[fiu].d;
				oi[fiu].d=temp.d;
				k=fiu;
			}
			else
				fiu=0;
	}while(fiu);
}



void erase(int n)
{
	oi[1].p=oi[n].p;
	oi[n].p=0;
	down(n-1,1);
}




void build(int n)
{
	int i;
	for(i=n/2;i>=1;--i)
		down(n,i);
}



int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	int n,d,l,i,j,k,s=0;
	scanf("%d%d%d",&n,&d,&l);
	for(i=1;i<=n;++i)
		scanf("%d%d",&oi[i].d,&oi[i].p);
	sort(oi+1,oi+1+n,comp);
	i=1;
	for(j=0;j<=d;j=j+l)
	{
		for(;i<=n&&oi[i].d<=j;++i);
		build(i-1);
		s=s+oi[1].p;
		erase(i);
	}
	printf("%d\n",s);
	return 0;
}