Pagini recente » Cod sursa (job #2859223) | Cod sursa (job #2258603) | Cod sursa (job #355396) | Cod sursa (job #2981483) | Cod sursa (job #42087)
Cod sursa(job #42087)
#include <stdio.h>
int n, x[100001], a[100001], p, l, tmax, t[100001];
int dm,sol;
void read()
{
int i,d;
scanf("%d%d%d", &n, &p, &l);
for (i = 1; i <= n; i++)
{
scanf("%d%d", &d, &x[i]);
t[i] = (p-d) / l+1;
if (t[i] > tmax)
tmax = t[i];
}
}
void rec_heap(int i)
{
int st, dr, maxim, aux;
while (i<=dm)
{
st = 2*i; dr = 2*i+1;
if (st <= dm && a[st] > a[i])
maxim = st;
else
maxim = i;
if (dr <= dm && a[dr] > a[maxim])
maxim = dr;
if (i != maxim)
{
aux = a[i];
a[i] = a[maxim];
a[maxim] = aux;
i = maxim;
}
else
i=dm+1;
}
}
int extragere_maxim()
{
int v =a [1];
a[1] = a[dm--];
rec_heap(1);
return v;
}
void insert_heap(int v)
{
int i,t,aux;
a[++dm] = v;
for (i = dm; i > 1; i = i/2)
{
t=i/2;
if (a[t]<a[i])
aux = a[t], a[t] = a[i], a[i] = aux;
else
i = 1;
}
}
void rezolv()
{
int j, i;
for (i = tmax; i >= 1; i--)
{ for (j = 1; j <= n; j++)
if (t[j] == i)
insert_heap(x[j]);
sol+=extragere_maxim();
}
}
int main()
{
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
read();
rezolv();
printf("%d\n", sol);
return 0;
}