Overview

The problem asks us to choose \(K\) problems out of \(N\) such that the sum of their scores is at least \(P\), while minimizing the maximum difficulty among them. This can be solved by “sorting by difficulty and maintaining the sum of the top \(K\) largest scores while incrementally adding candidates from the beginning.”

Analysis

Insight 1: Fix the Answer and Formulate a Decision Problem

For problems asking for the “minimum possible value of the maximum difficulty”, a standard approach is to fix the answer to \(X\) and convert it into a decision problem.

“Can we choose \(K\) problems such that the maximum difficulty is at most \(X\) and the total score is at least \(P\)?”

This decision is simple. The only usable problems are those satisfying \(B_i \le X\), so we just need to take the \(K\) problems with the largest scores \(A_i\) among them and check if their sum is at least \(P\) (since we want to maximize the sum, greedily taking the largest scores is optimal). Of course, if there are fewer than \(K\) problems satisfying \(B_i \le X\), it is impossible.

Insight 2: Monotonicity

Increasing \(X\) only increases the set of usable problems, so if it is achievable with \(X\), it is also achievable with any \(X' > X\). In other words, the decision result is monotonic with respect to \(X\), so binary search can be used.

However, the meaningful candidates for \(X\) are essentially just the values of \(B_i\). Thus, if we sort by \(B\) and consider “being able to use up to the first \(i\) problems” as we vary \(i\), we can solve this in a single scan without writing a binary search. This approach is easier to implement.

Issue with the Naive Approach

If, for each \(i\), we compute the “sum of the top \(K\) largest \(A\) among the first \(i\) problems” by sorting each time, it would take \(O(N K \log N)\) or \(O(N^2 \log N)\), which will exceed the time limit for \(N = 10^5\).

Instead, we can use the fact that the set of the top \(K\) elements barely changes as we increment \(i\) by \(1\). Whether a new element \(A_i\) enters this set can be determined simply by comparing it with the “minimum value among the \(K\) elements we currently hold”. This can be maintained precisely using a priority queue that allows extraction of the minimum element (min-heap).

Algorithm

1. Pair each problem as \((B_i, A_i)\) and sort them in ascending order of \(B\).
2. Prepare a min-heap pq (the currently selected values of \(A\)) and their total sum sum.
3. Iterate through \(i = 0, 1, \dots, N-1\) in order:
   • If the size of pq is less than \(K\), add \(A_i\) and update sum += A_i.
   • If the size is \(K\) and \(A_i > \) the minimum element of pq, remove the minimum element and insert \(A_i\) (also updating sum). This consistently maintains the “top \(K\) largest \(A\) among the first \(i+1\) elements”.
   • After that, if the size of pq is \(K\) and sum \(\ge P\), the answer is \(B_i\) (the \(i\)-th \(B\) after sorting), so print it and terminate.
4. If the condition is not met by the end, print \(-1\).

Why is \(B_i\) at the moment the condition is first satisfied the answer? The fact that the condition was not satisfied up to the \((i-1)\)-th problem means that no matter how we choose \(K\) problems from the first \(i\) problems (\(0\) to \(i-1\)), the sum of scores is strictly less than \(P\) (since the sum of the top \(K\) largest scores is the maximum possible sum). Therefore, an optimal solution must include the \(i\)-th problem, and the maximum difficulty among the chosen problems will be \(B_i\). Even if multiple problems share the same value of \(B\), the output value will be identical, so this is not an issue.

Concrete Example

Consider the case where \(N=4, K=2, P=10\), and \((A,B) = (3,5), (8,2), (4,9), (6,3)\).

Sorting in ascending order of \(B\) gives \((8,2), (6,3), (3,5), (4,9)\).

• \(i=0\): pq \(=\{8\}\), sum \(=8\) (size \(1 < K\))
• \(i=1\): pq \(=\{8,6\}\), sum \(=14 \ge 10\) and size \(=2=K\) \(\rightarrow\) answer \(B=3\)

Indeed, choosing the problems with scores \(8\) and \(6\) gives a total of \(14 \ge 10\), and the maximum difficulty is \(3\).

Complexity

• Time Complexity: \(O(N \log N)\) (sorting and heap operations each take \(O(N \log N)\))
• Space Complexity: \(O(N)\)

Key Implementation Points

• Overflow: Since \(P \le 10^{14}\) and the sum of scores can be up to \(10^5 \times 10^9 = 10^{14}\), it will overflow a 32-bit int. Use a 64-bit integer (long long) for the sum and \(P\).

• Sorting pairs: Storing elements in pair<long long, long long> in the order of \((B, A)\) allows sort to order them by \(B\) in ascending order (be careful not to place \(A\) as the first element).

• How to write a min-heap: In C++, priority_queue is a max-heap by default, so write priority_queue<long long, vector<long long>, greater<long long>> to make it a min-heap.

• Do not check the condition with fewer than \(K\) elements: Since we need to choose exactly \(K\) problems, be sure to include the condition pq.size() == K.

• If implemented using binary search, within the decision function we can find the “sum of the top \(K\) largest \(A\) among problems with \(B_i \le X\)” by sorting descending, which will pass in about \(O(N \log^2 N)\). However, the scanning approach described above is simpler.

  Source Code

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

int main(){
    int N; long long K, P;
    scanf("%d %lld %lld", &N, &K, &P);
    vector<pair<long long,long long>> v(N); // (B, A)
    for(int i=0;i<N;i++){
        long long a,b;
        scanf("%lld %lld",&a,&b);
        v[i] = {b,a};
    }
    sort(v.begin(), v.end());
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long sum = 0;
    for(int i=0;i<N;i++){
        long long a = v[i].second;
        if((long long)pq.size() < K){
            pq.push(a);
            sum += a;
        } else if(!pq.empty() && a > pq.top()){
            sum -= pq.top();
            pq.pop();
            pq.push(a);
            sum += a;
        }
        if((long long)pq.size() == K && sum >= P){
            printf("%lld\n", v[i].first);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

---

This editorial was generated by claude5opus-high.