Pagini recente » Cod sursa (job #925947) | Cod sursa (job #144682) | Cod sursa (job #2941900) | Cod sursa (job #2741701) | Cod sursa (job #1317977)
/***/
#include<stdio.h>
#include<algorithm>
using namespace std;
struct oi{
int d,a;
}nr[100010];
int sum;
int hn,heap[100010];
pair <int,int> v[100010];
void schimb(int i,int poz){
int aux=heap[poz];
heap[poz]=heap[i];
heap[i]=aux;
}
void upheap(int i){
int poz=i>>1;
if(heap[i]>heap[poz] && poz>0){
schimb(i,poz);
upheap(poz);
}
}
void downheap(int i){
int st=i<<1,max;
max=i;
if(st<=hn && heap[max]<heap[st])
max=st;
++st;
if(st<=hn && heap[max]<heap[st])
max=st;
if(max!=i){
schimb(i,max);
downheap(max);
}
}
int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int n,x,l,i,tmax;
scanf("%d%d%d",&n,&x,&l);
for(i=0;i<n;++i){
scanf("%d%d",&nr[i].d,&nr[i].a);
v[i].second=i;
v[i].first=(x-nr[i].d)/l;
}
sort(v,v+n);
tmax=v[n-1].first;
hn=0;
i=n-1;
while(i>=0 && tmax>=0){
while(tmax==v[i].first && i>=0){
heap[++hn]=nr[v[i].second].a;
upheap(hn);
--i;
}
if(hn>0){
sum+=heap[1];
heap[1]=heap[hn--];
heap[hn+1]=0;
downheap(1);
}
--tmax;
}
printf("%d\n",sum);
fclose(stdin);
fclose(stdout);
return 0;
}