Pagini recente » Cod sursa (job #1854848) | Cod sursa (job #1764621) | Cod sursa (job #41914) | Cod sursa (job #2575844) | Cod sursa (job #490699)
Cod sursa(job #490699)
#include <fstream>
#include <algorithm>
using namespace std;
const char InFile[]="lupu.in";
const char OutFile[]="lupu.out";
const int MaxN=100500;
ifstream fin(InFile);
ofstream fout(OutFile);
struct oaie
{
oaie(int lana2=0, int pos2=0):lana(lana2),pos(pos2){}
int lana, pos;
};
bool oaie_cmp(oaie a, oaie b)
{
return b.pos<a.pos;
}
long long lana;
int n,x,l,d,a,HSize=0,ind;
int H[MaxN];
oaie v[MaxN];
inline int left(int nod)
{
return nod<<1;
}
inline int right(int nod)
{
return (nod<<1)+1;
}
inline int parent(int nod)
{
return nod>>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 st=left(nod);
int ind=nod;
if(st<=HSize)
{
if(H[ind]<H[st])
{
ind=st;
}
}
int dr=right(nod);
if(dr<=HSize)
{
if(H[ind]<H[dr])
{
ind=dr;
}
}
if(ind==nod)
{
break;
}
else
{
int aux=H[ind];
H[ind]=H[nod];
H[nod]=aux;
nod=ind;
}
}
}
int main()
{
fin>>n>>x>>l;
for(register int i=0;i<n;++i)
{
fin>>d>>a;
int pos=1;
pos+=(x-d)/l;
v[++ind]=oaie(a,pos);
}
fin.close();
sort(v+1,v+1+n,oaie_cmp);
ind=1;
while(v[ind].pos>0)
{
int dpos=v[ind].pos;
while(v[ind].pos==dpos)
{
H[++HSize]=v[ind++].lana;
heap_up(HSize);
}
if(HSize>=1)
{
lana+=H[1];
H[1]=H[HSize--];
heap_down(1);
}
}
fout<<lana;
fout.close();
return 0;
}