Pagini recente » Cod sursa (job #1560153) | Cod sursa (job #1967976) | Rating Radu-Bogdan Croitoru (dotix) | Istoria paginii utilizator/madalici | Cod sursa (job #371719)
Cod sursa(job #371719)
#include <stdio.h>
#include <algorithm>
#include <set>
#define N 1<<17
#define pb push_back
using namespace std;
int n,x,l,heap[N],r;
long long rez;
struct oaie
{
int val,lana;
};
struct timp
{
int x,c;
};
timp T[N];
oaie v[N];
bool comp(timp a,timp b)
{
if (a.x>b.x)
return 1;
return 0;
}
void read()
{
scanf("%d%d%d",&n,&x,&l);
int i;
for (i=1; i<=n; i++)
{
scanf("%d%d",&v[i].val,&v[i].lana);
if (x<=v[i].val)
{
T[i].x=1;
T[i].c=v[i].lana;
}
else
{
T[i].x=(x-v[i].val)/l+1;
T[i].c=v[i].lana;
}
}
sort(T+1,T+n+1,comp);
}
void interschimba(int poz1, int poz2)
{
int temp = heap[poz1];
heap[poz1] = heap[poz2];
heap[poz2] = temp;
}
void mut_in_sus(int poz)
{
if (poz > 1 && heap[poz/2] < heap[poz])
{
interschimba(poz, poz/2);
mut_in_sus(poz/2);
}
}
void mut_in_jos(int poz)
{
if ((2*poz <= r && heap[poz] < heap[2*poz] ) ||
(2*poz+1<= r && heap[poz] < heap[2*poz+1]))
{
int maximum = 2*poz;
if (2*poz+1 <= r && heap[2*poz+1] > heap[2*poz])
maximum = 2*poz+1;
interschimba(poz, maximum);
mut_in_jos(maximum);
}
}
void solve()
{
int valoare=T[1].x,poz=0;
while (valoare>=1)
{
while (T[poz+1].x==valoare)
{
poz++;
heap[++r]=T[poz].c;
mut_in_sus(r);
}
if (r)
{
rez+=heap[1];
heap[1]=heap[r];
r--;
mut_in_jos(1);
}
valoare--;
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
read();
solve();
printf("%lld\n",rez);
return 0;
}