Cod sursa(job #1839802)

Utilizator giotoPopescu Ioan gioto Data 3 ianuarie 2017 14:35:27
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int NR, Tmax, n, x, l, d, a[100005], T[100005], pos[100005], Heap[100005];
inline bool cmp(int x, int y){
    return T[x] < T[y];
}
inline void push(int x){
    while(x / 2 && a[Heap[x]] > a[Heap[x / 2]]){
        int aux = Heap[x];
        Heap[x] = Heap[x / 2];
        Heap[x / 2] = aux;
    }
}
inline void pop(int x){
    int y = 0;
    while(x != y){
        y = x;
        if(y * 2 <= NR && a[Heap[x]] < a[Heap[y * 2]]) x = y * 2;
        if(y * 2 + 1 <= NR && a[Heap[x]] < a[Heap[y * 2 + 1]]) x = y * 2;
        int aux = Heap[x];
        Heap[x] = Heap[y];
        Heap[y] = aux;
    }
}
int main()
{
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    scanf("%d%d%d", &n, &x, &l);
    for(int i = 1; i <= n ; ++i){
        scanf("%d%d", &d, &a[i]);
        if(d > x)
            T[i] = 0;
        else
            T[i] = 1 + (x - d) / l;
        if(T[i] > Tmax)
            Tmax = T[i];
        pos[i] = i;
    }
    sort(pos + 1, pos + n + 1, cmp);
    int L = n, Sol = 0;
    for(int j = Tmax; j >= 1 ; --j){
        if(T[pos[L]] == j){
            for(L; T[pos[L]] == j ; --L){
                ++NR;
                Heap[NR] = pos[L];
                push(NR);
            }
        }
        if(NR == 0) continue;
        Sol += a[Heap[1]];
        Heap[1] = Heap[NR--];
        pop(1);
    }
    printf("%d", Sol);
    return 0;
}