Pagini recente » Monitorul de evaluare | Cod sursa (job #967913)
Cod sursa(job #967913)
#include <fstream>
#include <array>
#include <vector>
#include <functional>
#include <cstdlib>
#include <algorithm>
using namespace std;
template< class type, class comp >
inline void swim( vector< type >& heap, unsigned k, comp compare )
{
while ( k > 1 && !compare( heap[ k / 2 ], heap[ k ] ) )
{
std::swap( heap[ k / 2 ], heap[ k ] );
k /= 2;
}
}
template< class type, class comp >
void sink( vector< type >& heap, unsigned k, comp compare )
{
const unsigned n = heap.size();
while ( 2 * k < n )
{
unsigned j = 2 * k;
if ( j + 1 < n && compare( heap[ j + 1 ], heap[ j ] ) )
j++;
if ( compare( heap[ k ], heap[ j ] ) )
break;
else
std::swap( heap[ k ], heap[ j ] );
k = j;
}
}
template< class type, class comp >
inline void insert( vector< type >& heap, type v, comp compare )
{
heap.push_back( v );
swim( heap, heap.size() - 1, compare );
}
template< class type, class comp >
inline type del( vector< type >& heap, comp compare )
{
type ceva = heap[ 1 ];
std::swap( heap[ 1 ], heap.back() );
heap.pop_back();
sink( heap, 1, compare );
return ceva;
}
int main()
{
ifstream in("lupu.in");
ofstream out("lupu.out");
int n = 0, x = 0, l = 0;
in >> n >> x >> l;
array< int, 100000 > dist;
array< int, 100000 > lana;
for ( unsigned i = 0; i < n; i++ )
{
in >> dist[ i ];
dist[ i ] = ( x - dist[ i ] ) / l;
in >> lana[ i ];
}
in.close();
srand( n );
quick3s( dist, lana, 0, n );
vector< int > heap;
heap.push_back( 0 );
vector< int > end;
end.push_back( 0 );
int index = 0;
while ( dist[ index ] < 0 )
index++;
long long s = 0;
for ( int i = n - 1; i >= index; i-- )
{
while ( i > index && dist[ i - 1 ] == dist[ i ] )
insert( heap, lana[ i-- ], std::greater< int >() );
insert( heap, lana[ i ], std::greater< int >() );
s += del( heap, std::greater< int >() );
}
out << s;
out.close();
return 0;
}