Pagini recente » Cod sursa (job #2016904) | Cod sursa (job #1336889) | Cod sursa (job #722876) | Cod sursa (job #2877306) | Cod sursa (job #1665189)
#include <cstdio>
#include<algorithm>
#define MAX 100000
using namespace std;
int n, x, 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(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--;
down(1);
}
int main()
{
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
int i, dist, m1=0, val, pasmax=-1, j;
scanf("%d%d%lld", &n, &x, &l);
for(i=1;i<=n;i++){
scanf("%d%d", &dist, &val);
if(dist<=x)
{
v[++m1].cost=val;
v[m1].maxp=(x-dist)/l;
if(v[m1].maxp>pasmax)
pasmax=v[m1].maxp;
}
}
sort(v+1, v+m1+1, cresc);
j=1;
for(i=pasmax;i>=0;i--)
{
while(v[j].maxp>=i&&j<=m1)
{
add(j);
j++;
}
if(m>0){
tot+=v[heap[1]].cost;
delete1();
}
}
printf("%lld", tot);
return 0;
}