Overview

This problem asks us to choose \(K\) problems out of \(N\) such that the total score is at least \(P\), and minimize the maximum difficulty (\(B_i\)) among the chosen problems. We need to efficiently determine how high of a difficulty we must tolerate to achieve a total score of at least \(P\), prioritizing problems with higher scores.

Analysis

Naive Approach and Its Limitations

There are \(\binom{N}{K}\) ways to choose \(K\) problems out of \(N\), which makes an exhaustive search impossible for \(N \le 10^5\).

Key Observation

Since we want to minimize the maximum difficulty, we want to prioritize using problems with lower difficulties. Therefore, let us sort the problems in ascending order of difficulty \(B_i\) in advance.

Iterating through the problems one by one in increasing order of difficulty, suppose we allow the difficulty of the current problem to be the maximum difficulty. In this case, we can maximize the total score by choosing the \(K\) problems with the largest scores \(A_i\) from among all problems seen so far. Since we process the problems in ascending order of difficulty, the difficulty at the first moment the sum of scores becomes at least \(P\) will be the answer—the minimum possible maximum difficulty.

Efficiently Maintaining the Top \(K\) Scores

As we add problems one by one in order of difficulty, we want to efficiently maintain the sum of the top \(K\) largest scores among the problems seen so far. This can be achieved using a min-heap (priority queue) maintained at a size of at most \(K\).

• Add the score \(A_i\) of the new problem to the heap and add it to the running sum.
• If the size of the heap exceeds \(K\), remove the minimum element from the heap and subtract it from the running sum.

In this way, the heap always holds the top \(K\) largest scores, allowing us to update and check the sum in \(O(\log K)\) for each problem.

Algorithm

1. Sort the problems in ascending order of difficulty \(B_i\).
2. Initialize a min-heap pq and a variable sum to store the sum of the elements in the heap.
3. Iterate through the sorted problems from beginning to end:
   • Push the current problem’s score \(A_i\) into pq and add \(A_i\) to sum.
   • If the size of pq exceeds \(K\), pop the minimum element (pq.top()) and subtract it from sum.
   • If the size of pq is equal to \(K\) and sum >= P, record the current problem’s difficulty \(B_i\) as the answer and break out of the loop.
4. If the loop finishes without satisfying the condition, output -1 indicating that it is impossible.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the problems takes \(O(N \log N)\).
  • For each problem, we perform insertions and deletions in the priority queue, taking \(O(N \log K)\) across the entire loop.
  • Overall, the time complexity is \(O(N \log N)\), which is fast enough for the constraint \(N = 10^5\).
• Space Complexity: \(O(N)\)
  • Storing the array of problems takes \(O(N)\) memory, and the priority queue uses at most \(O(K)\) memory.

Implementation Details

• Watch out for integer overflow: The target score \(P\) and the sum of chosen scores sum can reach up to \(10^{14}\), which overflows a 32-bit integer. In C++, make sure to use the long long type.

• Using a min-heap: In C++, std::priority_queue is by default a max-heap (which extracts the maximum element), so declare it with std::greater to make it a min-heap. This allows us to discard the unneeded problem with the smallest score in \(O(\log K)\) whenever the size exceeds \(K\).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

    int n, k;
    long long p;
    if (!(cin >> n >> k >> p)) return 0;

    struct Problem {
        long long a;
        long long b;
    };

    vector<Problem> probs(n);
    for (int i = 0; i < n; ++i) {
        cin >> probs[i].a >> probs[i].b;
    }

    sort(probs.begin(), probs.end(), [](const Problem& x, const Problem& y) {
        return x.b < y.b;
    });

    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long sum = 0;
    long long ans = -1;

    for (int i = 0; i < n; ++i) {
        pq.push(probs[i].a);
        sum += probs[i].a;
        if ((int)pq.size() > k) {
            sum -= pq.top();
            pq.pop();
        }
        if ((int)pq.size() == k && sum >= p) {
            ans = probs[i].b;
            break;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.