Cod sursa(job #194837)

Utilizator alexeiIacob Radu alexei Data 14 iunie 2008 19:06:21
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<stdio.h>
#include<algorithm>
#define nmax 100024
using namespace std;

typedef struct{
        int cost,timp;
        }q;
q v[nmax];

inline int cmp(q A,q B) {
    return A.timp<B.timp;
}

int h[nmax];
int sf;
int N,X,L;

void change(int a,int b)
{
     h[a]^=h[b];
     h[b]^=h[a];
     h[a]^=h[b];
}

void upp(int poz)
{
 if( poz>1 ){
 
 int new_poz=poz>>1;

     if( h[new_poz]<h[poz] ){     
     change(poz,new_poz);
     upp(new_poz);
     }
     
     }
}

void down(int poz)
{
     
int left=poz<<1;
int right=left+1;
int 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);
 
 int i,n=0;
 int solfin=0;
 int aux1,aux2;
 
 scanf("%d%d%d",&N,&X,&L);
 
 for(i=1; i<=N; ++i){
 scanf("%d%d",&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);

 int poz=N,next;
 int Tmax=v[N].timp;   
 //show_1();
 
 for(i=Tmax; i>=0; --i){
   
   next=1;
   
   if( v[poz].timp<i ){
   next+=i-v[poz].timp;
   i=v[poz].timp;
   }  
   //formez heap;
   //sf=0;
   
   while( v[poz].timp==i )
   {
       h[++sf]=v[poz].cost;
       upp(sf);
       --poz;
   }
   //extrag sol
   
   while( next )
   {
          --next;
          solfin+=h[1];
          change(1,sf);
          --sf;
          down(1);
   }//*/
 
 }  
 
 printf("%d\n",solfin); 
 
 return 0;
}