Cod sursa(job #490699)

Utilizator ChallengeMurtaza Alexandru Challenge Data 7 octombrie 2010 16:03:05
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#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;
}