Cod sursa(job #769171)

Utilizator ion824Ion Ureche ion824 Data 18 iulie 2012 15:33:04
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.41 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){
     int nod=1;
     while(nod)
      {
       nod=0;
       if(2*k<=hp)
        {
          nod=2*k;
          if(2*k+1<=hp && h[nod]<h[nod+1])++nod;         
          if(h[nod]<=h[k])nod=0;
        }          
       if(nod)
         {
          swap(h[nod],h[k]);
          k=nod;      
         }                        
      }               
}

int main(void){
    ifstream fin("gutui.in");
    ofstream fout("gutui.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];
       t[i]=(X-x)/L;
       if(t[i]>tmax)tmax=t[i];
       I[i]=i;               
      }
    sort(I+1,I+N+1,cmp()); 
    for(j=tmax,i=1;j>=0;--j)
    {
       while(t[I[i]]==j && i<=N){ h[++hp]=ln[I[i]]; upheap(hp); ++i; }       
       if(hp)
         {
          cost+=h[1];
          h[1]=h[hp--];  
          downheap(1);    
         }              
    }
    fout<<cost;             
 return 0;   
}