Pagini recente » Cod sursa (job #2274085) | Cod sursa (job #1166563) | Cod sursa (job #2492483) | Cod sursa (job #597629) | Cod sursa (job #1665134)
#include <cstdio>
#include<algorithm>
#define MAX 100000
using namespace std;
int n, x, m;
long long cf, l, tot;
struct oite_vesele{
int dist, cost;
}; oite_vesele v[MAX+1];
int heap[MAX+1];
bool cresc(oite_vesele a, oite_vesele b)
{
return (a.dist<b.dist);
}
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(father(x)>0&&(f))
{
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(son_left(x)<=m&&(f))
{
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, f=1;
scanf("%d%d%lld", &n, &x, &l);
for(i=1;i<=n;i++)
scanf("%d%d", &v[i].dist, &v[i].cost);
sort(v+1, v+n+1, cresc);
i=1;
while((f)&&cf<=x)
{
while(m>0&&v[heap[1]].dist+cf>x)
delete1();
if(m==0)
f=0;
while(i<=n&&v[i].dist+cf<=x){
add(i);
i++;
f=1;
}
if(m!=0){
tot+=v[heap[1]].cost;
delete1();
cf+=l;
}
}
printf("%lld", tot);
return 0;
}