Cod sursa(job #547961)

Utilizator avram_florinavram florin constantin avram_florin Data 6 martie 2011 21:09:40
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream>
#include<algorithm>
#include<cstdio>

using namespace std;
const int MaxN = 100005;
const char in[] = "lupu.in";
const char out[] = "lupu.out";

struct oaie{
		int dist,lana;
}z[MaxN];
int nh,h[MaxN];
long long rez;
pair<int,int> v[MaxN];

ifstream f(in);
ofstream g(out);

inline void swap(int i,int j)
{
	int aux = h[i];
	h[i] = h[j];
	h[j] = aux;
}

void upHeap(int i)
{
	if( h[i] > h[i>>1] && i>>1 )
		{
			swap(i,i>>1);
			upHeap(i>>1);
		}
}

void downHeap(int i)
{
	int m = i;
	if( i<<1 <= nh && h[m] < h[i<<1] )
		m = i<<1;
	if( i<<1+1 <= nh && h[m] < h[i<<1+1] )
		m = i<<1+1;
	if( m != i)
		{
			swap(i,m);
			downHeap(m);
		}
}

int main()
{
	int n,x,l,i,tmax;
	f >> n >> x >> l;
	for( i = 1 ; i <= n ; i++ )
		{
			f >> z[i].dist >> z[i].lana;
			v[i].first = (x-z[i].dist)/l;
			v[i].second = i;
		}
	sort(v+1,v+n+1);
	tmax = v[n].first;
	nh = 0;
	for( i = n ; i && tmax >= 0 ; )
		{
			while( tmax == v[i].first && i )
				{
					h[++nh] = z[v[i].second].lana;
					upHeap(nh);
					i--;
				}
			if( nh )
				{
					rez +=(long long)h[1];
					h[1] = h[nh];
					nh--;
					downHeap(1);
				}
			--tmax;
		}
	g << rez << '\n';
	f.close();
	g.close();
	return 0;
}