Cod sursa(job #1702685)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 15 mai 2016 14:21:28
Problema Lupul Urias si Rau Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>

using namespace std;

struct heap
{
	int s,l;
}v[100001];
int N,X,L,d;
void Maxify(int pos,int hlenght)
{
	long long int left=2*pos,right=2*pos+1,smallest;
	if(left<=hlenght&&(v[left].s<v[pos].s||(v[left].s==v[pos].s&&v[left].l>v[pos].l)))
		smallest=left;
	else
		smallest=pos;
	if(right<=hlenght&&(v[right].s<v[smallest].s||(v[right].s==v[smallest].s&&v[right].l>v[smallest].l)))
		smallest=right;
	if(pos!=smallest)
	{
		heap t=v[pos];
		v[pos]=v[smallest];
		v[smallest]=t;
		Maxify(smallest,hlenght);
	}
}
void Max_Heap(int hlenght)
{
	for(int i=hlenght/2;i>0;i--)
		Maxify(i,hlenght);
}
void del(int pos,int &end)
{
	heap t;
	t=v[pos];
	v[pos]=v[end];
	v[end]=t;
	end--;
	Maxify(pos,end);
}
unsigned long long S=0;
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);

	scanf("%d%d%d",&N,&X,&L);
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&d,&v[i].l);
		v[i].s=(X-d)/L+1;
	}
	Max_Heap(N);
	int test=1;
	while(N>0)
	{
		if(v[1].s>=test)
		{
			S+=v[1].l;
			test++;
		}
		del(1,N);
	}
	printf("%d",S);
	return 0;
}