Cod sursa(job #432292)

Utilizator ooctavTuchila Octavian ooctav Data 2 aprilie 2010 01:37:41
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
long long N, X, L, T = 0;
long long REZ = 0;
const long long NMAX = 100100;
long long O[NMAX];
long long lana[NMAX];
long long B[NMAX];
long long ln2[NMAX];
long long timp, ln;

void citire()
{
	scanf("%lld%lld%lld",&N,&X,&L);
	for(long long i = 1; i <= N ; i++)
	{
		scanf("%lld %lld", &timp, &ln);
		if(timp > X)	continue;
		timp = 1 + (X - timp) / L;
		if(timp > T)
			T = timp;
		O[i] = timp;
		lana[i] = ln;
	}
}

void merge_sort(long long l, long long r)
{
    long long m = (l + r) >> 1, i, j, k;
    if (l == r) return;
    merge_sort(l, m);
    merge_sort(m + 1, r);
    for (i=l, j=m+1, k=l; i<=m || j<=r; )
        if (j > r || (i <= m && O[i] > O[j]))
		{
            B[k] = O[i];
			ln2[k++] = lana[i++];
		}
        else
		{
            B[k] = O[j];
			ln2[k++] = lana[j++];
		}
    for (k = l; k <= r; k++) O[k] = B[k], lana[k] = ln2[k];
}

struct cmp
{
	bool operator()(const long long &a, const long long &b)const
	{
		return lana[a] < lana[b];
	}
};

priority_queue <long long, vector<long long>, cmp> Q;

void rezolva()
{
	long long nr = 1;
	for(long long i = T ; i ; --i)
	{
		long long j = nr;
		while(O[j] == O[nr] && j <= N)
		{
			Q.push(j);
			j++;
		}
		if(!Q.empty())
		{
			REZ += lana[Q.top()];
			Q.pop();
		}
		nr = j;
	}
}

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	citire();
	if(N == 1)
	{
		printf("%lld",lana[1]);
		return 0;
	}
	merge_sort(1, N);
	rezolva();
	printf("%lld",REZ);

	return 0;
}