Overview

This problem is a dynamic programming problem where we maximize the number of mountains to climb while satisfying several constraints (number of climbs, strictly increasing elevation, and budget).

Analysis

First, this problem has the following three conditions: 1. The number of mountains to climb is at most \(K\). 2. The elevations of the climbed mountains must be strictly increasing in order of their indices. 3. The total admission fee for the climbed mountains must be at most \(B\) yen.

The goal is to maximize the number of climbs \(m\) while satisfying all of these conditions.

Naive Approach and Its Issues

The most naive method is to try all combinations, but since the number of mountains \(N\) can be up to 500, this is not practical. Also, since we can only proceed in order of mountain indices, the constraint that “we cannot climb a mountain with elevation lower than or equal to the last climbed mountain” becomes important.

Focusing on the “strictly increasing elevation” requirement, by keeping track of the elevation of the last climbed mountain, we can determine whether the next mountain can be climbed.

Solution: Dynamic Programming (DP)

We consider the following DP table:

dp[k][b] := Among all ways to climb \(k\) mountains with a total cost of at most \(b\) yen, the minimum value of the elevation of the last climbed mountain

• The reason for tracking “the minimum elevation” is to preserve as many possibilities as possible for climbing more mountains.
• If we have climbed a mountain with a lower elevation, we have more options to climb higher mountains afterward.

Update Method

For each mountain \(i\) (with admission fee \(c\) and elevation \(s\)), we update the DP table as follows:

• If there exists a state where we have already climbed \(k-1\) mountains with cost \(b - c\), and the last elevation in that state is less than \(s\), then we can update the new state \((k, b)\) with elevation \(s\).

To avoid selecting the same mountain multiple times, we need to update in reverse order (from back to front).

Algorithm

1. Initialize the DP table dp[k][b]. Set dp[0][0] = -1 (since elevations are positive), and all others to \(\infty\).
2. For each mountain \(i\):
   • Loop in reverse order from \(k = K\) down to \(1\), and from \(b = B\) down to \(c\).
   • If dp[k-1][b - c] < s, then update with dp[k][b] = min(dp[k][b], s).
3. The answer is the maximum \(k\) such that dp[k][b] != INF for some \(b\).

Complexity

• Time complexity: \(O(N \cdot K \cdot B)\)
• Space complexity: \(O(K \cdot B)\)

※ Since \(K \leq 50\) and \(B \leq 500\), this runs sufficiently fast.

Implementation Notes

• The DP table update must be done in reverse order. This prevents using the same mountain multiple times.

• By setting dp[0][0] = -1, transitions to the first mountain become straightforward.

• The key insight is tracking “the minimum elevation of the last climbed mountain,” which expands the range of future choices.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    B = int(data[idx])
    idx += 1
    
    C = [0] * N
    S = [0] * N
    for i in range(N):
        C[i] = int(data[idx])
        idx += 1
        S[i] = int(data[idx])
        idx += 1

    # dp[i][k][b] = 最初のi個の山について、k個登頂し、コスト合計がb以下であるような
    #                最後に登頂した山の標高の最小値（不可能ならINF）
    INF = float('inf')
    # dpは3次元だが、KとBが小さいのでOK
    # dp[k][b] = 最後に登頂した山の標高の最小値（可能なら）、k個登頂、コストb
    dp = [[INF] * (B + 1) for _ in range(K + 1)]
    dp[0][0] = -1  # 標高が正なので-1で初期化

    for i in range(N):
        c = C[i]
        s = S[i]
        # 後ろから更新することで同じ山を複数回使わないようにする
        for k in range(K, 0, -1):
            for b in range(B, c - 1, -1):
                prev_b = b - c
                # 以前の状態でk-1個選んで、最後の標高がs未満なら遷移可能
                if dp[k-1][prev_b] < s:
                    if dp[k][b] > s:
                        dp[k][b] = s

        # k=0のときはコストだけ更新
        for b in range(B, c - 1, -1):
            if dp[0][b - c] < s:  # 実際にはk=0では標高の制約はないが、dp[0][*] = -1で十分
                pass
            # 実際にはdp[0][b]は常に-1で良いが、念のため更新しない

    # 最大のkを見つける
    max_k = 0
    for k in range(K + 1):
        for b in range(B + 1):
            if dp[k][b] != INF:
                max_k = max(max_k, k)
    print(max_k)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.