Pagini recente » Cod sursa (job #2700764) | Cod sursa (job #2764100) | Cod sursa (job #127633) | Cod sursa (job #365953) | Cod sursa (job #1630211)
#include <stdio.h>
#include <algorithm>
#define lim 100005
using namespace std;
struct elem{int dist,val;};
elem v[lim];
int heap[lim],ind[lim],m;
int tata(int p){
return (p-1)/2;
}
int fiust(int p){
return 2*p+1;
}
int fiudr(int p){
return 2*p+2;
}
void schimba(int p,int q){
int aux;
aux=heap[p];
heap[p]=heap[q];
heap[q]=aux;
ind[heap[p]]=p;
ind[heap[q]]=q;
}
void urca(int p){
while(p>0&&v[heap[p]].val>v[heap[tata(p)]].val){
schimba(p,tata(p));
p=tata(p);
}
}
void adauga(int x){
heap[m]=x;
m++;
urca(m-1);
}
void coboara(int p){
int q,pp=1;
while(pp==1&&fiust(p)<m){
q=fiust(p);
if(fiudr(p)<m&&v[heap[fiust(p)]].val>v[heap[q]].val)
q=fiudr(p);
if(v[heap[q]].val>v[heap[p]].val){
schimba(p,q);
p=q;
}
else
pp=0;
}
}
void sterge(int p){
m--;
schimba(m,p);
if(p>0&&v[heap[p]].val>v[heap[tata(p)]].val)
urca(p);
else
coboara(p);
}
bool cmp(elem a,elem b){
if(a.dist<b.dist)
return true;
else
return false;
}
int main(){
FILE *fin,*fout;
fin=fopen("lupu.in","r");
fout=fopen("lupu.out","w");
int i,j,k,l,n,raza,x;
long long rasp=0;
fscanf(fin,"%d%d%d",&n,&raza,&x);
for(i=1;i<=n;i++)
fscanf(fin,"%d%d",&v[i].dist,&v[i].val);
sort(v+1,v+n+1,cmp);
k=raza/x;
i=1;
l=1;
for(j=k;j>=0;j--){
while(v[i].dist+j*x>raza){
sterge(ind[i]);
l++;
}
while(i<=n&&v[i].dist+j*x<=raza){
adauga(i);
i++;
}
if(m>0){
rasp=rasp+(long long)v[heap[0]].val;
sterge(0);
}
}
fprintf(fout,"%I64d",rasp);
fclose(fin);
fclose(fout);
return 0;
}