Cod sursa(job #675715)

Utilizator damgoodLincan Dan damgood Data 7 februarie 2012 23:34:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#include <utility>
#include <functional>
#include <algorithm>

#define MAXN 1000001

using namespace std;
int n, x, l;
long long sum;

pair<int, int> oi[ MAXN ];
int h[MAXN], size;

void read()
{
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);
	
	scanf("%d%d%d", &n, &x, &l);

	for(int i = 1; i <= n; ++i)
	{
		int dist, value;
		scanf("%d%d", &dist, &value);
		oi[i] = make_pair(dist, value);
	}
}

void po()
{
	for(int i = 1; i <= n; ++i)
		printf("%d %d\n", oi[i].first, oi[i].second);
}

void urca(int nod)
{
	if( nod > 1 && h[nod] < h[nod/2] )
	{
		swap(h[ nod ], h[ nod / 2]);
		urca(nod/2);
	}
}
/*
void urca(int nod)
{
	int v = h[ nod ];
		
	while( nod > 1 && v < h[ nod/2 ] )
	{
		h[ nod ] = h[ nod/2 ];
		nod = nod/2;
	}

	h[ nod ] = v;
}
*/
void coboara(int nod)
{
	int son = nod;
	if( 2 * nod <= size && h[ nod ] > h[ 2 * nod ] ) son = 2 * nod;
	if( 2 * nod + 1 <= size && h[ son ] > h[ 2 * nod + 1 ] ) son = 2 * nod + 1;
	if( son != nod ) 
	{
		swap(h[ nod ], h[ son ]);
		coboara(son);
	}
}
/*
void coboara(int nod)
{
	int son = nod;
	do {
		nod = son;
		if( 2 * nod <= size && h[ nod ] > h[ 2 * nod ] ) son = 2 * nod;
		if( 2 * nod + 1 <= size && h[ son ] > h[ 2 * nod + 1 ] ) son = 2 * nod + 1;
		if( son != nod ) 
		{
			swap(h[ nod ], h[ son ]);
		}
		else
			break;
	} while(true);
}
*/
void ph()
{
	for(int i = 1; i <= size; ++i)
		printf("%d ", h[i]);
	printf("\n");
}

void solve()
{
	sort(&oi[1], &oi[n+1], greater< pair<int,int> >());
	
	for(int i = 1; i <= n; ++i)
	{
		if( oi[i].first <= x )
		{
			x -= l;
			h[++size] = oi[i].second;
			urca(size);
		} else
		{
			if( oi[i].second > h[1] )
			{
				h[1] = oi[i].second;
				coboara(1);
			}
		}
	}
	
	for(int i = 1; i <= size; ++i)
		sum += h[i];
}

void printResult()
{
	printf("%lld\n", sum);
}

int main()
{
	read();
	solve();
	printResult();	
	return 0;
}