Cod sursa(job #1257506)

Utilizator ion824Ion Ureche ion824 Data 7 noiembrie 2014 20:35:15
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.53 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("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];
      	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 << '\n';    
	         
 return 0;   
}