Cod sursa(job #1847322)

Utilizator cameleonGeorgescu Dan cameleon Data 14 ianuarie 2017 15:29:13
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <algorithm>
#include<queue>

using namespace std;

struct oita {
    int lana,strat;
};
oita oaie[100005];
int nh, n,i,k,l,distanta,lana,nr;
long long totalLana;


int heap[100005];

bool cmp(oita a,oita b) {
    return (a.strat>b.strat);
}
void up(int k){
    while(k/2>0 && heap[k/2]<heap[k]){
        swap(heap[k],heap[k/2]);
        k=k/2;
    }
}
void down(int k){
    int pfiu;
    while(2*k<=nh){
        pfiu=-1;
        if(heap[k]<heap[2*k])
            pfiu=2*k;
        if(2*k+1<=nh && heap[k]<heap[2*k+1] && heap[2*k+1]>heap[pfiu])
            pfiu=2*k+1;
        if(pfiu!=-1){
            swap(heap[k],heap[pfiu]);
            k=pfiu;
        }
        else
            return;
    }
}
int main() {
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);

    scanf("%d %d %d",&n,&l,&k);
    for (i=1;i<=n;i++) {
        scanf("%d %d",&distanta,&lana);
        if(distanta<=l){
            nr++;
            oaie[nr].lana=lana;
            oaie[nr].strat = (l-distanta)/k;
        }
    }
    n=nr;
    sort(oaie+1,oaie+n+1,cmp);
   i=1;
   for(int d=l/k;d>=0;d--){//
        //pun oile care apartin stratului d in heap
       while(i<=n && oaie[i].strat==d){
            heap[++nh]=oaie[i].lana;up(nh);
        i++;
       }

       if(nh>0){
        totalLana+=heap[1];
        heap[1]=heap[nh--];
        down(1);
       }
   }

    printf("%lld\n",totalLana);
    return 0;
}