Cod sursa(job #194833)

Utilizator alexeiIacob Radu alexei Data 14 iunie 2008 18:34:20
Problema Lupul Urias si Rau Scor 0
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+1;

if( left <= sf ){
 if( h[left]>h[poz] )
 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;
 int solfin=0;
 int aux1,aux2;
 
 scanf("%d%d%d",&N,&X,&L);
 
 n=0;
 
 for(i=1; i<=N; ++i){
 scanf("%d%d",&aux1,&aux2);
 if( aux1<=X ){
 ++n;
 aux1=(X-aux1)/L;
 v[n].timp=aux1;
 v[n].cost=aux2;
 }
 }
 N=n;

 sort(v+1,v+N+1,cmp);

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