Pagini recente » Cod sursa (job #1188573) | Cod sursa (job #1535846) | Cod sursa (job #492227) | Cod sursa (job #2891303) | Cod sursa (job #43043)
Cod sursa(job #43043)
#include <stdio.h>
#define NMAX 100001
int n, a[NMAX], p, l, tmax;
int dm,sol;
typedef struct
{
int t, x;
}VEC;
VEC t[NMAX];
void read()
{
int i,d;
scanf("%d%d%d", &n, &p, &l);
for (i = 1; i <= n; i++)
{
scanf("%d%d", &d, &t[i].x);
t[i].t = (p-d) / l+1;
if (t[i].t > tmax)
tmax = t[i].t;
}
}
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;
}
}
int partitie(int st, int dr)
{
int i, j, pivot;
VEC aux;
i=st-1;
j=dr+1;
pivot=t[(st+dr)/2].t;
while (1)
{
do {++i;} while (t[i].t>pivot);
do {--j;} while (t[j].t<pivot);
if (i<j)
{ aux=t[i]; t[i]=t[j]; t[j]=aux;}
else
return j;
}
}
void sort(int st, int dr)
{
int m;
if (st < dr)
{
m = partitie(st, dr);
sort(st, m);
sort(m+1, dr);
}
}
void rezolv()
{
int j, i;
sort(1,n);
for (i =1; i <= n; i=j+1)
{ for (j = i; t[j].t == t[j+1].t && j < n; j++)
insert_heap(t[j].x);
insert_heap(t[j].x);
sol += extragere_maxim();
}
}
int main()
{
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
read();
rezolv();
printf("%d\n", sol);
return 0;
}