Overview

This problem asks us to select mountain peaks such that their altitudes are strictly increasing, while maximizing the number of peaks climbed under constraints on budget and the maximum number of peaks.

Analysis

The problem has the following 3 conditions: 1. The number of peaks climbed is at most K 2. The altitudes of the climbed peaks must be strictly increasing in order of their indices 3. The total entrance fees must be at most B yen

A brute-force search would consider whether to climb or skip each peak, resulting in \(O(2^N)\) complexity, which is infeasible for N=500. We need to solve this efficiently using dynamic programming.

The key observation is that to satisfy the strictly increasing altitude condition, the altitude of the next chosen peak must be greater than that of the previously chosen peak. We would like to manage the state as “number of peaks chosen,” “total cost,” and “altitude of the last chosen peak,” but since altitude values can be large (up to \(10^9\)), we cannot directly include them in the state.

Instead, we design the state to minimize “the altitude of the last chosen peak.” Among configurations with the same number of peaks and same cost, the one with a smaller last altitude is better because it allows more options for the next peak to choose.

Algorithm

We solve this using dynamic programming. The DP table is defined as follows: - \(dp[j][b]\): the minimum value of “the altitude of the last chosen peak” when exactly j peaks are chosen and the total cost is b

The initial state is \(dp[0][0] = 0\) for choosing 0 peaks (since actual altitudes are positive values, no peak has an altitude less than 0).

For each peak i (cost \(c_i\), altitude \(s_i\)), we perform the following update: - If in the state of having chosen j peaks with total cost b, the last altitude satisfies \(dp[j][b] < s_i\) (ensuring strictly increasing altitude), then - We can update the state of choosing j+1 peaks with total cost b+c_i to \(s_i\) - We only update if the new value is smaller than the existing value (since we are minimizing)

We perform this update for peaks 1 through N in order, and finally find the maximum j such that \(dp[j][b]\) is valid for some \(b \leq B\).

Complexity

• Time complexity: \(O(N \times K \times B)\)
  • A triple loop over the number of peaks N, maximum selection count K, and maximum budget B
  • Since N=500, K=50, B=500, this results in 500×50×500=12,500,000 operations, which is fast enough
• Space complexity: \(O(K \times B)\)
  • The DP table size is (K+1)×(B+1)

Implementation Notes

1. DP table initialization: Initialize with a sufficiently large value (INF), with only \(dp[0][0] = 0\) as the initial state

2. Update from the back: To avoid counting the same peak multiple times, iterate j from the back (K-1→0)

3. Iterate the cost loop from the back as well: To avoid adding the same peak’s cost multiple times

4. Finding the answer: Finally, scan the DP table and find the maximum j among all valid states

   Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    it = iter(data)
    N = int(next(it)); K = int(next(it)); B = int(next(it))
    costs = []
    heights = []
    for i in range(N):
        c = int(next(it)); s = int(next(it))
        costs.append(c)
        heights.append(s)
    
    # dp[j][b]: 合計j個選び、合計コストがbであるときの最後の標高の最小値（より小さい方が良い）
    INF = 10**18
    dp = [[INF] * (B+1) for _ in range(K+1)]
    dp[0][0] = 0   # 0個選んだとき、コスト0、最後の標高は0（実際の標高は正なので0より小さい山はない）
    
    ans = 0
    for i in range(N):
        c = costs[i]
        s = heights[i]
        # 後ろから更新（同じ山を2回使わないように）
        for j in range(K-1, -1, -1):
            for b in range(B - c, -1, -1):
                if dp[j][b] < s:
                    if dp[j+1][b+c] > s:
                        dp[j+1][b+c] = s
        # 直接更新しないで、ループの後で確認する
    
    # 答えを探す: jが最大で、b<=Bのもの
    for j in range(K, -1, -1):
        for b in range(B+1):
            if dp[j][b] < INF:
                if j > ans:
                    ans = j
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.