Pagini recente » Cod sursa (job #213531) | Cod sursa (job #1215638) | Cod sursa (job #1257238) | Cod sursa (job #2367949) | Cod sursa (job #2809931)
#include <stdio.h>
#include <iostream>
#define N 100000
struct node {
int dis;
int cost;
};
bool operator > ( const node& a, const node& b ) {
if ( a.cost == b.cost )
return (a.dis < b.dis);
return (a.cost > b.cost);
}
bool operator < ( const node& a, const node& b ) {
return !(a.cost > b.cost);
}
node heap[N];
int nheap;
int parent( int nod ) { return (nod - 1) / 2; }
int leftChild( int nod ) { return nod * 2 + 1; }
int rightChild( int nod ) { return nod * 2 + 2; }
void upHeap( int nod ) {
while ( nod && heap[parent( nod )] < heap[nod] ) {
std::swap( heap[parent( nod )], heap[nod] );
nod = parent( nod );
}
}
void downHeap( int nod ) {
int maxx = nod;
if ( leftChild( nod ) < nheap && heap[leftChild( nod )] > heap[maxx] )
maxx = leftChild( nod );
if ( rightChild( nod ) < nheap && heap[rightChild( nod )] > heap[maxx] )
maxx = rightChild( nod );
if ( nod != maxx ) {
std::swap( heap[maxx], heap[nod] );
downHeap( maxx );
}
}
void addToHeap( node val ) {
heap[nheap] = val;
upHeap( nheap );
nheap ++;
}
node removeMin() {
node aux = heap[0];
heap[0] = heap[-- nheap];
downHeap( 0 );
return aux;
}
node getMin() { return heap[0]; }
bool isHeapEmpty() { return (nheap == 0); }
/*void afis( int nod ) {
if ( nod >= nheap )
return;
printf( "%d %d\n", heap[nod].dis, heap[nod].cost );
afis( leftChild( nod ) );
afis( rightChild( nod ) );
}*/
int main() {
FILE *fin, *fout;
int n, range, pas, ans, addDis;
node x;
fin = fopen( "lupu.in", "r" );
fscanf( fin, "%d%d%d", &n, &range, &pas );
for ( int i = 0; i < n; i ++ ) {
fscanf( fin, "%d%d", &x.dis, &x.cost );
addToHeap( x );
}
fclose( fin );
//afis( 0 );
ans = addDis = 0;
while ( !isHeapEmpty() > 0 ) {
while ( !isHeapEmpty() && getMin().dis + addDis > range )
removeMin();
if ( !isHeapEmpty() )
ans += removeMin().cost;
addDis += pas;
}
fout = fopen( "lupu.out", "w" );
fprintf( fout, "%d\n", ans );
fclose( fout );
return 0;
}