Overview

This problem asks you to determine whether each quest satisfies the “efficient quest” condition, sum up the experience points of quests that meet the condition, and check if the total reaches the target value.

Analysis

The key points for this problem are as follows:

Efficient Quest Condition

Quest \(i\) is an efficient quest when the experience gained \(R_i\) is at least \(K\) times the stamina consumed \(D_i\), that is: $\(R_i \geq K \times D_i\)$

Understanding with Examples

For example, when \(K = 3\): - Quest A: \(D = 10\), \(R = 50\) → \(50 \geq 3 \times 10 = 30\), so it’s efficient ✓ - Quest B: \(D = 20\), \(R = 40\) → \(40 \geq 3 \times 20 = 60\) is false, so it’s inefficient ✗

Simplicity of This Problem

This problem doesn’t require complex algorithms. We simply check the condition for each quest and sum up the experience points of those that satisfy it.

However, note that \(T\) can be as large as \(10^{18}\), and since \(R_i\) can be up to \(10^9\) with \(N\) up to \(2 \times 10^5\), the total experience can reach approximately \(2 \times 10^{14}\). In Python, we don’t need to worry about integer overflow, so this isn’t a problem.

Algorithm

1. Read \(N\), \(K\), \(T\)
2. Initialize a variable total_exp to \(0\) to hold the sum of experience points
3. For each quest \(i\):
   • Read \(D_i\) and \(R_i\)
   • If \(R_i \geq K \times D_i\), add \(R_i\) to total_exp
4. Finally, output Yes if total_exp >= T, otherwise output No

total_exp = 0
for each quest i:
    if R[i] >= K * D[i]:
        total_exp += R[i]

if total_exp >= T:
    output "Yes"
else:
    output "No"

Complexity

• Time Complexity: \(O(N)\)
  • We perform constant-time checking and addition for each quest
• Space Complexity: \(O(1)\)
  • We only use a variable to hold the total experience and don’t need to store information about all quests

Implementation Notes

1. Beware of Overflow (for other languages): In languages like C++, the calculation of \(K \times D_i\) and the sum of experience points may overflow, so you need to use appropriate types (such as long long). In Python, integers have no upper limit, so this isn’t a concern.

2. Efficient Input Processing: By checking and adding while reading, without storing quest information in an array, we keep the space complexity at \(O(1)\).

3. How to Write the Condition: Simply write \(R_i \geq K \times D_i\) as R >= K * D. Avoid writing it as R / D >= K using division, as this may cause floating-point precision errors.

Source Code

def main():
    N, K, T = map(int, input().split())
    
    total_exp = 0
    for _ in range(N):
        D, R = map(int, input().split())
        # Efficient quest: R >= K * D
        if R >= K * D:
            total_exp += R
    
    if total_exp >= T:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.