Overview

This problem is an optimization problem that combines the constraint of staying within a budget of \(K\) yen (a knapsack problem element) with the constraint that adjacent streetlights cannot be selected simultaneously (a maximum independent set problem element). By using dynamic programming (DP), we can efficiently find the maximum value.

Analysis

First, the difficulty of this problem lies in the simultaneous presence of \(2\) constraints.

1. Cost constraint: The total cost must be at most \(K\) (a typical knapsack problem).
2. Placement constraint: Adjacent streetlights cannot be selected simultaneously.

If there were no cost constraint, this could be solved with a simple DP that maintains “the maximum value considering up to the \(i\)-th item.” Conversely, if there were no placement constraint, it could be solved as a standard \(0/1\) knapsack problem.

To combine these, we take the approach of maintaining the state of whether the \(i\)-th streetlight was replaced or not, while updating the maximum value for each budget amount.

Specifically, we manage the following \(2\) states: - dp0[j]: The maximum reduction effect when considering up to the \(i\)-th streetlight, with total cost \(j\), and not replacing the \(i\)-th streetlight - dp1[j]: The maximum reduction effect when considering up to the \(i\)-th streetlight, with total cost \(j\), and replacing the \(i\)-th streetlight

Algorithm

We solve this using dynamic programming (DP).

1. DP Table Definition

• dp0[j] : The maximum profit in the state of “not selecting” the \(i\)-th item when using budget \(j\)
• dp1[j] : The maximum profit in the state of “selecting” the \(i\)-th item when using budget \(j\)

2. Initial State

• dp0[0] = 0
• All other values are initialized to a very small value (\(-\infty\)) indicating they are unreachable.

3. Transitions (for the \(i\)-th streetlight \(V_i, W_i\))

Let the new states be new_dp0, new_dp1. They are updated as follows:

• When not replacing the \(i\)-th streetlight (new_dp0)
  • It doesn’t matter whether the \((i-1)\)-th was “replaced” or “not replaced.”
  • new_dp0[j] = max(dp0[j], dp1[j])
• When replacing the \(i\)-th streetlight (new_dp1)
  • Since adjacent streetlights cannot be replaced, we can only transition from the state where the \((i-1)\)-th was “not replaced.”
  • new_dp1[j] = dp0[j - W_i] + V_i (only when \(j \geq W_i\))

4. Final Answer

After considering all streetlights, the maximum value among all elements of dp0 and dp1 is the answer.

Complexity

• Time complexity: \(O(NK)\)
  • For \(N\) streetlights, we repeat a loop (or array operation) of size \(K\).
  • When \(N=200, K=10,000\), the number of computations is approximately \(2 \times 10^6\), which fits well within the time limit.
• Space complexity: \(O(K)\)
  • Since we only need to keep the previous state, the implementation requires memory independent of the number of streetlights \(N\).

Implementation Notes

• Initialization: Since the reduction effect can be \(0\), unreached states must be initialized not with 0 but with a sufficiently small value such as -1 or -10^18.

• Optimization in Python: Looping \(K\) times in Python can be slow. As in the provided code, by utilizing list slicing and map(max, ...), the operations are internally processed in C and run faster.

• Budget range: When updating new_dp1, care must be taken not to access indices below the cost \(W_i\).

  Source Code

import sys

def solve():
    # 競技プログラミングにおいて高速な入力読み込みを行うため、sys.stdin.read().split()を使用します。
    # これにより、すべての入力トークンをリストとして取得できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 街路灯の数, K: 予算の上限
    N = int(input_data[0])
    K = int(input_data[1])
    
    # dp0[j]: i番目までの街路灯を考慮し、合計費用がjで、i番目を「交換しない」場合の最大削減効果
    # dp1[j]: i番目までの街路灯を考慮し、合計費用がjで、i番目を「交換する」場合の最大削減効果
    # 到達不可能な状態を表現するために、十分に小さな負の数（-INF）で初期化します。
    INF = 10**18
    dp0 = [-INF] * (K + 1)
    dp1 = [-INF] * (K + 1)
    
    # 初期状態：0個の街路灯を考慮し、費用0、削減効果0
    dp0[0] = 0
    
    # 各街路灯について順番にDPテーブルを更新します。
    for i in range(N):
        # i番目の街路灯の削減効果 V_i と交換費用 W_i
        v = int(input_data[2 + 2 * i])
        w = int(input_data[3 + 2 * i])
        
        # new_dp0: 今回の街路灯を「交換しない」場合の更新
        # 前の街路灯が「交換された」か「交換されていない」かのどちらの状態からも遷移可能です。
        # Pythonのmap(max, ...)は要素ごとの最大値を高速に計算できます。
        new_dp0 = list(map(max, dp0, dp1))
        
        # new_dp1: 今回の街路灯を「交換する」場合の更新
        # 隣り合う街路灯を同時に交換できないため、前の街路灯が「交換されていない」状態からのみ遷移可能です。
        new_dp1 = [-INF] * (K + 1)
        if w <= K:
            # 予算内の範囲で、前の状態(dp0)に削減効果 v を加算します。
            # リストのスライスとリスト内包表記を用いることで、Pythonでの処理速度を向上させます。
            dp0_prev_part = dp0[:K - w + 1]
            new_dp1[w:] = [x + v for x in dp0_prev_part]
        
        # DPテーブルを更新
        dp0 = new_dp0
        dp1 = new_dp1
        
    # すべての街路灯を考慮した後の、予算内での最大削減効果を求めます。
    # dp0[0]が常に0以上であるため、ansも必ず0以上になります。
    ans = max(max(dp0), max(dp1))
    
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

---

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