Cod sursa(job #199881)

Utilizator ProtomanAndrei Purice Protoman Data 20 iulie 2008 23:32:06
Problema Lupul Urias si Rau Scor 68
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <algorithm>
#define mx 100010

using namespace std;

struct oaie
{
	long t, l;
} oi[mx];
long n, x, l, ac, h;
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)
{
	long m = mx - 1;
	if (h >= (x << 1))
		m = x << 1;
	if (h > (x << 1))
		if (hp[x << 1] < hp[(x << 1) + 1])
			m = (x << 1) + 1;
	if (hp[x] < hp[m])
	{
		swap(hp[x],hp[m]);
		heapdown(m);
	}
}

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);
	ac = x % l;
	for (int i = 1; i <= n && oi[i].t <= x && ac <= x; i++)
	{
		if (oi[i].t > ac)
		{
			ac += l;
			maxim += hp[1];
			hp[1] = oi[i].l;
			heapdown(1);
		}
		else
		{
			h++;
			hp[h] = oi[i].l;
			heapup(h);
		}
	}
	while (ac <= x && h)
	{
		ac += l;
		maxim += hp[1];
		hp[1] = hp[h];
		h--;
		heapdown(1);
	}
	printf("%ld\n", maxim);
	fclose(stdin);
	fclose(stdout);
	return 0;
}