Pagini recente » Cod sursa (job #503048) | Cod sursa (job #931164) | Cod sursa (job #2367528) | Cod sursa (job #2053691) | Cod sursa (job #195576)
Cod sursa(job #195576)
#include<stdio.h>
#include<algorithm>
#define nmax 100024
using namespace std;
typedef struct{
long long cost,timp;
}q;
q v[nmax];
inline int cmp(q A,q B) {
return A.timp<B.timp;
}
long long h[nmax];
long long sf;
long long N,X,L;
void change(const long long a,const long long b)
{
long long aux=h[a];
h[a]=h[b];
h[b]=aux;
}
void upp(long long poz)
{
if( poz>1 ){
long long new_poz=poz>>1;
if( h[new_poz]<h[poz] ){
change(poz,new_poz);
upp(new_poz);
}
}
}
void down(long long poz)
{
long long left=poz<<1;
long long right=left+1;
long long ctrl=poz;
if( left <= sf )
if( h[left]>h[ctrl] )
ctrl=left;
if( right <= sf)
if( h[right]>h[ctrl] )
ctrl=right;
if( ctrl!=poz )
{
change(ctrl,poz);
down(ctrl);
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
long long i,n=0;
long long solfin=0;
long long aux1,aux2;
scanf("%lld%lld%lld",&N,&X,&L);
for(i=1; i<=N; ++i){
scanf("%lld%lld",&aux1,&aux2);
if( aux1<=X ){
++n;
aux1=(X-aux1)/L;
if( !aux1 )
aux1=1;
v[n].timp=aux1;
v[n].cost=aux2;
}
}
N=n;
sort(v+1,v+N+1,cmp);
long long poz=N,next;
long long Tmax=v[N].timp;
for(i=Tmax; i>=0; --i){
next=1;
if( v[poz].timp<i ){
next+=i-v[poz].timp;
i=v[poz].timp;
}
while( v[poz].timp==i && poz )
{
h[++sf]=v[poz].cost;
upp(sf);
--poz;
}
while( next && sf )
{
--next;
solfin+=h[1];
change(1,sf);
--sf;
down(1);
}
}
printf("%lld\n",solfin);
return 0;
}