Cod sursa(job #195576)

Utilizator alexeiIacob Radu alexei Data 19 iunie 2008 19:37:18
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#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;
}