Pagini recente » Cod sursa (job #2149044) | Cod sursa (job #3298) | Cod sursa (job #889320) | Cod sursa (job #2350799) | Cod sursa (job #981788)
Cod sursa(job #981788)
#include<stdio.h>
#include<algorithm>
#define maxn 100005
using namespace std;
struct sheep_step{int t,val;} a[maxn];
int n,dx,dl,nh,tmax;
int h[maxn];
long long sol;
void read()
{
int dist,fur,nr;
scanf("%d%d%d",&n,&dx,&dl);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&dist,&fur);
nr=0; while(dist<=dx) nr++,dist+=dl;
a[i].t=nr; a[i].val=fur;
}
}
int cmp(sheep_step x,sheep_step y) { return x.t>y.t; }
void heap_up(int k)
{
if(k<=1) return;
int i=k/2;
if(h[i]<h[k]) {swap(h[i],h[k]); heap_up(i);}
}
void heap_dw(int k)
{
int i=2*k;
if(i<=nh)
{
if(i+1<=nh && h[i+1]>h[i]) i++;
if(h[i]>h[k]) {swap(h[i],h[k]); heap_dw(i);}
}
}
void extract()
{
swap(h[1],h[nh--]);
heap_dw(1);
}
void solve()
{
int j=1;
sort(a+1,a+n+1,cmp);
tmax=a[1].t;
for(int i=tmax;i>=1;i--)
{
for(;a[j].t==i && j<=n;j++) {h[++nh]=a[j].val; heap_up(nh);}
if(nh>0) sol+=h[1],extract();
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
read();
solve();
printf("%lld",sol);
fclose(stdin);
fclose(stdout);
return 0;
}