Cod sursa(job #769165)

Utilizator ion824Ion Ureche ion824 Data 18 iulie 2012 15:17:44
Problema Lupul Urias si Rau Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<fstream>
#include<algorithm>
using namespace std;
const int NM = 100005;
int ln[NM],t[NM],I[NM];
int h[NM],hp;

inline void swap(int &a,int &b){ int k=a; a=b; b=k; }

struct cmp{
  bool operator()(const int &i,const int &j){
       return t[i]>t[j];
       }       
};

void upheap(int k){
    while(k>1 && h[k]>h[k/2])
     {
      swap(h[k],h[k/2]);
      k/=2;
     }              
}

void downheap(int k){
     if(h[2*k]>h[k] && h[2*k]>h[2*k+1]){
                    swap(h[k],h[2*k]);
                    if(2*k<hp)downheap(2*k);
                    }
     else if(h[2*k+1]>h[k] && h[2*k+1]>=h[2*k]){
                    swap(h[k],h[2*k+1]);
                    if(2*k+1<hp)downheap(2*k+1);
                    }                                               
}

void insert(int k){
      h[++hp]=k; upheap(hp);
}

void del(){
      h[1]=h[hp]; h[hp]=-1; --hp; downheap(1);
}

int main(void){
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");
    int N,L,X,i,j,tmax=0,x; long long cost=0;
    fin>>N>>X>>L;
    for(i=1;i<=N;++i)
      {
       fin>>x>>ln[i]; h[i]=-1;
       t[i]=(X-x)/2;
       if(t[i]>tmax)tmax=t[i];
       I[i]=i;               
      }
    sort(I+1,I+N+1,cmp()); h[0]=-1;
    for(j=tmax,i=1;j>=0;--j)
    {
       while(t[I[i]]==j && i<=N){ insert(ln[I[i]]); ++i; }       
       if(hp>0)
         {
          cost+=h[1];
          del();    
         }              
    }
    fout<<cost;             
 return 0;   
}