Cod sursa(job #1845155)

Utilizator cameleonGeorgescu Dan cameleon Data 10 ianuarie 2017 23:04:28
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <algorithm>
#include<queue>

using namespace std;

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


priority_queue <int> heap;

bool cmp(oita a,oita b) {
    return (a.strat>b.strat);
}

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(l>=distanta){
            nr++;
            oaie[nr].lana=lana;
            oaie[nr].strat = (l-distanta)/k;
        }
    }
    n=nr;
    sort(oaie+1,oaie+n+1,cmp);
    heap.push(oaie[1].lana);
    for (i=2;i<=n;i++) {
        if (oaie[i].strat == oaie[i-1].strat)
            heap.push(oaie[i].lana);
        else {
            int x = oaie[i-1].strat - oaie[i].strat;
            for (int j=1;j<=x;j++) {
                if (heap.empty()) break;
                lana=heap.top();
                totalLana += lana;
                heap.pop();
            }
            heap.push(oaie[i].lana);
        }
    }
    if (oaie[n].strat == 0 && !heap.empty()) {
            lana=heap.top();
            totalLana += lana;
    }
    printf("%lld\n",totalLana);
    return 0;
}