Pagini recente » Cod sursa (job #753157) | Cod sursa (job #1358411) | Cod sursa (job #586722) | Cod sursa (job #2665688) | Cod sursa (job #1665215)
#include <cstdio>
#include<algorithm>
#define MAX 100000
using namespace std;
int n, x1, m;
long long cf, l, tot;
struct oite_vesele{
int maxp, cost;
}; oite_vesele v[MAX+1];
int heap[MAX+1];
bool cresc(oite_vesele a, oite_vesele b)
{
return (a.maxp>b.maxp);
}
inline int father(int x){ return x/2;};
inline int son_left(int x){ return x*2;};
inline int son_right(int x){ return x*2+1;};
inline void swap1(int a, int b)
{
int aux=heap[a];
heap[a]=heap[b];
heap[b]=aux;
}
inline void up(int x)
{
int p, f=1;
while((f)&&father(x)>0)
{
f=0;
p=father(x);
if(v[heap[p]].cost<v[heap[x]].cost)
{
swap1(p, x);
f=1;
}
x=p;
}
}
inline void down(int x)
{
int p, q, f=1;
while((f)&&son_left(x)<=m)
{
f=0;
p=son_left(x);
q=son_right(x);
if(q<=m&&v[heap[p]].cost<v[heap[q]].cost)
p=q;
if(v[heap[p]].cost>v[heap[x]].cost)
{
swap1(p, x);
f=1;
}
x=p;
}
}
inline void add(int x)
{
heap[++m]=x;
up(m);
}
inline void delete1()
{
swap1(1, m);
m--;
if(m>0)
down(1);
}
int main()
{
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
int i, dist, val, j, last;
scanf("%d%d%lld", &n, &x1, &l);
for(i=1;i<=n;i++){
scanf("%d%d", &dist, &val);
v[i].cost=val;
if(x1-dist>=0)
v[i].maxp=(x1-dist)/l;
else v[i].maxp=-1;
}
sort(v+1, v+n+1, cresc);
j=1;
for(i=v[1].maxp;i>=0;i--)
{
while(j<=n&&v[j].maxp>=i)
{
add(j);
j++;
}
if(m>0){
tot+=v[heap[1]].cost;
delete1();
}
}
printf("%lld", tot);
return 0;
}