Cod sursa(job #1259216)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 9 noiembrie 2014 20:29:40
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fi("lupu.in");
ofstream fo("lupu.out");

class Max_Heap{
      private:
              int h[100005];
              int heapsize;
              void coboara(int k);
              void urca(int k);
      public:
             Max_Heap();
             void adauga(int k);
             void sterge(int k);
             int maxim();
             int heap_size();
};

void Max_Heap::coboara(int k){
     bool ok=1;
     int nod;

     while(ok)
     {
      ok=0;
      
      if(2*k<=heapsize){
                        nod=2*k;
                        
                        if(2*k+1<=heapsize && h[2*k+1]>h[nod]) nod=2*k+1;
                        
                        if(h[nod]>h[k]){
                                        ok=1;
                                        swap(h[nod],h[k]);
                                        k=nod;
                                       }
                       }
     }
}

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

Max_Heap::Max_Heap(){
     heapsize=0;
}

void Max_Heap::adauga(int x){
     h[++heapsize]=x;
     urca(heapsize);
}

void Max_Heap::sterge(int k){
     h[k]=h[heapsize--];
     urca(k);
     coboara(k);
}

int Max_Heap::maxim(){
    return h[1];
}

int Max_Heap::heap_size(){
    return heapsize;
}

struct oaie{
       int dist;
       int profit;
       int timp;
};

const int MAX_N = 100005;
Max_Heap h;
oaie a[MAX_N];
int timp,tmax,i,j,n,nr,X,L;
long long sol=0;

bool comp(const oaie &A, const oaie &B){
     return (A.timp>B.timp);
}

int main(){
    fi>>n>>X>>L;
    for(i=1;i<=n;i++){
                      int distanta;
                      int profitul;
                      fi>>distanta>>profitul;
                      if(distanta<=X){
                                      ++nr;
                                      a[nr].dist=distanta;
                                      a[nr].profit=profitul;
                                      a[nr].timp=(X-a[nr].dist)/L;
                                     }
                     }
    
    sort(a+1,a+nr+1,comp);
    
    tmax=a[1].timp;
    
    for(timp=tmax,j=1; timp>=0; --timp)
       {    
        for(; j<=nr && timp==a[j].timp; ++j) h.adauga(a[j].profit);
        
        if(h.heap_size()){
                          sol+=1LL*h.maxim(); 
                          h.sterge(1);     
                         }          
       }
    
    fo<<sol;
    
    fi.close();
    fo.close();
    return 0;
}