Cod sursa(job #1259121)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 9 noiembrie 2014 18:53:12
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 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 nr,i,j,n,X,L;
long long sol=0;


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

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