Pagini recente » Cod sursa (job #1029814) | Cod sursa (job #2334290) | Cod sursa (job #2347553) | Cod sursa (job #2813697) | Cod sursa (job #1037776)
#include<stdio.h>
#include<algorithm>
int h[100001],nh;
struct oaie{
int dist;
int lana;
}v[100001];
bool cmp(oaie a,oaie b){
return a.dist>b.dist;
}
void schimba(int p1,int p2){
int aux;
aux=h[p1];
h[p1]=h[p2];
h[p2]=aux;
}
void urca(int p){
while(p!=1&&h[p]<h[p/2]){
schimba(p,p/2);
p/=2;
}
}
void adauga(int x){
h[++nh]=x;
urca(nh);
}
void coboara(int p){
int fs=2*p,fd=2*p+1,bun=p;
if(fs<=nh&&h[fs]>h[bun])
bun=fs;
if(fd<=nh&&h[fd]>h[bun])
bun=fd;
if(bun!=p){
schimba(p,bun);
coboara(bun);
}
}
void sterge(int p){
schimba(h[p],h[nh--]);
urca(p);
coboara(p);
}
int main(){
int n,x,l,a,d,i,cont=0;
long long total = 0;
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&x,&l);
for(i=1;i<=n;i++){
scanf("%d%d",&d,&a);
v[i].dist=d;
v[i].lana=a;
}
std::sort(&v[1],&v[n+1],cmp);
for(i=1;i<=n;i++){
if(v[i].dist + cont <= x)
{
adauga(v[i].lana);
total += v[i].lana;
cont += l;
}
else
if(v[i].lana > h[1])
{
total += v[i].lana - h[1];
h[1] = v[i].lana;
coboara(1);
}
}
printf("%lld",total);
return 0;
}