Pagini recente » Cod sursa (job #2730830) | Cod sursa (job #2947244) | Cod sursa (job #374067) | Cod sursa (job #1854520) | Cod sursa (job #1185717)
#include <stdio.h>
#define N_MAX 100000
int heap[ N_MAX + 1 ], ind = 1, dist[ N_MAX ], lan[ N_MAX ];
void qs ( int st, int dr ){
int i = st, j = dr, piv = dist[ ( st + dr ) / 2 ], aux;
while ( i <= j ){
while ( dist[ i ] > piv ) i++;
while ( dist[ j ] < piv ) j--;
if ( i <= j ){
aux = dist[ i ]; dist[ i ] = dist[ j ]; dist[ j ] = aux;
aux = lan[ i ]; lan[ i ] = lan[ j ]; lan[ j ] = aux;
i++; j--;
}
}
if ( st < j ) qs ( st, j );
if ( i < dr ) qs ( i, dr );
return ;
}
void AddToHeap ( int x ){
int poz = ind;
while ( poz > 1 && heap[ poz / 2 ] > x ){
heap[ poz ] = heap[ poz / 2 ];
poz /= 2;
}
heap[ poz ] = x;
ind++;
return ;
}
int DeleteFromHeap (){
int rez = heap[ 1 ];
int x = heap[ ind - 1 ], poz = 1, a, b, cpoz = poz - 1;
ind--;
while ( poz * 2 < ind && cpoz != poz ){
a = poz * 2; b = poz * 2 + 1;
cpoz = poz;
if ( poz * 2 + 1 < ind ){
if ( heap[ a ] < heap[ b ] ){
if ( heap[ a ] < x ){
heap[ poz ] = heap[ a ];
poz = a;
}
}
else{
if ( heap[ b ] < x ){
heap[ poz ] = heap[ b ];
poz = b;
}
}
}
else{
if ( heap[ a ] < x ){
heap[ poz ] = heap[ a ];
poz = a;
}
}
}
heap[ poz ] = x;
return rez;
}
int main()
{
FILE *in = fopen ( "lupu.in", "r" );
int n, x, l;
fscanf ( in, "%d%d%d", &n, &x, &l );
int i;
for ( i = 1; i <= n; i++ ){
fscanf ( in, "%d%d", &dist[ i ], &lan[ i ] );
}
qs ( 1, n );
for ( i = 1; i <= n; i++ ){
if ( dist[ i ] + ( ind - 1 ) * l <= x ) AddToHeap ( lan[ i ] );
else if ( ind > 1 && dist[ i ] + ( ind - 2 ) * l <= x
&& heap[ 1 ] < lan[ i ] ){
DeleteFromHeap ();
AddToHeap ( lan[ i ] );
}
}
fclose ( in );
FILE *out = fopen ( "lupu.out", "w" );
long long rez = 0;
while ( ind > 1 ) rez += DeleteFromHeap ();
fprintf ( out, "%lld", rez );
fclose ( out );
return 0;
}