Pagini recente » Cod sursa (job #879268) | Cod sursa (job #2504302) | Cod sursa (job #263799) | Cod sursa (job #2099251) | Cod sursa (job #3143480)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define NMAX 100000
using namespace std;
struct str {
int pasi, val;
} v[NMAX], heap[NMAX];
int nexxt[NMAX];
int heapsize, pas;
bool cmp( str a, str b ) {
if( a.pasi != b.pasi )
return a.pasi < b.pasi;
return a.val < b.val;
}
inline int parent(int i) { return (i - 1) / 2; }
inline int leftChild(int i) { return i * 2 + 1; }
inline int rightChild(int i) { return i * 2 + 2; }
void first_del();
void upHeap(int i) {
while (i && heap[parent(i)].val < heap[i].val) {
swap(heap[parent(i)], heap[i]);
i = parent(i);
}
}
void downHeap(int i) {
int left, right, biggest;
biggest = i;
left = leftChild(i), right = rightChild(i);
if (left < heapsize && heap[left].val > heap[biggest].val)
biggest = left;
if (right < heapsize && heap[right].val > heap[biggest].val)
biggest = right;
if (i != biggest) {
swap(heap[i], heap[biggest]);
downHeap(biggest);
}
}
void extractMax() {
swap( heap[0], heap[--heapsize] );
downHeap( 0 );
}
void heap_insert( str oaie ) {
heap[heapsize++] = oaie;
upHeap( heapsize - 1 );
}
void update(int i, int value) {
heap[i].val = value;
upHeap(i);
downHeap(i);
}
int getMax() {
return heap[0].val;
}
void heap_delete(int i) {
update(i, getMax());
extractMax();
}
void first_del() {
while( heapsize && heap[0].pasi < pas )
heap_delete( 0 );
}
int main() {
FILE *fin, *fout;
int n, x, l, i, d, a, pas_max, st, finn, j;
long long sum;
fin = fopen( "lupu.in", "r" );
fout = fopen( "lupu.out", "w" );
fscanf( fin, "%d%d%d", &n, &x, &l );
pas_max = 0;
sum = 0;
for( i = 0; i < n; i++ ) {
fscanf( fin, "%d%d", &d, &a );
v[i].pasi = ( x - d + l ) / l;
v[i].val = a;
if( v[i].pasi > pas_max )
pas_max = v[i].pasi;
}
sort( v, v + n, cmp );
i = n - 1;
for( pas = pas_max; pas > 0; pas-- ) {
while( i >= 0 && v[i].pasi >= pas ) {
heap_insert( v[i] );
i--;
}
sum += getMax();
extractMax();
}
fprintf( fout, "%lld", sum );
fclose( fin );
fclose( fout );
return 0;
}