Overview

Given a budget \(K\), the problem asks to maximize the total reduction effect (value) of selected streetlights, subject to the constraint that no two adjacent streetlights can be selected simultaneously. We handle “independent set on a line (no adjacent selections)” and “knapsack (budget constraint)” at the same time.

Analysis

The difficulty of this problem lies in having two types of constraints:

• Budget constraint: The total cost \(W_i\) of selected streetlights must be at most \(K\) (knapsack)
• No adjacent selections: Streetlights \(i\) and \(i+1\) cannot be selected simultaneously (one-dimensional adjacency constraint)

A naive brute-force approach of “select or don’t select” each streetlight would result in \(2^N\) possibilities, which is far too slow for \(N \le 200\).

On the other hand, if we only had the adjacency constraint, \(dp[i] =\) “maximum value considering streetlights \(1..i\)” could be solved with a standard DP, but here we also need to track “the cost used” as part of the state, and we must simultaneously ensure that when selecting streetlight \(i\), streetlight \(i-1\) was not selected.

The key insight is as follows:

• As long as we know “whether the previous streetlight (\(i-1\)) was selected,” we can enforce the adjacency constraint
• Since \(K \le 10^4\), a DP with cost as a state dimension runs in \(O(NK)\), which is fast enough

Therefore, by designing a DP that separates into “the previous streetlight was not selected” and “the previous streetlight was selected”, we can satisfy both the adjacency constraint and the budget constraint.

Algorithm

Let \(c\) (\(0 \le c \le K\)) denote the total cost, and consider the following DP:

• \(dp0[c]\): The maximum reduction effect when, at the current position, “the previous streetlight was not selected” and the total cost is \(c\)
• \(dp1[c]\): The maximum reduction effect when, at the current position, “the previous streetlight was selected” and the total cost is \(c\)

The initial state is that nothing has been selected yet: - \(dp0[0] = 0\) - All other states are set to \(-\infty\) (represented as a sufficiently small value NEG in the code) to indicate impossible states

We process each streetlight \((v, w)\) one by one and perform the following transitions.

1. Do not select the current streetlight

If we don’t select the current one, we transition to the “previous not selected” state for the next step. Regardless of whether the previous one was selected (\(dp0\) or \(dp1\)), since “we don’t select the current one,” the next state is always “not selected.”

• \(new0[c] = \max(dp0[c], dp1[c])\)

2. Select the current streetlight

To select the current one, the adjacency constraint requires that “the previous one was not selected.” Thus, we can only transition from \(dp0\).

• \(new1[c] = dp0[c-w] + v\) (only when \(c \ge w\))

This transitions to the “previous was selected” state.

Finally, after processing all streetlights, the answer is: - \(\max_c \max(dp0[c], dp1[c])\) (since the last streetlight can be either selected or not selected).

Complexity

• Time complexity: \(O(NK)\) (For each streetlight, we scan costs \(0..K\))
• Space complexity: \(O(K)\) (Using arrays of length \(K+1\) for \(dp0\) and \(dp1\), updated via rolling arrays)

Implementation Notes

• A value to represent impossible states is needed. In the code, NEG = -10**30 is used to distinguish unreachable states (since \(V_i\) is at most \(10^9\) and \(N \le 200\), this is sufficiently small).

• Array updates use a rolling approach (create new0/new1 and swap them in), keeping space at \(O(K)\).

• The “select” transition is always from \(dp0\) only, which naturally enforces the adjacency constraint.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    k = int(next(it))

    NEG = -10**30
    dp0 = [NEG] * (k + 1)  # previous not chosen
    dp1 = [NEG] * (k + 1)  # previous chosen
    dp0[0] = 0

    for _ in range(n):
        v = int(next(it))
        w = int(next(it))

        new0 = [NEG] * (k + 1)
        new1 = [NEG] * (k + 1)

        for c in range(k + 1):
            a = dp0[c]
            b = dp1[c]
            new0[c] = a if a >= b else b

        for c in range(w, k + 1):
            prev = dp0[c - w]
            if prev != NEG:
                val = prev + v
                if val > new1[c]:
                    new1[c] = val

        dp0, dp1 = new0, new1

    print(max(max(dp0), max(dp1)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.