Pagini recente » Cod sursa (job #3220330) | Cod sursa (job #1155729) | Cod sursa (job #1352518) | Cod sursa (job #2331873) | Cod sursa (job #2809414)
// Mihai Priboi
#include <stdio.h>
#include <iostream>
#include <algorithm>
// heap
#define MAXN 100000
inline int parent( int ind ) { return (ind - 1) / 2; }
inline int left_child( int ind ) { return ind * 2 + 1; }
inline int right_child( int ind ) { return ind * 2 + 2; }
int heap[MAXN];
int heap_size;
void upHeap( int nod ) {
if( nod > 0 && heap[nod] > heap[parent(nod)] ) {
std::swap( heap[nod], heap[parent(nod)] );
upHeap( parent(nod) );
}
}
void downHeap( int nod ) {
int nod_min;
nod_min = left_child(nod);
if( right_child(nod) < heap_size && heap[right_child(nod)] > heap[nod_min] )
nod_min = right_child(nod);
if( nod_min < heap_size && heap[nod] < heap[nod_min] ) {
std::swap( heap[nod], heap[nod_min] );
downHeap( nod_min );
}
}
void insertVal( int x ) {
heap[heap_size] = x;
upHeap( heap_size++ );
}
int deleteMin() {
int rez;
rez = heap[0];
std::swap( heap[0], heap[--heap_size] );
downHeap(0);
return rez;
}
struct oaie {
int dist, lana;
};
bool cmp( const oaie &a, const oaie &b ) {
return a.dist < b.dist;
}
oaie v[MAXN];
int main() {
FILE *fin, *fout;
int n, i, x, l, ind;
long long sum;
fin = fopen( "lupu.in", "r" );
fscanf( fin, "%d%d%d", &n, &x, &l );
for( i = 0; i < n; i++ )
fscanf( fin, "%d%d", &v[i].dist, &v[i].lana );
fclose( fin );
std::sort( v, v + n, cmp );
ind = sum = 0;
for( i = 0; i <= x; i += l ) {
while( ind < n && v[ind].dist <= i )
insertVal( v[ind++].lana );
if( heap_size > 0 )
sum += deleteMin();
}
fout = fopen( "lupu.out", "w" );
fprintf( fout, "%lld", sum );
fclose( fout );
return 0;
}