Pagini recente » Cod sursa (job #2760722) | Cod sursa (job #2780350) | Cod sursa (job #2822257) | Cod sursa (job #3159573) | Cod sursa (job #645413)
Cod sursa(job #645413)
#include <stdio.h>
#include <algorithm>
using namespace std;
int v[100001],nr;
struct oi
{
int dst,pf;
};
oi a[1000001];
void chng (int &a,int &b)
{
int aux;
aux=a;
a=b;
b=aux;
}
bool cmp (oi a, oi b)
{
if (a.dst > b.dst)
return true;
return false;
}
void urca (int x)
{
if (x>=2 && v[x]<v[x/2])
{
chng (v[x],v[x/2]);
urca (x/2);
}
}
void coboara (int p)
{
int pmin = p;
if(2*p <= nr && v[2*p] < v[pmin]) pmin = 2*p;
if(2*p + 1 <= nr && v[2*p + 1] < v[pmin]) pmin = 2*p + 1;
if(pmin != p)
{
chng(v[p],v[pmin]);
coboara(pmin);
}
}
int main ()
{
int n,d,l,i;
long long s=0;
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d %d %d",&n,&d,&l);
for (i=1;i<=n;i++)
{
scanf("%d %d",&a[i].dst,&a[i].pf);
}
sort (&a[1],&a[n+1],cmp);
for (i=1;i<=n;i++)
{
if (a[i].dst<=d)
{
v[++nr]=a[i].pf;
urca (nr);
d -= l;
continue;
}
if(nr>=1 && a[i].pf>v[1])
{
v[1] = a[i].pf;
coboara(1);
}
}
for (i=1;i<=nr;i++)
s+=v[i];
printf("%lld",s);
return 0;
}