Pagini recente » Cod sursa (job #2740014) | Cod sursa (job #1553380) | Cod sursa (job #693849) | Cod sursa (job #804711) | Cod sursa (job #196259)
Cod sursa(job #196259)
#include <cstdio>
#include <algorithm>
#define N_MAX 1<<17
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN "lupu.in"
#define OUT "lupu.out"
using namespace std;
int suma,T_MAX,N,X,L;
int T[N_MAX],lana[N_MAX],H[N_MAX];
inline int father(int nod) {return nod / 2; }
inline int left_son(int nod) {return nod * 2; }
inline int right_son(int nod) {return nod * 2 + 1;}
void scan()
{
int x;
freopen(IN, "r",stdin);
freopen(OUT, "w",stdout);
scanf("%d%d%d", &N,&X,&L);
FOR(i,1,N)
{
scanf("%d%d",&x,&lana[i]);
T[i]=(X-x)/L;
if(T[i]>T_MAX)
T_MAX=T[i];
}
}
void percolate(int N, int K)
{
int key = H[K];
while ((K > 1) && (key > H[father(K)]))
{
H[K] = H[father(K)];
K = father(K);
}
H[K] = key;
}
void sift(int N, int K)
{
int son;
do
{
son = 0;
if (left_son(K) <= N)
{
son = left_son(K);
if (right_son(K) <= N && H[right_son(K)] > H[left_son(K)])
{
son = right_son(K);
}
if (H[son] <= H[K])
{
son = 0;
}
}
if (son)
{
swap(H[K], H[son]);
K = son;
}
} while (son);
}
void cut(int N, int K)
{
H[K] = H[N];
--N;
if ((K > 1) && (H[K] > H[father(K)]))
{
percolate(N, K);
}
else
{
sift(N, K);
}
}
void insert(int N, int key)
{
H[N] = key;
percolate(N, N);
}
void solve()
{
int last=0;
FOR(val,0,T_MAX)
{
FOR(i,1,N)
{
if(T[i]!=T_MAX-val)
continue;
insert(++last,lana[i]);
}
if(last)
{
suma+=H[1];
cut(last,1);
--last;
}
}
printf("%d\n",suma);
}
int main()
{
scan();
solve();
return 0;
}