Pagini recente » Cod sursa (job #416693) | Cod sursa (job #242984) | Cod sursa (job #54432) | Cod sursa (job #1366692) | Cod sursa (job #1033860)
#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);
v[0].a=0;
a=0;
for(i=1;i<=nr;i++)
{
a+=v[i].a-v[i-1].a;
if(a)
{
h[++k]=v[i].b;
upheap(k);
a--;
}
else if(k && h[1]<v[i].b)
{
h[1]=v[i].b;
}
}
for(i=1;i<=k;i++) s+=h[i];
printf("%lld",s);
return 0;
}