Overview

Given \(N\) towns arranged from east to west, we want to find a selection of towns that maximizes profit while considering movement restrictions and budget constraints.

Analysis

In this problem, the selected towns do not need to have consecutive numbers, but when the numbers of the selected towns are sorted in ascending order, the difference between adjacent numbers must be at most \(K\). This means that the range of movement is limited.

For example, when \(K=2\), moving from town \(1 \to 3\) is possible, but \(1 \to 4\) is not.

Additionally, each town has a profit \(A_i\) and a stay cost \(B_i\), and we want to maximize the total profit under the constraint that the total stay cost is at most \(M\) yen.

A naive approach would be to consider all subsets of towns and choose the one with the maximum profit among those satisfying the constraints, but since \(N\) can be up to \(200\), this is computationally infeasible (\(2^{200}\) is extremely large).

Therefore, it is effective to use dynamic programming (DP) based on “the last town visited” and “the cost spent so far.”

Algorithm

We define the following DP table for this problem:

\[ \text{dp}[i][m] := \text{maximum profit when town } i \text{ is the last selected town with cost at most } m \]

In the initial state, for each town \(i\), we set the case where only that town is selected (as the first town): - \(\text{dp}[i][B_i] = A_i\) (provided that \(B_i \leq M\))

Then, for each town \(i\), we perform transitions to the next reachable town \(j\) (i.e., \(i < j \leq \min(i + K, N - 1)\)).

Specifically, from the current cost \(m\) and profit \(\text{dp}[i][m]\), we calculate the new cost and profit when visiting the next town \(j\), and update if a better value is found:

\[ \text{new\_cost} = m + B_j,\quad \text{new\_profit} = \text{dp}[i][m] + A_j \]

Then, if \(\text{new\_cost} \leq M\) and \(\text{dp}[j][\text{new\_cost}] < \text{new\_profit}\), we update:

\[ \text{dp}[j][\text{new\_cost}] = \text{new\_profit} \]

Finally, the answer is the maximum profit among all \(\text{dp}[i][m]\).

Complexity

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

Since \(N, M, K\) are at most \(200\), the maximum computation is approximately \(8 \times 10^6\), which is sufficiently fast.

Implementation Notes

• Initialize the DP table with \(-1\) beforehand to represent “unreachable states.”
• When initializing each town as the “first town,” do not forget to check that \(B_i \leq M\).
• When updating, be careful not to exceed the budget (\(\text{new\_cost} \leq M\)).
• At the end, scan the entire table to obtain the maximum profit.

## Source Code

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    A = [0] * N
    B = [0] * N
    
    for i in range(N):
        A[i] = int(data[3 + 2*i])
        B[i] = int(data[4 + 2*i])
    
    # dp[i][m] := i番目の町を最後に選んだ、コストがm以下での最大利益
    # 初期化: -1 で初期化し、到達不可能を示す
    dp = [[-1] * (M + 1) for _ in range(N)]
    
    # 初期状態：各町を最初に選ぶ場合
    for i in range(N):
        if B[i] <= M:
            dp[i][B[i]] = A[i]
    
    # DP更新
    for i in range(N):
        for j in range(i + 1, min(i + K + 1, N)):
            cost_next = B[j]
            profit_next = A[j]
            for m in range(M - cost_next + 1):
                if dp[i][m] != -1:
                    new_cost = m + cost_next
                    new_profit = dp[i][m] + profit_next
                    if new_cost <= M:
                        if dp[j][new_cost] < new_profit:
                            dp[j][new_cost] = new_profit
    
    # 最大利益を探す
    max_profit = 0
    for i in range(N):
        for m in range(M + 1):
            if dp[i][m] > max_profit:
                max_profit = dp[i][m]
    
    print(max_profit)

if __name__ == "__main__":
    main()

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