Pagini recente » Cod sursa (job #2562991) | Cod sursa (job #461298) | Cod sursa (job #3126856) | Cod sursa (job #1904066) | Cod sursa (job #1702768)
#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;
}