Pagini recente » Cod sursa (job #2262741) | Cod sursa (job #1559403) | Cod sursa (job #897621) | Cod sursa (job #2221941) | Cod sursa (job #490646)
Cod sursa(job #490646)
#include <fstream>
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):d(d2),lana(lana2){}
int d, lana;
};
int lana,n,x,l,d,a,HSize=0;
oaie H[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;
H[++HSize]=oaie(d,a);
heap_up(HSize);
}
fin.close();
while(HSize>0)
{
if(H[1].d<=x)
{
x-=l;
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;
}