Cod sursa(job #807270)

Utilizator radu_bucurRadu Bucur radu_bucur Data 4 noiembrie 2012 15:07:38
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
struct oaie{
	long long d; 
	int w;};
oaie a[100001];
long long sum;
long long v[100011],n,l,nh,  p, x, i;
void schimba (long long z, long long u)
{
	long long aux;
	aux=v[z]; 
	v[z]=v[u]; 
	v[u]=aux;
}
bool cmp (oaie z, oaie u)
{
	if (z.d==u.d) return z.w>u.w;
	return z.d>u.d;
}
void urc (long long p)
{
	if (p==1||v[p]>=v[p/2]) return;
	schimba (v[p],v[p/2]);
	urc (p/2);
}
void cobor(long long p)
{
	int fs,fd,plm;
	fs=p*2; 
	plm=p;
	fd=p*2+1; 
	if (fs<=nh&&v[fs]<v[plm]) plm=fs;
	if (fd<=nh&&v[fd]<v[plm]) plm=fd;
	if (plm!=p)
	{
		schimba(p,plm);
		cobor(plm);
	}
}
int main()
{
	in>>n>>x>>l;
	for (i=1;i<=n;i++)
	{
		in>>a[i].d>>a[i].w;
	}
	p=0; nh=0; sum=0;
	sort (a+1,a+n+1,cmp);
	for (i=1;i<=n;i++)
	{
		if (a[i].d+p*l<=x)
		{
			v[++nh]=a[i].w;
			p++;
			urc(nh);
		}else
		{	
			if(v[1]<a[i].w)
			{   
				v[++nh]=a[i].w;
				schimba (1,nh);
				nh--;
				cobor(1);
			}
		}
	}
	for (i=1;i<=nh;i++) sum=sum+v[i];
	out<<sum;
	return 0;
}