Pagini recente » Cod sursa (job #1882260) | Cod sursa (job #2916038) | Cod sursa (job #1344919) | Cod sursa (job #1610560) | Cod sursa (job #2634642)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin( "lupu.in" );
ofstream fout( "lupu.out" );
const int MaxN = 100001;
int d[MaxN], l[MaxN], ind[MaxN];
long long t[MaxN], heap[MaxN];
int indH;
static inline int fth( int node ) {
return (node >> 1);
}
static inline int lSon( int node ) {
return (node << 1);
}
static inline int rSon( int node ) {
return ((node << 1) + 1);
}
void swap( int a, int b ) {
long long aux;
aux = heap[a];
heap[a] = heap[b];
heap[b] = aux;
}
void repairUpp( int node ) {
while ( node > 1 && heap[node] > heap[fth( node )] ) {
swap( node, fth( node ) );
node = fth( node );
}
}
void repairDown( int node ) {
int son;
while ( node < indH ) {
if ( lSon( node ) <= indH && rSon( node ) <= indH ) {
if ( heap[lSon( node )] > heap[rSon( node )] ) {
son = lSon( node );
} else {
son = rSon( node );
}
} else if ( lSon( node ) > indH && rSon( node ) <= indH ) {
son = rSon( node );
} else if ( rSon( node ) > indH && lSon( node ) <= indH ) {
son = lSon( node );
} else {
son = indH + 1;
}
if ( son <= indH && heap[son] > heap[node] ) {
if ( son <= indH ) {
swap( son, node );
node = son;
} else {
node = indH + 1;
}
} else {
node = indH + 1;
}
}
}
void add( long long value ) {
++indH;
heap[indH] = value;
repairUpp( indH );
}
void cutMax() {
swap( indH, 1 );
--indH;
repairUpp( 1 );
repairDown( 1 );
}
int cmp( int a, int b ) {
return t[a] > t[b];
}
int main() {
int n, range, dist, i;
long long maxl;
fin >> n >> range >> dist;
for ( i = 0; i < n; ++i ) {
fin >> d[i] >> l[i];
t[i] = (range - d[i]) / dist + 1;
ind[i] = i;
}
sort( ind, ind + n, cmp );
maxl = 0;
add( l[ind[0]] );
for ( i = 1; i < n; ++i ) {
if ( t[ind[i]] < t[ind[i - 1]] ) {
maxl += (t[ind[i - 1]] - t[ind[i]]) * heap[1];
cutMax();
}
add( l[ind[i]] );
}
maxl += heap[1];
fout << maxl;
fin.close();
fout.close();
return 0;
}