Pagini recente » Cod sursa (job #2673354) | Cod sursa (job #1370248) | Cod sursa (job #2568696) | Cod sursa (job #2557908) | Cod sursa (job #547961)
Cod sursa(job #547961)
#include<fstream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MaxN = 100005;
const char in[] = "lupu.in";
const char out[] = "lupu.out";
struct oaie{
int dist,lana;
}z[MaxN];
int nh,h[MaxN];
long long rez;
pair<int,int> v[MaxN];
ifstream f(in);
ofstream g(out);
inline void swap(int i,int j)
{
int aux = h[i];
h[i] = h[j];
h[j] = aux;
}
void upHeap(int i)
{
if( h[i] > h[i>>1] && i>>1 )
{
swap(i,i>>1);
upHeap(i>>1);
}
}
void downHeap(int i)
{
int m = i;
if( i<<1 <= nh && h[m] < h[i<<1] )
m = i<<1;
if( i<<1+1 <= nh && h[m] < h[i<<1+1] )
m = i<<1+1;
if( m != i)
{
swap(i,m);
downHeap(m);
}
}
int main()
{
int n,x,l,i,tmax;
f >> n >> x >> l;
for( i = 1 ; i <= n ; i++ )
{
f >> z[i].dist >> z[i].lana;
v[i].first = (x-z[i].dist)/l;
v[i].second = i;
}
sort(v+1,v+n+1);
tmax = v[n].first;
nh = 0;
for( i = n ; i && tmax >= 0 ; )
{
while( tmax == v[i].first && i )
{
h[++nh] = z[v[i].second].lana;
upHeap(nh);
i--;
}
if( nh )
{
rez +=(long long)h[1];
h[1] = h[nh];
nh--;
downHeap(1);
}
--tmax;
}
g << rez << '\n';
f.close();
g.close();
return 0;
}