Cod sursa(job #2837775)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 22 ianuarie 2022 15:55:30
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");

const int N = 1e5;

struct sheep
{
    int wool, dist;
};

int n, x, l, maxi;
long long ans;
sheep v[N + 5];
priority_queue<int> pq;

bool comp(sheep a, sheep b)
{
    return a.dist < b.dist;
}

int wave(int ind)
{
    int val, d = x - v[ind].dist;
    if(d < 0)
        val = 0;
    else
        val = d / l + 1;
    return val;
}

int main()
{
    in >> n >> x >> l;
    for(int i = 1; i <= n; i++)
    {
        in >> v[i].dist >> v[i].wool;
        int w = wave(i);
        maxi = max(maxi, w);
    }
    sort(v + 1, v + n + 1, comp);

    //for(int i = 1; i <= n; i++)
    //    cout << v[i].dist << ' ' << v[i].wool << ' ' << wave(i) << '\n';

    int ind = 1;
    for(int w = maxi; w > 0; w--)
    {
        while(ind <= n && wave(ind) == w)
        {
            pq.push(v[ind].wool);
            ind++;
        }
        if(!pq.empty())
        {
            ans += pq.top() * 1LL;
            pq.pop();
        }
    }

    out << ans << '\n';

    return 0;
}