Cod sursa(job #3298863)

Utilizator mateistefan11matei stefan mateistefan11 Data 2 iunie 2025 19:06:40
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.28 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
template<typename T>
class priorityQueue
{
private:
    vector<T> a;

    static inline int parent(int p)
    {
        return (p - 1) / 2;
    }

    static inline int leftChild(int p)
    {
        return (2 * p + 1);
    }

    static inline int rightChild(int p)
    {
        return (2 * p + 2);
    }

    void shiftUp(int p)
    {
        while(p > 0)
        {
            int t = parent(p);
            if(a[p] <= a[t]) return;
            swap(a[p], a[t]);
            p = t;
        }
    }
    void shiftDown(int p)
    {
        int n = a.size();
        while (p < n / 2)
        {
            int maxim = p;
            int left = leftChild(p);
            int right = rightChild(p);
            if(left < n && a[maxim] < a[left])
                maxim = left;
            if(right < n && a[maxim] < a[right])
                maxim = right;
            if(maxim == p) return;
            swap(a[maxim], a[p]);
            p = maxim;
        }
    }
public:

    priorityQueue() = default;
    ~priorityQueue() = default;

    bool Empty(){ return a.empty(); }
    int Size(){ return a.size(); }

    void Push(const T& val)
    {
        a.push_back(val);
        shiftUp(a.size() - 1);
    }

    void Pop()
    {
        if(Empty()) return;
        a[0] = a.back();
        a.pop_back();
        if(!a.empty()) shiftDown(0);
    }

    const T& Top()
    {
        if(!Empty()) return a[0];
    }

    void ChangePriority(const T& oldVal, const T& newVal)
    {
        int poz = -1;
        for(int i = 0; i < a.size(); i++)
            if(a[i] == oldVal)
            {
                poz = i;
                break;
            }
        if(poz == -1) return;
        a[poz] = newVal;
        if(a[poz] > oldVal) shiftDown(poz);
        else shiftUp(poz);
    }
};

/// arme1 - pbinfo
void prob1()
{
    int n,m, i, x;
    priorityQueue<long long> q;
    long long s = 0;
    cin >> n >> m;
    for(i = 1; i <= n; i++)
    {
        cin >> x;
        q.Push(x);
    }
    for(i = 1; i <= m; i++)
    {
        cin >> x;
        q.Push(x);
    }

    while(n != 0)
    {
        s += q.Top();
        q.Pop();
        n--;
    }
    cout << s;
}


/// Lupul urias si rau - infoarena
bool comp(pair<int, int> a, pair<int, int> b)
{
    return a.first < b.first;
}
void prob2()
{
    int n = 0, x = 0, l = 0, i, dist = 0;
    unsigned long long ans = 0;
    vector<pair<int, int> > o;
    priorityQueue<int> q;

    fin >> n >> x >> l;
    for(i = 1; i <= n; ++i)
    {
        int d, lana;
        fin >> d >> lana;
        o.push_back({d, lana});
    }
    sort(o.begin(), o.end(), comp);
    for(i = 0; i < n; ++i)
    {
        if(dist >= o[i].first) q.Push(o[i].second);
        else
        {
            if(!q.Empty())
            {
                ans += q.Top();
                q.Pop();
            }
            dist += l;
            --i;
            if(dist > x) break;
        }
    }

    while(!q.Empty() && dist <= x)
    {
        ans += q.Top();
        q.Pop();
        dist += l;
    }

    fout << ans;
}
int main()
{
    prob2();
    return 0;
}