Pagini recente » Cod sursa (job #928999) | Cod sursa (job #3143361) | Cod sursa (job #2560734) | Cod sursa (job #2504765) | Cod sursa (job #782462)
Cod sursa(job #782462)
#include <fstream>
#include <algorithm>
#define distanta first
#define profit second
#define NMAX 100100
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
pair <int , int> V[NMAX];
int N,X,L,Vf,Heap[NMAX];
long long sol;
inline int father(int k)
{
return k/2;
}
inline int left(int k)
{
return 2*k;
}
inline int right(int k)
{
return 2*k+1;
}
inline int cmp(int a,int b)
{
if(V[Heap[a]].profit>V[Heap[b]].profit) return 1;
else return 0;
}
void up(int nod)
{
while(nod>1 && cmp(nod,father(nod)))
{
swap(Heap[nod],Heap[father(nod)]);
nod=father(nod);
}
}
void down(int nod)
{
int son;
do
{
son=0;
if(left(nod)<=Vf)
{
son=left(nod);
if(right(nod)<=Vf && cmp(right(nod),left(nod)))
son=right(nod);
if(cmp(nod,son)) son=0;
}
if(son)
{
swap(Heap[nod],Heap[son]);
nod=son;
}
}
while(son);
}
void citire()
{
f>>N>>X>>L;
for(int i=1; i<=N; i++)
{
f>>V[i].distanta>>V[i].profit;
V[i].distanta=(X-V[i].distanta)/L+1;
}
}
int main()
{
int i , k;
citire();
sort(V+1,V+N+1);
reverse(V+1,V+N+1);
for(k=V[1].distanta,i=1;k>=1;k--)
{
for(;V[i].distanta==k && i<=N;i++)
{
Heap[++Vf]=i;
up(Vf);
}
if(Vf)
{
sol+=V[Heap[1]].profit;
Heap[1]=Heap[Vf--];
down(1);
}
}
g<<sol<<"\n";
}