Cod sursa(job #278008)

Utilizator ProtomanAndrei Purice Protoman Data 12 martie 2009 00:51:55
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <algorithm>
#include <stdio.h>

#define f first
#define s second
#define MAX 100010
#define ll long long

using namespace std;

ll n, x, l, adun, dimHeap;
pair <ll, ll> oaie[MAX];
ll maxHeap[MAX];

inline void heapUp(int nod)
{
	if (nod == 1)
		return;

	if (maxHeap[nod] > maxHeap[nod / 2])
	{
		swap(maxHeap[nod], maxHeap[nod / 2]);

		heapUp(nod / 2);
	}
}

inline void heapDown(int nod)
{
	if (2 * nod <= dimHeap)
	{
		int locMax = 2 * nod;

		if (2 * nod < dimHeap)
			if (maxHeap[2 * nod] < maxHeap[2 * nod] + 1)
				locMax++;

		if (maxHeap[nod] < maxHeap[locMax])
		{
			swap(maxHeap[nod], maxHeap[locMax]);

			heapDown(locMax);
		}
	}
}

int main()
{
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);

	scanf("%lld %lld %lld", &n, &l, &x);

	for (int i = 1; i <= n; i++)
		scanf("%lld %lld", &oaie[i].f, &oaie[i].s);

	sort(oaie + 1, oaie + 1 + n);

	int lungPart = 0;
	if (x)
		lungPart = l % x;

	int ramas = 1;
	for (; lungPart <= l; lungPart += x)
	{
		for (; ramas <= n && oaie[ramas].f <= lungPart; ramas++)
		{
			maxHeap[++dimHeap] = oaie[ramas].s;

			heapUp(dimHeap);
		}

		if (dimHeap)
		{
			adun += maxHeap[1];

			maxHeap[1] = maxHeap[dimHeap];
			maxHeap[dimHeap--] = 0;

			heapDown(1);
		}
	}

	printf("%lld", adun);

	fclose(stdin);
	fclose(stdout);
	return 0;
}