Pagini recente » Cod sursa (job #294739) | Cod sursa (job #753366) | Cod sursa (job #2414899) | Cod sursa (job #1724646) | Cod sursa (job #195552)
Cod sursa(job #195552)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,x,l;
int v[100010];
unsigned long long r;
struct lup
{
int a,b;
};
lup a[100010];
inline int father(int k)
{
return k>>1;
}
inline int left_son(int k)
{
return k<<1;
}
inline int right_son(int k)
{
return (k<<1)+1;
}
/*void upheap(int k)
{
if((k==1)||(v[k]<=v[father(k)]))
return;
swap(v[k],v[father(k)]);
upheap(father(k));
}
void downheap(int h,int k)
{
int max1=k;
if(left_son(k)<=h)
{
if(v[left_son(k)]>v[max1])
max1=left_son(k);
}
if(right_son(k)<=h)
{
if(v[right_son(k)]>v[max1])
max1=right_son(k);
}
if(max1!=k)
{
swap(v[max1],v[k]);
downheap(h,max1);
}
}*/
void upheap(int k)
{
int key=v[k];
while((k>1)&&(key>v[father(k)]))
{
v[k]=v[father(k)];
k=father(k);
}
v[k]=key;
}
void downheap(int k,int h)
{
int son;
do
{
son=0;
if(left_son(k)<=h)
{
son=left_son(k);
if(right_son(k)<=h)
{
if(v[left_son(k)]<v[right_son(k)])
son=right_son(k);
}
if(v[k]>=v[son])
son=0;
}
if(son)
{
swap(v[k],v[son]);
k=son;
}
}while(son);
}
bool compar(const lup &o,const lup &p)
{
if(o.a>p.a)
return true;
/*if(o.a<p.a)
return false;
if(o.b>p.b)
return true;*/
return false;
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&x,&l);
int i,c=0,j=0;
for(i=0; i<n; i++)
{
scanf("%d%d",&a[i].a,&a[i].b);
if(a[i].a<=x)
a[i].a=(x-a[i].a)/l;
else
{
i--;
n--;
}
}
sort(a,a+n,compar);
for(i=a[0].a; i>=0; i--)
{
for(; (j<n)&&(a[j].a==i); j++)
{
v[++c]=a[j].b;
upheap(c);
}
r+=v[1];
v[1]=v[c];
c--;
downheap(1,c);
}
printf("%llu\n",r);
return 0;
}