Cod sursa(job #1847305)

Utilizator cameleonGeorgescu Dan cameleon Data 14 ianuarie 2017 15:14:11
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 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;
    oaie[++n].strat=-1;

    sort(oaie+1,oaie+n+1,cmp);
    heap[++nh]=oaie[1].lana;
    for (i=2;i<=n;i++) {
        if (oaie[i].strat != oaie[i-1].strat)
        {
            int x = oaie[i-1].strat - oaie[i].strat;
            for (int j=1;j<=x;j++) {
                if (nh>0){
                    totalLana += heap[1];
                    heap[1]=heap[nh--];
                    if(nh>0)
                    down(1);
                }
            }
        }
        heap[++nh]=oaie[i].lana;
        up(nh);
    }

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