Pagini recente » Cod sursa (job #2667570) | Cod sursa (job #1869925) | Cod sursa (job #1150111) | Cod sursa (job #637148) | Cod sursa (job #491165)
Cod sursa(job #491165)
#include <fstream>
#include <algorithm>
using namespace std;
const char InFile[]="lupu.in";
const char OutFile[]="lupu.out";
const int MaxN=100010;
struct oaie
{
oaie(int lana2=0, int pos2=0):lana(lana2),pos(pos2){}
int lana,pos;
};
ifstream fin(InFile);
ofstream fout(OutFile);
int H[MaxN],HSize,n,x,l,d,a;
long long lana;
oaie V[MaxN];
bool cmp_oaie(oaie a, oaie b)
{
return a.pos>b.pos;
}
inline int parent(int nod)
{
return nod>>1;
}
inline int left(int nod)
{
return nod<<1;
}
inline int right(int nod)
{
return (nod<<1)+1;
}
void heap_up(int nod)
{
int p=parent(nod);
while(p>0 && H[p]<H[nod])
{
int aux=H[p];
H[p]=H[nod];
H[nod]=aux;
nod=p;
p=parent(nod);
}
}
void heap_down(int nod)
{
while(true)
{
int ind=nod;
int l=left(nod);
if(l<=HSize)
{
if(H[l]>H[ind])
{
ind=l;
}
}
int r=right(nod);
if(r<=HSize)
{
if(H[r]>H[ind])
{
ind=r;
}
}
if(ind!=nod)
{
int aux=H[nod];
H[nod]=H[ind];
H[ind]=aux;
nod=ind;
}
else
{
break;
}
}
}
int main()
{
fin>>n>>x>>l;
for(register int i=0;i<n;++i)
{
fin>>d>>a;
V[i].lana=a;
V[i].pos=(x-d)/l+1;
}
fin.close();
sort(V,V+n,cmp_oaie);
int ind=0;
for(register int i=V[0].pos;i>0;--i)
{
while(V[ind].pos==i)
{
H[++HSize]=V[ind++].lana;
heap_up(HSize);
}
if(HSize>0)
{
lana+=(long long)H[1];
H[1]=H[HSize--];
heap_down(1);
}
}
fout<<lana;
fout.close();
return 0;
}