Cod sursa(job #3166981)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 9 noiembrie 2023 20:57:02
Problema Lupul Urias si Rau Scor 92
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>

using namespace std;

struct sheep
{
    long long dist, cost;
};

class comp
{
public:
    bool operator ()(const sheep &a, const sheep &b)
    {
        if(a.cost == b.cost)
            return a.dist < b.dist;
        return a.cost < b.cost;
    }
};

long long n, x, l;
vector <sheep> sheeps;
priority_queue <sheep, vector <sheep>, comp> pq;

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);

    cin >> n >> x >> l;

    for(int i = 1; i <= n; i ++)
    {
        long long d, a;
        cin >> d >> a;
//        if(d <= x)
        sheeps.push_back({(x - d) / l + 1, a});
//        cout << (x - d) / l + 1 << " " << a << "\n";
    }

    sort(sheeps.begin(), sheeps.end(), [](const sheep &a, const sheep &b)
    {
        if(a.dist == b.dist)
            return a.cost < b.cost;
        return a.dist > b.dist;
    });

    sheeps.push_back({0, 0});

    long long ans = 0;

//    cout << "\n";
    int i = 0;
    while(i < sheeps.size() - 1)
    {
        int stages;
        pq.push(sheeps[i]);
        while(i < sheeps.size()  &&  sheeps[i].dist == sheeps[i + 1].dist)
        {
            pq.push(sheeps[i + 1]);
            i ++;
        }

        stages = sheeps[i].dist - sheeps[i + 1].dist;
//        cout << sheeps[i].dist << " " << sheeps[i + 1].dist << " " << stages << "\n";
        while(!pq.empty()  &&  stages)
        {
            ans += pq.top().cost;
//            cout << pq.top().dist << " " << pq.top().cost << "\n";
            pq.pop();
            stages --;
        }
        i ++;
    }

    cout << ans;
    return 0;
}