Cod sursa(job #199849)

Utilizator ProtomanAndrei Purice Protoman Data 20 iulie 2008 21:16:04
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <algorithm>
#define mx 200010

using namespace std;

struct oaie
{
	long t, l;
} oi[mx];
long n, x, l, ac;
long long maxim;
long hp[mx];

inline bool cmp(const oaie &a, const oaie &b)
{
	return (a.t < b.t);
}

void heapup(long x)
{
	if (hp[x] > hp[x / 2] && x > 1)
	{
		swap(hp[x],hp[x / 2]);
		heapup(x / 2);
	}
}

void heapdown(long x)
{
	int maxim = mx - 1;
	if (hp[0] >= (x << 1))
		maxim = x << 1;
	if (hp[0] > (x << 1) && hp[x << 1] < hp[(x << 1) + 1])
		maxim = (x << 1) + 1;
	if (hp[x] < hp[maxim])
	{
		swap(hp[x],hp[maxim]);
		heapdown(maxim);
	}
}

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%ld %ld %ld", &n, &x, &l);
	for (int i = 1; i <= n; i++)
		scanf("%ld %ld", &oi[i].t, &oi[i].l);
	sort(oi+1,oi+1+n,cmp);
	if (l)
		ac = x % l;
	for (int i = 1; i <= n && oi[i].t <= x && ac <= x; i++)
	{
		if (oi[i].t > ac)
		{
			ac += l;
			maxim += (long long) hp[1];
			hp[1] = oi[i].l;
			heapdown(1);
		}
		else
		{
			hp[0]++;
			hp[hp[0]] = oi[i].l;
			heapup(hp[0]);
		}
	}
	while (ac <= x && hp[0])
	{
		ac += l;
		maxim += (long long) hp[1];
		hp[1] = hp[hp[0]];
		hp[0]--;
		heapdown(1);
	}
	printf("%lld\n", maxim);
	fclose(stdin);
	fclose(stdout);
	return 0;
}