Pagini recente » Cod sursa (job #1058269) | Cod sursa (job #2001398) | Cod sursa (job #1028802) | Cod sursa (job #2752531) | Cod sursa (job #710440)
Cod sursa(job #710440)
#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;
}