Cod sursa(job #342102)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 20 august 2009 17:11:25
Problema Lupul Urias si Rau Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define lm 100010

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

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

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

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

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

void heap_down (int 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 (v[i].d > k || i>n)
		{
			if (m>0)
			{
				s += h[1];
				h[1] = h[m];
				m--;
				heap_down (1);
			}
			k += l;
			if (k>x) break;
		}
		if (i>n) break;
		if (v[i].d <=k)
		{
			m++;
			h[m] = v[i].a;
		}
		heap_up (m);
	}
	printf("%lld",s);
}