Cod sursa(job #3347227)

Utilizator unomMirel Costel unom Data 15 martie 2026 20:00:35
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");
int n, x, l;
pair<int, int> v[100005];
vector<int> pos;
vector<int> col[100005];

int main()
{
    in>>n>>x>>l;

    int d, a;
    for(int i = 1; i<=n; i++)
    {
        in>>d>>a;
        v[i] = {d, a};

        if(x - d >= 0)
        {
            int nr = (x - d) / l;

            pos.push_back(nr);
        }
    }

    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());

    for(int i = 1; i<=n; i++)
    {
        d = v[i].first;
        a = v[i].second;

        if(x - d >= 0)
        {
            int nr = (x - d) / l;
            nr = lower_bound(pos.begin(), pos.end(), nr) - pos.begin();

            col[nr].push_back(a);
        }
    }

    for(int i = 0; i<n; i++)
    {
        sort(col[i].begin(), col[i].end());
    }

    long long ans = 0;
    priority_queue<pair<int, int>> pq;
    for(int i = pos.size() - 1; i>=0; i--)
    {
        pq.push({col[i][col[i].size() - 1], i});
        col[i].pop_back();

        int nxt = 0;
        if(i > 0)
        {
            nxt = pos[i - 1] + 1;
        }

        for(int j = pos[i]; j>=nxt; j--)
        {
            if(pq.empty())
            {
                break;
            }

            pair<int, int> cur = pq.top();
            pq.pop();

            ans += cur.first;
            if(col[cur.second].size() >= 1)
            {
                pq.push({col[cur.second][col[cur.second].size() - 1], cur.second});
                col[cur.second].pop_back();
            }
        }
    }

    out<<ans;

    return 0;
}