Overview

This problem asks us to place several advertising panels (width \(w_i\), value \(b_i\)) without overlapping along a corridor of total length \(L\), under the constraint that no consecutive sequence of empty slots may be \(K\) or more (i.e., every contiguous empty gap must have width at most \(K-1\)), and to maximize the total value obtained.

We determine whether a valid placement exists, and if so, find the maximum value.

---

Analysis

1. Formulating the Fire Safety Regulation as an Inequality

Let \(j\) be the number of advertising panels selected. When \(j\) panels are placed in the corridor, there are a total of \(j + 1\) gaps (empty intervals) — between adjacent panels and at both ends.

To satisfy the fire safety regulation, the length of each of these \(j + 1\) gaps must be at most \(K - 1\). Therefore, the maximum total number of empty slots is \((j + 1) \times (K - 1)\), which occurs when every gap has the maximum length \(K - 1\).

If the total width of the \(j\) selected panels is \(w\), then the actual total number of empty slots is \(L - w\). Thus, the necessary and sufficient condition for a valid placement satisfying the fire safety regulation is: $\(L - w \le (j + 1) \times (K - 1)\)$

Rearranging with respect to \(w\), we obtain: $\(w \ge L - (j + 1) \times (K - 1)\)$

Additionally, since panels must not extend beyond the corridor, we naturally require \(w \le L\) as well.

2. Reduction to a Knapsack Problem

From the above analysis, the problem can be restated as follows:

Select \(j\) panels from the \(N\) available panels, and let \(w\) be their total width. Among all selections satisfying $\(L - (j + 1) \times (K - 1) \le w \le L\)$ find the maximum total value.

This can be solved as a knapsack problem with item count tracking (dynamic programming), maintaining two state dimensions: the number of selected items \(j\) and the total width \(w\).

---

Algorithm

Dynamic Programming (DP) Design

DP Table Definition: dp[j][w] : The maximum attractiveness (value) when exactly \(j\) panels are selected with a total width of exactly \(w\) (unreachable states are marked as -1).

Initial State: - dp[0][0] = 0 - All other entries are -1

Transition: For each panel \(i\) (\(1 \le i \le N\), width \(w_i\), value \(b_i\)), update the DP table. To avoid selecting the same panel more than once, iterate over the count \(j\) in reverse order (from large to small).

When dp[j][w] holds a valid value (not \(-1\)), selecting this panel yields the following transition: $\(\text{dp}[j + 1][w + w_i] = \max(\text{dp}[j + 1][w + w_i], \text{dp}[j][w] + b_i)\)$

Computing the Answer: After processing all panels, find the maximum value of dp[j][w] among all \((j, w)\) satisfying: - \(0 \le j \le N\) - \(\max(0, L - (j + 1) \times (K - 1)) \le w \le L\)

If no state satisfying the conditions exists (i.e., the maximum remains at the initial value -1), output -1.

---

Complexity

Time Complexity: \(O(N^2 L)\)

• The outer loop processes the \(N\) panels sequentially.
• The inner loops iterate over the number of selected panels \(j\) (at most \(N\)) and the current width \(w\) (at most \(L\)).
• Therefore, the total number of transitions is at most \(N \times N \times L = N^2 L\).
• In this implementation, we maintain total_w, the maximum possible sum of widths of panels seen so far, and skip unnecessary iterations over \(w\), significantly improving the constant factor.
• Under the constraints \(N \le 400\), \(L \le 1000\), we have \(N^2 L \approx 1.6 \times 10^8\), but with the above optimization, this comfortably fits within the time limit.

Space Complexity: \(O(N L)\)

• The DP table has size \((N + 1) \times (L + 1)\).
• With \(N \le 400\), \(L \le 1000\), memory usage is very small. The space complexity is \(O(N L)\), safely within both time and memory limits.

---

Implementation Notes

• Memory savings via in-place DP: When updating the DP table, iterating over the count \(j\) in reverse order (for j in range(i, -1, -1)) ensures that old data from before the transition is not overwritten, allowing correct transitions using only a single 2D array.

• Pruning (speedup): A variable total_w is maintained, holding the cumulative sum of widths of panels encountered so far. This eliminates wasteful transition attempts for impossibly large values of \(w\), dramatically improving execution speed.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    L = int(data[1])
    K = int(data[2])

    panels = []
    idx = 3
    for _ in range(N):
        panels.append((int(data[idx]), int(data[idx + 1])))
        idx += 2

    # dp[j][w] : j枚選んで幅wのときの最大価値
    dp = [[-1] * (L + 1) for _ in range(N + 1)]
    dp[0][0] = 0

    total_w = 0
    for i in range(N):
        wi, bi = panels[i]
        limit = min(L - wi, total_w)
        for j in range(i, -1, -1):
            dp_prev = dp[j]
            dp_curr = dp[j + 1]
            for w in range(limit + 1):
                val = dp_prev[w]
                if val != -1:
                    new_val = val + bi
                    if new_val > dp_curr[w + wi]:
                        dp_curr[w + wi] = new_val
        total_w = min(L, total_w + wi)

    ans = -1
    for j in range(N + 1):
        dp_j = dp[j]
        # w の下限条件: (j + 1) * (K - 1) >= L - w  =>  w >= L - (j + 1) * (K - 1)
        min_w = L - (j + 1) * (K - 1)
        if min_w < 0:
            min_w = 0
        for w in range(min_w, L + 1):
            if dp_j[w] > ans:
                ans = dp_j[w]

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.