Cod sursa(job #710440)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 martie 2012 18:24:30
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <algorithm>

#define LL long long
#define NMax 100005
#define t first
#define p second

using namespace std;

int N, H[NMax], Pos[NMax];
pair <int, LL> P[NMax];
LL TotalP;

inline bool Compare (int &X, int &Y)
{
	return P[X].p>P[Y].p;
}

inline void Swap (int &X, int &Y)
{
	swap (Pos[H[X]], Pos[H[Y]]);
	swap (H[X], H[Y]);
}

inline void Sift (int &X)
{
	int S=X<<1;
	if (S+1<=H[0] and Compare (H[S+1], H[S])) ++S;
	if (S<=H[0] and Compare (H[S], H[X]))
	{
		Swap (X, S); Sift (S);
	}
}

inline void Percolate (int &X)
{
	int F=X>>1;
	if (F>0 and Compare (H[X], H[F]))
	{
		Swap (X, F); Percolate (F);
	}
}

inline void Insert (int X)
{
	H[++H[0]]=X;
	Percolate (H[0]);
}

inline void Delete (int X)
{
	if (X>H[0]) return;
	Swap (X, H[0]);
	Pos[H[H[0]]]=0; H[H[0]]=0; --H[0];
	Sift (X);
}

void Solve ()
{
	sort (P+1, P+N+1); reverse (P+1, P+N+1);
	for (int i=P[1].t, j=1; i>=0; --i)
	{
		for (; P[j].t>=i and j<=N; Insert (j), ++j);
		TotalP+=P[H[1]].p;
		Delete (1);
	}
}

void Read ()
{
	freopen ("lupu.in", "r", stdin);
	int X, L;
	scanf ("%d %d %d", &N, &X, &L);
	for (int i=1; i<=N; ++i)
	{
		scanf ("%d %lld", &P[i].t, &P[i].p);
		P[i].t=(X-P[i].t)/L;
	}
}

void Print ()
{
	freopen ("lupu.out", "w", stdout);
	printf ("%lld\n", TotalP);
}

int main ()
{
	Read ();
	Solve ();
	Print ();
	return 0;
}