Cod sursa(job #547535)

Utilizator avram_florinavram florin constantin avram_florin Data 6 martie 2011 14:20:51
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include<fstream>
#include<algorithm>
#define MaxN 100005

using namespace std;

ifstream f ("lupu.in");
ofstream g ("lupu.out");

struct sheep{
		int time,lana;
		};
sheep a[MaxN],h[MaxN];
int nh;

struct cmp{
	bool operator()(const sheep &a,const sheep &b)
	{	return a.time>b.time;
	}
};

inline int maxim(int a,int b)
{
	if(a>b)
		return a;
	return b;
}

inline bool compar(sheep a,sheep b)
{
	if( a.lana == b.lana )
		return a.time < b.time;
		else
		return a.lana > b.lana;
}

void swap( sheep &a , sheep &b )
{
	sheep aux;
	aux = a;
	a = b;
	b = aux;
}

inline void downHeap(int x)
{
	int y = x;
	if( x<<1 <= nh && compar(h[x<<1],h[y]) )
		y = x<<1;
	if( x<<1 < nh && compar(h[x<<1+1],h[y]) )
		y = x<<1+1;
	if( x != y )
		{
			swap(h[x],h[y]);
			downHeap(y);
		}
}

inline void upHeap(int x)
{
	if( x <= 1 )
		return ;
	if( compar(h[x],h[x>>1]) )
		{
			swap(h[x],h[x>>1]);
			upHeap(x>>1);
		}
}

int main()
{
	int n,X,L,x,y,i,j,dim=0,Tmax = -1;
	long long rez =0;
	f >> n >> X >> L;
	for( i = 1 ; i <= n ; i++ )
		{
			f >> x >> y;
			if( x <= X )
				{
					a[++dim].time = (X-x)/L+1;
					a[dim].lana = y;
					Tmax = maxim(Tmax,a[dim].time);
				}
		}
	sort(a+1,a+dim+1,cmp());
	for( i = Tmax ,j=1; i ; i-- )
		{
			for( ; j <= dim && a[j].time == i; j++ )
				{
					h[++nh] = a[j];
					upHeap(nh);
				}
			while( nh && h[1].time < i )
				{
					h[1] = h[nh];
					nh--;
					downHeap(1);
				}
			if( nh )
				{
					rez += h[1].lana;
					h[1] = h[nh];
					nh--;
					downHeap(1);
				}
		}
	g << rez << '\n';
	return 0;
}