Pagini recente » Cod sursa (job #1359996) | Cod sursa (job #2389231) | Istoria paginii runda/juniori_2011_1 | Cod sursa (job #99488) | Cod sursa (job #490694)
Cod sursa(job #490694)
#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 d2=0, int lana2=0, int pos2=0):d(d2),lana(lana2),pos(pos2){}
int d, 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;
oaie H[MaxN],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].lana<H[nod].lana)
{
oaie 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].lana<H[st].lana)
{
ind=st;
}
}
int dr=right(nod);
if(dr<=HSize)
{
if(H[ind].lana<H[dr].lana)
{
ind=dr;
}
}
if(ind==nod)
{
break;
}
else
{
oaie 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=d<=x?1:0;
pos+=(x-d)/l;
v[++ind]=oaie(d,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];
heap_up(HSize);
++ind;
}
lana+=H[1].lana;
oaie aux=H[HSize];
H[HSize]=H[1];
H[1]=aux;
--HSize;
heap_down(1);
}
fout<<lana;
fout.close();
return 0;
}