Overview

We consider problems in increasing order of difficulty, adding them to our set of candidates while maintaining the sum of the \(K\) problems with the highest scores among them. The answer is the difficulty at the moment this sum first becomes at least \(P\).

Analysis

Once an upper bound on difficulty is fixed, we should greedily choose problems with the highest scores

Suppose we require the difficulty of all chosen problems to be at most \(x\). Under this condition, to maximize the total score, it is optimal to choose the \(K\) problems with the highest scores among those with difficulty at most \(x\).

Therefore, the maximum difficulty can be at most \(x\) if and only if the following two conditions are met:

• There are at least \(K\) problems with difficulty at most \(x\).
• Among them, the sum of the \(K\) highest scores is at least \(P\).

If the sum is still insufficient even after picking the \(K\) problems with the highest scores, no other choice of problems can satisfy the condition.

Examining problems in increasing order of difficulty

Checking all combinations of \(K\) problems would require examining up to \(\binom{N}{K}\) possibilities, which is too slow and will exceed the time limit.

Therefore, we sort the problems in ascending order of difficulty and add them to our candidates one by one from the beginning. Letting \(b\) be the difficulty of the current problem, all problems added so far have difficulty at most \(b\).

However, re-sorting all candidates by score every time a problem is added is also inefficient. Since we only need the \(K\) problems with the highest scores, we can maintain them using a min-heap.

Maintaining the top \(K\) highest scores with a min-heap

A min-heap is a data structure that allows for fast retrieval and removal of its minimum value.

When we insert a new score and the number of elements exceeds \(K\), we remove the minimum score. This ensures that the heap always contains at most \(K\) problems with the highest scores among all problems processed so far.

For example, when \(K=2\) and scores appear in order of difficulty as \(4, 7, 6\), the maintained scores change as follows:

• Add \(4\): \(\{4\}\)
• Add \(7\): \(\{4,7\}\), sum \(11\)
• Add \(6\) and remove the minimum \(4\): \(\{6,7\}\), sum \(13\)

By updating the sum alongside additions and removals, there is no need to recompute it from scratch each time.

Algorithm

1. Store each problem as a pair \((B_i,A_i)\) and sort them in ascending order of difficulty.
2. Initialize an empty min-heap to manage the scores, along with a variable sum for the sum of its elements.
3. Process the sorted problems one by one from the beginning. Letting \(b\) be the current difficulty and \(a\) be the score, perform the following:
   • Push \(a\) into the heap and add \(a\) to sum.
   • If the size of the heap exceeds \(K\), remove the minimum element and subtract it from sum.
   • If the size of the heap is \(K\) and sum is at least \(P\), output \(b\) and terminate.
4. If the condition is never satisfied after processing all problems, output \(-1\).

Explanation of Correctness

The heap always holds the top \(K\) highest scores among the processed problems.

If there are \(K\) or fewer processed problems, it holds all of them. Once there are more, by adding the new score and then removing the minimum value, the \(K\) highest scores are retained.

Thus, when the heap contains \(K\) elements, sum represents the maximum possible total score that can be obtained by choosing \(K\) problems from those processed so far.

Let \(b\) be the difficulty at the moment the condition is first satisfied. By choosing the \(K\) problems in the heap, we can achieve a total score of at least \(P\) while ensuring all chosen problems have difficulty at most \(b\).

On the other hand, all problems with difficulty strictly less than \(b\) were processed earlier. If the condition could be satisfied using only those problems, the check would have succeeded earlier. Therefore, no value smaller than \(b\) can be the answer, making \(b\) the minimum possible value.

If the condition is never met, even the \(K\) highest scores among all problems are insufficient to reach \(P\), so the answer is \(-1\).

Complexity

• Time complexity: \(O(N\log N)\)
  • Sorting takes \(O(N\log N)\), and all heap operations take \(O(N\log(K+1))\) in total.
• Space complexity: \(O(N)\)
  • Storing the problems takes \(O(N)\) space, and the heap uses \(O(K)\) space.

Implementation Notes

• Use long long for the sum.
  The total score can be up to \(10^5\times10^9=10^{14}\), which exceeds the range of a 32-bit integer. Be sure to read \(P\) as long long as well.

• In C++, priority_queue is a max-heap by default.
  To extract the minimum value, specify greater<int> as follows:

  priority_queue<int, vector<int>, greater<int>> scores;
  

• Check that the number of elements is \(K\), not just the sum.
  Even if the sum is at least \(P\), the condition is not satisfied if fewer than \(K\) problems have been gathered.

• There is no need to process problems with the same difficulty as a batch.
  Even if the condition is satisfied halfway through processing problems of the same difficulty, that difficulty is valid as the answer. If it is not satisfied yet, you can simply continue the checks while adding the remaining problems.

• In the code, problems are stored in the order \((B_i,A_i)\). Since the input order is \(A_i,B_i\), pay attention to the order when reading the input.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    long long P;
    cin >> N >> K >> P;

    vector<pair<int, int>> problems(N);
    for (auto& [b, a] : problems) {
        cin >> a >> b;
    }
    sort(problems.begin(), problems.end());

    priority_queue<int, vector<int>, greater<int>> scores;
    long long sum = 0;

    for (const auto& [b, a] : problems) {
        scores.push(a);
        sum += a;

        if (static_cast<int>(scores.size()) > K) {
            sum -= scores.top();
            scores.pop();
        }

        if (static_cast<int>(scores.size()) == K && sum >= P) {
            cout << b << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return 0;
}

---

This editorial was generated by gpt-6-astra-medium.