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