Overview

This problem is a variant of the knapsack problem where we maximize profit while keeping the total accommodation cost within \(M\). The difference from the standard knapsack problem is the movement distance constraint: “the gap between any two consecutively chosen towns must be at most \(K\).”

Analysis

1. Dynamic Programming (DP) Definition

If we know “which town was visited last” and “the total accommodation cost so far,” we can determine which town to visit next. Therefore, we define the following DP table:

• dp[i][j]: The maximum profit when town \(i\) is chosen as the last visited town and the total accommodation cost is \(j\)

2. Transition Logic

When visiting town \(i\), if the previously visited town is \(p\), then the condition \(i - p \leq K\) must be satisfied. In other words, letting \(A_i\) be the profit and \(B_i\) be the accommodation cost at town \(i\), the transition formula is:

\[dp[i][j + B_i] = \max_{i-K \leq p < i} \{ dp[p][j] \} + A_i\]

Additionally, if town \(i\) is the “first town visited,” there is no previous town, so simply \(dp[i][B_i] = A_i\).

3. Optimization Techniques

A naive computation of the transitions would search the most recent \(K\) towns for each \(i, j\), resulting in a time complexity of \(O(N \times M \times K)\). While this might be feasible under the given constraints (\(N, M \le 200\)), we can apply the sliding window maximum technique for a more efficient solution.

For each accommodation cost \(j\), we use a “sliding window (deque)” to maintain the maximum of \(dp[p][j]\) over the most recent \(K\) towns, allowing maximum value retrieval in \(O(1)\). This reduces the overall time complexity to \(O(NM)\).

Algorithm

1. Initialize the DP table dp[N][M+1] with \(-1\) (unreachable).
2. For each accommodation cost \(j \in [0, M]\), prepare a deque to manage the maximum values.
3. For towns \(i = 0\) to \(N-1\), perform the following in order:
   • For each accommodation cost \(j\), remove indices from the front of the deque that correspond to “old towns more than \(K\) away from the current town \(i\).”
   • (Transition 1) Use the front of the deque (the maximum value within range) to update dp[i][j + B_i].
   • (Transition 2) Consider the case where town \(i\) is the first town (\(dp[i][B_i] = A_i\)).
   • For the next town, add the current dp[i][j] to the deque. When doing so, maintain the deque in monotonically decreasing order of values.
4. The answer is the maximum value among all entries in the dp table.

Complexity

• Time Complexity: \(O(N \times M)\)
  • This is a double loop over towns (\(N\)) and accommodation costs (\(M\)). Deque operations involve one addition and one removal per element in amortized \(O(1)\).
• Space Complexity: \(O(N \times M)\)
  • The DP table has size \(N \times (M+1)\).

Implementation Notes

• Initialization: Since profit can be \(0\), unreached states should be distinguished using \(-1\) or similar.

• Deque Management: deques[j] stores indices that manage “the maximum profit among the past \(K\) towns when the accommodation cost is exactly \(j\).”

• Range Checking: Before processing a new town \(i\), verify that the index \(p\) at the front of the deque satisfies \(i - p \leq K\).

  Source Code

import sys
from collections import deque

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 町の数, M: 滞在費の総額の上限, K: 馬車が一度に移動できる町の数の上限
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # 各町の利益 A_i と滞在費 B_i を取得
    A = []
    B = []
    for i in range(N):
        A.append(int(input_data[3 + 2*i]))
        B.append(int(input_data[4 + 2*i]))
        
    # dp[i][j] は、i 番目の町を最後に訪れ、滞在費の合計が j であるときの最大利益を表す。
    # -1 はその状態が到達不可能であることを示す。
    dp = [[-1] * (M + 1) for _ in range(N)]
    
    # 各滞在費 j について、直近 K 個の町の中での最大利益を効率的に管理するため、スライディングウィンドウ（deque）を使用する。
    # deques[j] は、dp[p][j] (p < i) の最大値を求めるためのインデックスを保持する。
    deques = [deque() for _ in range(M + 1)]
    
    for i in range(N):
        ai = A[i]
        bi = B[i]
        
        # 1. 町 i を、それ以前に訪れた町 p (i-K <= p < i) の次に訪れる場合を考える。
        # 各滞在費 j について、ウィンドウ [i-K, i-1] 内で最大の利益を持つ町 p を deques[j][0] から取得する。
        for j in range(M - bi + 1):
            if deques[j]:
                best_p = deques[j][0]
                # deques[j][0] に入っているインデックス p は、dp[p][j] が最大であることを保証されている。
                if dp[best_p][j] != -1:
                    new_profit = dp[best_p][j] + ai
                    if new_profit > dp[i][j + bi]:
                        dp[i][j + bi] = new_profit
        
        # 2. 町 i を最初に訪れる町とする場合を考える。
        if bi <= M:
            if ai > dp[i][bi]:
                dp[i][bi] = ai
        
        # 3. 次の町 (i+1) 以降の計算のために、現在の dp[i] の結果を deques に追加し、ウィンドウ外のインデックスを削除する。
        for j in range(M + 1):
            # 現在の町 i の結果を deque に追加（単調性を維持）
            if dp[i][j] != -1:
                while deques[j] and dp[deques[j][-1]][j] <= dp[i][j]:
                    deques[j].pop()
                deques[j].append(i)
            
            # 次の町 (i+1) のウィンドウは [i+1-K, i] なので、i+1-K 未満（つまり i-K 以下）のインデックスを削除する。
            if deques[j] and deques[j][0] <= i - K:
                deques[j].popleft()
                
    # 全ての dp テーブルの中から最大の利益を探す。
    ans = 0
    for i in range(N):
        for j in range(M + 1):
            if dp[i][j] > ans:
                ans = dp[i][j]
    
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.