Pagini recente » Cod sursa (job #2219564) | Cod sursa (job #215945) | Cod sursa (job #2023390) | Cod sursa (job #1937108) | Cod sursa (job #278009)
Cod sursa(job #278009)
#include <algorithm>
#include <stdio.h>
#define f first
#define s second
#define MAX 100010
#define ll long long
using namespace std;
ll n, x, l, adun, dimHeap;
pair <ll, ll> oaie[MAX];
ll maxHeap[MAX];
inline void heapUp(int nod)
{
if (nod == 1)
return;
if (maxHeap[nod] > maxHeap[nod / 2])
{
swap(maxHeap[nod], maxHeap[nod / 2]);
heapUp(nod / 2);
}
}
inline void heapDown(int nod)
{
if (2 * nod <= dimHeap)
{
int locMax = 2 * nod;
if (2 * nod < dimHeap)
if (maxHeap[2 * nod] < maxHeap[2 * nod + 1])
locMax++;
if (maxHeap[nod] < maxHeap[locMax])
{
swap(maxHeap[nod], maxHeap[locMax]);
heapDown(locMax);
}
}
}
int main()
{
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
scanf("%lld %lld %lld", &n, &l, &x);
for (int i = 1; i <= n; i++)
scanf("%lld %lld", &oaie[i].f, &oaie[i].s);
sort(oaie + 1, oaie + 1 + n);
int lungPart = 0;
if (x)
lungPart = l % x;
int ramas = 1;
for (; lungPart <= l; lungPart += x)
{
for (; ramas <= n && oaie[ramas].f <= lungPart; ramas++)
{
maxHeap[++dimHeap] = oaie[ramas].s;
heapUp(dimHeap);
}
if (dimHeap)
{
adun += maxHeap[1];
maxHeap[1] = maxHeap[dimHeap];
maxHeap[dimHeap--] = 0;
heapDown(1);
}
}
printf("%lld", adun);
fclose(stdin);
fclose(stdout);
return 0;
}