Pagini recente » Cod sursa (job #1451194) | Cod sursa (job #2454194) | Cod sursa (job #1403305) | Cod sursa (job #1849926) | Cod sursa (job #2809652)
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define MAXELEM 2147483647
struct oaieee{
int dist, lana;
};
oaieee v[MAXN+2];
int heap[MAXN+2];
int heapSize = 1;
bool cmp( oaieee a, oaieee b ) {
return a.dist < b.dist;
}
void downheap( int poz ) {
while( 2 * poz <= heapSize && heap[poz] < max( heap[2*poz], heap[2*poz+1] ) ) {
if( heap[2*poz] > heap[2*poz+1] ) {
swap( heap[poz], heap[2*poz] );
poz = 2 * poz;
}
else {
swap( heap[poz], heap[2*poz+1] );
poz = 2 * poz + 1;
}
}
}
void upheap( int poz ) {
while( poz > 0 && heap[poz] > heap[poz/2] ) {
swap( heap[poz], heap[poz/2] );
poz = poz / 2;
}
}
void Insert( int val ) {
heap[heapSize++] = val;
upheap(heapSize-1);
}
void extractMax() {
heap[1] = heap[heapSize-1];
heapSize--;
downheap(1);
}
int main() {
FILE *fin, *fout;
int x, l, i, poz, n;
long long s;
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 );
heap[0] = MAXELEM;
sort( v, v + n, cmp );
i = 0;
poz = x % l;
s = 0;
while( i < n && poz <= x ) {
while( i < n && v[i].dist <= poz ) {
Insert( v[i].lana );
i++;
}
if( heapSize > 1 ) {
s += heap[1];
extractMax();
}
poz += l;
}
fout = fopen( "lupu.out", "w" );
fprintf( fout, "%lld", s );
fclose( fout );
return 0;
}