Pagini recente » Cod sursa (job #2473797) | usor | Cod sursa (job #2123162) | Cod sursa (job #2275441) | Cod sursa (job #1037804)
#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(fd<=nh&&h[fd]<h[bun])
bun=fd;
if(fs<=nh&&h[fs]<h[bun])
bun=fs;
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 + l*cont <= x)
{
adauga(v[i].lana);
total += v[i].lana;
cont++;
}
else
if(v[i].lana > h[1])
{
total += v[i].lana;
total -= h[1];
h[1] = v[i].lana;
coboara(1);
}
}
printf("%lld",total);
return 0;
}