Overview

This is a problem where you maximize the total score by selecting all rest spots with positive scenic scores from among those with elevation strictly lower than \(X\).

Analysis

Key Insight: The constraint “visit in strictly decreasing order” is effectively not a constraint at all

At first glance, the condition “you must visit spots in strictly decreasing order of elevation” seems difficult. It might appear to require dynamic programming similar to the Longest Increasing Subsequence (LIS) problem.

However, there is an important observation here:

All \(A_i\) are distinct

This means that no matter which subset of spots you choose, if you arrange them in decreasing order of elevation, they always form a strictly decreasing sequence.

Verification with a concrete example

For example, suppose there are 3 spots with elevations \(\{100, 300, 200\}\). If you select all three, you can visit them in decreasing order of elevation as \(300 \to 200 \to 100\), which satisfies the strictly decreasing condition.

In other words, no matter which subset you choose, you can always satisfy the condition by visiting in the appropriate order.

The essence of the problem

Organizing the conditions:

1. Only spots satisfying \(A_i < X\) are candidates
2. You can choose any subset from the candidates (the ordering constraint is automatically satisfied as explained above)
3. You want to maximize the sum of \(B_i\) of the chosen spots

This reduces to a very simple problem:

Among the spots satisfying \(A_i < X\), select all those with \(B_i > 0\)

Spots with \(B_i > 0\) are beneficial to select, while spots with \(B_i \leq 0\) either cause a loss or make no difference, so they should not be selected. Since the score is \(0\) when no spots are visited, we only need to select those with positive scores.

Algorithm

1. For each spot, check whether \(A_i < X\) (elevation condition filter)
2. Among the spots satisfying the condition, sum up all \(B_i\) values where \(B_i > 0\)
3. Output that total (if no such spots exist, output \(0\))

Complexity

• Time complexity: \(O(N)\) — just a single pass through all spots
• Space complexity: \(O(N)\) — for reading the input (if storing the filtered list). If you only compute the sum, \(O(1)\) additional memory is sufficient

Implementation Notes

• Don’t forget the “strictly lower” condition \(A_i < X\): Spots with \(A_i = X\) cannot be selected. Note that the inequality is <, not <=.

• \(B_i\) can take negative values: Selecting a spot with a negative scenic score results in a loss, so only select those with positive values.

• Selecting 0 spots is possible: If all spots have \(B_i\) negative, or all have \(A_i \geq X\), the answer is \(0\).

• Fast input: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is effective to use bulk reading with sys.stdin.buffer.read().

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    X = int(input_data[idx]); idx += 1
    
    spots = []
    for i in range(N):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        if a < X:
            spots.append((a, b))
    
    # We need to select a subset of spots with strictly decreasing altitudes
    # and maximize the sum of B values.
    # Since altitudes are all distinct and we need strictly decreasing order,
    # the order is determined by sorting. We can pick any subset of spots
    # (sorted by decreasing altitude) and the constraint is automatically satisfied.
    # 
    # So the problem reduces to: pick a subset of the filtered spots to maximize
    # sum of B_i. This is simply the sum of all positive B_i values.
    
    result = 0
    for a, b in spots:
        if b > 0:
            result += b
    
    print(result)

main()

---

This editorial was generated by claude4.6opus-thinking.