Pagini recente » Cod sursa (job #1295757) | Cod sursa (job #1883642) | Cod sursa (job #2682775) | Cod sursa (job #1661251) | Cod sursa (job #195564)
Cod sursa(job #195564)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define father(k) k>>1
#define left_son(k) k<<1
#define right_son(k) (k<<1)+1
int n,x,l;
int v[100010];
long long r;
struct lup
{
int a,b;
};
lup a[100010];
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;
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);
}
if(c)
{
r+=v[1];
v[1]=v[c];
c--;
if(c)
downheap(1,c);
}
}
printf("%lld\n",r);
return 0;
}