Cod sursa(job #2793299)

Utilizator bog_manBogdan Manghiuc bog_man Data 3 noiembrie 2021 13:58:58
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve(){
    ifstream in("lupu.in");
    ofstream out("lupu.out");
    
    int n, x, l;
    in >> n >> x >> l;
    
    vector<pair<int, int>> sheep(n);
    for (int i = 0; i < n; ++i){
        pair<int, int> p;
        in >> p.first >> p.second;
        sheep[i] = p;
    }
    
    sort(sheep.begin(), sheep.end(), 
        [](const pair<int, int> a, const pair<int, int> b) {
            return a.first < b.first;             
        }
    );
    
    if (0 == l){
        ll ans = 0;
        for (int i = 0; i < n; ++i)
            if (sheep[i].first <= l)
                ans += sheep[i].second;
        out << ans << endl;
        return;
    }
    
    priority_queue<int, vector<int>, greater<int>> ans;
    
    for (int i = n-1; i >= 0; --i){
        int group_num = (x - sheep[i].first) / l + 1;
            ans.push(sheep[i].second);
            while ((int) ans.size() > group_num && ans.size() > 0)
                ans.pop();
    }
    
    ll sol = 0;
    while (!ans.empty()){
        // cout << ans.top() << " ";
        sol += ans.top();
        ans.pop();
    }
    
    out << sol << endl;
    in.close();
    out.close();
}

int main(){
    solve();
    return 0;
}