Pagini recente » Cod sursa (job #1697368) | Cod sursa (job #1785240) | Cod sursa (job #1838842) | Cod sursa (job #831538) | Cod sursa (job #1033694)
#include <cstdio>
#include <algorithm>
using namespace std;
struct lup
{
int a,b;
};
lup v[100010],aux;
long long int h[100010],s;
int a,b,i,nr,k,mid,d,x,n;
void sort1(int st,int dr)
{
int i=st,j=dr;
mid=v[(i+j)/2].a;
do
{
while(v[i].a>mid) i++;
while(v[j].a<mid) j--;
if(i<=j)
{
aux=v[i];v[i]=v[j];v[j]=aux;
i++;j--;
}
}while(i<=j);
if(i<dr) sort1(i,dr);
if(j>st) sort1(st,j);
}
void upheap(int i)
{
if(i/2 && h[i]>h[i/2])
{
swap(h[i],h[i/2]);
upheap(i/2);
}
}
void downheap(int i)
{
if(i*2+1<=k && h[i]<h[i*2+1] && h[i*2+1]>=h[i*2])
{
swap(h[i],h[i*2+1]);
downheap(i*2+1);
}
else if(i*2<=k && h[i]<h[i*2] && h[i*2]>=h[i*2+1])
{
swap(h[i],h[i*2]);
downheap(i*2);
}
}
int main()
{
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
scanf("%d%d%d",&n,&d,&x);
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
if(a<=d)
{
v[++nr].a=1+(d-a)/x;
v[nr].b=b;
}
}
sort1(1,nr);
h[++k]=v[1].b;
for(i=2;i<=nr;i++)
{
if(v[i].a==v[i-1].a)
{
h[++k]=v[i].b;
upheap(k);
}
else
{
s+=h[1];
h[1]=v[i].b;
downheap(1);
}
}
s+=h[1];
printf("%lld",s);
return 0;
}