Cod sursa(job #3370671)

Utilizator MateiDiaconuDiaconu Matei Stefan MateiDiaconu Data 26 octombrie 2026 18:32:58
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 100000

const int INF = (1LL << 31) - 1;

struct Oaie{
    int priority, lana;
};

Oaie oi[MAXN];

int heap[MAXN];
int heap_size;

inline int parent(int i){
    return (i - 1) / 2;
}
inline int leftChild(int i){
    return i * 2 + 1;
}
inline int rightChild(int i){
    return i * 2 + 2;
}

void upHeap(int i){
    while(i && heap[i] > heap[parent(i)]){
        swap(heap[i], heap[parent(i)]);
        i = parent(i);
    }
}

void downHeap(int i){
    int biggest, left, right;

    left = leftChild(i);
    right = rightChild(i);
    biggest = i;

    if(left < heap_size && heap[left] > heap[biggest]){
        biggest = left;
    }
    if(right < heap_size && heap[right] > heap[biggest]){
        biggest = right;
    }

    if(biggest != i){
        swap(heap[i], heap[biggest]);
        downHeap(biggest);
    }
}

void insert(int val){
    heap[heap_size++] = val;
    upHeap(heap_size - 1);
}

int extractMax(){
    int max_value;

    max_value = heap[0];

    heap[0] = heap[--heap_size];
    downHeap(0);

    return max_value;
}

bool cmpByPriority(Oaie& a, Oaie& b){
    if(a.priority == b.priority){
        return a.lana > b.lana;
    }
    return a.priority > b.priority;
}

int main(){
    FILE *fin, *fout;
    fin = fopen("lupu.in", "r");
    fout = fopen("lupu.out", "w");

    int n, x, l, d, i, t, j;
    long long s, prev;

    fscanf(fin, "%d%d%d", &n, &x, &l);

    for(i = 0; i < n; i++){
        fscanf(fin, "%d%d", &d, &oi[i].lana);

        if(d > x){
            oi[i].priority = -1;
        }
        else if(l == 0){
            oi[i].priority = INF;
        }
        else{
            oi[i].priority = (x - d) / l;
        }

    }

    sort(oi, oi + n, cmpByPriority);

    s = 0;
    prev = oi[0].priority;
    i = 0;
    while(i < n && oi[i].priority >= 0){
        t = oi[i].priority;

        j = 0;
        while(j < prev - t && heap_size){
            s += extractMax();
            j++;
        }

        while(i < n && oi[i].priority == t){
            insert(oi[i].lana);
            i++;
        }
        prev = t;
    }

    j = 0;
    while(j <= prev && heap_size){
        s += extractMax();
        j++;
    }

    fprintf(fout, "%lld", s);

    fclose(fin);
    fclose(fout);
    return 0;
}