Cod sursa(job #1403655)

Utilizator azkabancont-vechi azkaban Data 27 martie 2015 14:48:13
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<bits/stdc++.h>
using namespace std;
const int Max=100005;
int g[Max],t[Max],ind[Max];
int h[Max],hp,hc;
int n,l,H,i,j;
int tmax(0),x;
long long cost(0); 

bool cmp(const int &i,const int &j)
 {
  return t[i]>t[j];
 }       
 
void upheap(int nod)
 {
 int tata=nod/2;
 if (!tata) return ;
 if (tata>=1 && h[nod]>h[tata])
     {
      swap(h[nod],h[nod/2]);
      upheap(tata);
     }              
}

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

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

void add_Heap(int value)
{
 h[++hp]=value;
 return ;
}
 
int main(void)
 {
 ifstream cin("lupu.in");
ofstream cout("lupu.out");
 cin>>n>>H>>l;
 
  for(i=1;i<=n;++i)
      {
       cin>>hc>>g[i];
	   ind[i]=i; 
       t[i]=(H-hc)/l;
       tmax=max(tmax,t[i]);          
      }
    
    sort(ind+1,ind+n+1,cmp); 
    
    i=1;
    for(j=tmax;j>=0;--j)
    {
     while(t[ind[i]]==j && i<=n)
	     { 
		 add_Heap(g[ind[i]]);
		 upheap(hp); 
		 ++i; 
		 }       
     if(hp)
        {
         cost+=h[1];
         sterge();
        }              
    }
    cout<<cost;            
 return 0;   
}