Cod sursa(job #547570)

Utilizator avram_florinavram florin constantin avram_florin Data 6 martie 2011 14:48:28
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream>
#include<algorithm>
#define MaxN 100001

using namespace std;

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

struct sheep{
		int dist,lana;
		};
sheep a[MaxN];
int n,N,X,L,Tmax,nh,h[MaxN];
long long rez;

bool cmp(sheep a , sheep b)
{
	if( a.dist == b.dist )
		return a.lana > b.lana;
		else
		return a.dist < b.dist;
}

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

inline void upHeap(int x)
{
	if( x > 1 )
		if( h[x] > h[x>>1] )
			{
				int aux = h[x];
				h[x] = h[x>>1];
				h[x>>1] = aux;
				upHeap(x>>1);
			}
}

inline void downHeap(int x)
{
	int m = x;
	if( x << 1 <= nh && h[x<<1] > h[m] )
		m  = x<<1;
	if( x << 1 + 1 <= nh && h[x<<1+1] > h[m] )
		m = x<<1 + 1;
	if( m != x)
		{
			int aux = h[x];
			h[x] = h[m];
			h[m] = aux;
			downHeap(m);
		}
}

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