Cod sursa(job #342098)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 20 august 2009 16:57:23
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define lm 100010
#define ll long long

struct oaie
{
	ll d, a;
} v[lm];

int cmp (oaie x, oaie y)
{
	return x.d < y.d;
}

ll h[lm], n, l, m, x;
long long s;

void swap (ll a, ll b)
{
	ll aux;
	aux = h[a];
	h[a] = h[b];
	h[b] = aux;
}

void heap_up (ll nod)
{
	if (nod > 1)
		if (h[nod/2] < h[nod])
		{
			swap (nod, nod/2);
			heap_up (nod/2);
		}
}

void heap_down (ll nod)
{
	if (nod*2 <=m)
	{
		int c = 2*nod;
		if (h[c] < h[c+1]) c++;
		if (h[nod] < h[c])
		{
			swap(nod, c);
			heap_down (c);
		}
	}
}	

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d %d %d",&n, &x, &l);
	int i;
	for (i=1; i<=n; i++) scanf("%d %d",&v[i].d, &v[i].a);
	sort (v+1, v+n+1, cmp);
	long long  k = x - x/l*l;
	for (i=1; i<=n+1; i++)
	{
		if (m>0)
			if (v[i].d > k || i>n)
			{
				s += h[1];
				h[1] = h[m];
				m--;
				heap_down (1);
			}
		while (v[i].d > k) k +=l;
		if (k>x || i>n) break;
		m++;
		h[m] = v[i].a;
		heap_up (m);
	}
	printf("%lld",s);
}