Overview

Under the constraint that “you can only solve problems with difficulty at most your current skill level,” determine whether you can choose problems wisely to raise your final skill to at least \(T\).

Analysis

There are two key observations:

• Among the problems you can solve, solving the easiest one first is safe (and in fact optimal)

  • Solving any problem increases your skill, but you must satisfy the condition “your current skill must be at least the problem’s difficulty” to solve it.
  • Therefore, by solving the easiest problem you can currently solve, your skill reliably increases and the range of problems you can solve next expands.
  • Conversely, there is no benefit to choosing a harder problem first when easier ones are available — there is “no reason to postpone easier problems.”

• Sort in ascending order and iterate; if you get stuck at any point, you can never solve anything beyond that

  • Arrange difficulties in ascending order and repeatedly “solve if possible” from left to right.
  • If at some point \(d > \text{cur}\) (current skill), then since the array is sorted in ascending order, all subsequent problems satisfy \(d' \ge d > \text{cur}\).
  • Therefore, none of the remaining problems can be solved, and your skill cannot increase any further.

If you naively “search for a solvable problem each time” or “try all subsets”: - Exhaustive search is \(2^N\), which is infeasible - Strategies like “always pick the hardest solvable problem” have no guaranteed correctness (a common cause of WA) - Even with advanced data structures, what you ultimately want is “process solvable problems in ascending order,” so sorting once and making a single pass is the simplest and most reliable approach.

Concrete example: - \(S=10\), problems \([1, 9, 20]\) - Solving in ascending order: \(10 \to 11\) (solve 1) \(\to 20\) (solve 9), reaching 20, which allows solving the problem with difficulty 20 - If an “unsolvable problem” is encountered, everything beyond it is also unsolvable, so we can terminate early

Algorithm

1. Sort the difficulty array \(D\) in ascending order.
2. Set current skill \(\text{cur}=S\). If \(\text{cur} \ge T\) from the start, output Yes.
3. For each \(d\) in the sorted order:
   • If \(d > \text{cur}\), no further problems can be solved, so break out of the loop.
   • Otherwise, the problem can be solved, so set \(\text{cur} \leftarrow \text{cur} + d\).
   • If \(\text{cur} \ge T\), output Yes.
4. If we finish without reaching \(T\), output No.

This method is correct for determining reachability because “solving problems from easiest to hardest maximizes your skill as much as possible.”

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the array)

Implementation Notes

• \(S,T\) can be up to \(10^{18}\), so depending on the language, 64-bit integers are required (Python’s int is arbitrary precision, so this is not an issue).

• After sorting, only a single pass is needed, so you can break immediately when \(d > \text{cur}\) (since the array is sorted in ascending order).

• Early termination when \(\text{cur} \ge T\) is reached midway improves performance.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, S, T = map(int, input().split())
    D = list(map(int, input().split()))
    D.sort()

    cur = S
    if cur >= T:
        print("Yes")
        return

    for d in D:
        if d > cur:
            break
        cur += d
        if cur >= T:
            print("Yes")
            return

    print("Yes" if cur >= T else "No")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.