Cod sursa(job #490646)

Utilizator ChallengeMurtaza Alexandru Challenge Data 7 octombrie 2010 11:21:43
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#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;
}