Cod sursa(job #1702768)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 15 mai 2016 15:39:31
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int N,X,L,d,Max=0,pos=1,Size=0,Heap[100001]={};
long long int S;
struct arr
{
	int t,val;
}v[100001];
bool cond(arr a, arr b)
{
	return a.t>b.t||(a.t==b.t&&a.val>b.val);
}
void Read()
{
	scanf("%d%d%d",&N,&X,&L);
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&d,&v[i].val);
		v[i].t=(X-d)/L+1;
		if(v[i].t>Max)
			Max=v[i].t;
	}
	sort(v+1,v+N,cond);
}
void Add_To_Heap(int element,int &Hl)
{
	Hl++;
	Heap[Hl]=element;
}
void Extract_From_Heap (int pos,int &Hl)
{
	int t=Heap[pos];
	Heap[pos]=Heap[Hl];
	Heap[Hl]=t;
	Hl--;
}
void Maxify_Heap(int pos,int Hl)
{
	int left=2*pos,right=2*pos+1,largest;
	if(left<=Hl&&Heap[left]>Heap[pos])
		largest=left;
	else
		largest=pos;
	if(right<=Hl&&Heap[right]>Heap[largest])
		largest=right;
	if(pos!=largest)
	{
		int t=Heap[largest];
		Heap[largest]=Heap[pos];
		Heap[pos]=t;
		 Maxify_Heap(largest,Hl);
	}
}
void Max_Heap (int Hl)
{
	for(int i=Hl/2;i>0;i--)
		Maxify_Heap(i,Hl);
}
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	Read();
	for(int i=Max;i>0;i--)
	{
		while(v[pos].t==i)
		{
			Add_To_Heap(v[pos].val,Size);
			pos++;
			Maxify_Heap(1,Size);
		}
		S+=Heap[1];
		Extract_From_Heap(1,Size);
		Maxify_Heap(1,Size);
	}
	printf("%lld",S);
	return 0;
}