Overview

This problem asks us to select a set of plots from \(N\) plots arranged in a line within a budget \(W\), maximizing the total beauty of the selected plots plus a bonus for selecting contiguous plots (\(L \times B\) for a contiguous segment of length \(L \geq 2\)). It is a variant of the knapsack problem augmented with a “contiguous selection bonus” element.

Analysis

Key Insights

1. Difference from the standard knapsack problem: In addition to choosing each plot independently, a bonus is awarded for “choosing adjacent plots contiguously,” which requires tracking whether the previous plot was chosen or not.

2. Focusing on the incremental bonus: If we try to calculate the bonus \(L \times B\) all at once at the end based on the contiguous segment length \(L\), we would need to maintain the length of the contiguous segment in the DP state, causing a state explosion. However, if we look at the incremental gain of the bonus:

   • When extending from length \(1 \to 2\): The bonus goes from \(0 \to 2B\), so the increase is \(+2B\).
   • When extending from length \(L \to L+1\) (\(L \geq 2\)): The bonus goes from \(LB \to (L+1)B\), so the increase is \(+B\).

Thus, we do not need to remember the exact length of the contiguous segment; distinguishing between “length 1” and “length 2 or greater” is sufficient to correctly calculate the incremental gains.

1. Managing with 3 states: It is sufficient to classify the state of the previous plot into the following 3 states:
   • State 0: The previous plot was not chosen (or it is before the first plot).
   • State 1: The previous plot was chosen, and the current contiguous segment length is \(1\).
   • State 2: The previous plot was chosen, and the current contiguous segment length is \(2\) or greater.

Algorithm

\(dp[w][s]\) = Maximum total beauty when using cost \(w\), and the state of the previous plot is \(s\) (\(s \in \{0, 1, 2\}\)).

For each plot \(i\), we perform the following transitions:

Concrete Example: Choosing plots \(\{2, 3, 4\}\) (with \(B = 5\)) - Choose plot 2: State 0 → State 1, \(+D_2\) - Choose plot 3: State 1 → State 2, \(+D_3 + 2 \times 5 = D_3 + 10\) - Choose plot 4: State 2 → State 2, \(+D_4 + 5\)

Total bonus = \(10 + 5 = 15 = 3 \times 5\) ✓

The final answer is the maximum value across all states and costs after processing all plots.

Complexity

• Time Complexity: \(O(N \times W)\) (For each plot, we update each state for costs \(0 \sim W\) in constant time)
• Space Complexity: \(O(W)\) (Maintaining 3 arrays of length \(W+1\) for each state)

Implementation Details

• Separating into 3 arrays (dp0, dp1, dp2): Avoids indexing into a 2D array for speed optimization.

• Managing unreachable states with NEG_INF = -1: Since beauty values are always non-negative, \(-1\) can safely mark unreachable states.

• Checking w + ci <= W during transitions: Conditional branch to prevent exceeding the budget.

• Considering States 1 and 2 in the final answer: The contiguous segment might end at the last plot, so we take the maximum over all states.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    
    D = []
    C = []
    for i in range(N):
        d = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        D.append(d)
        C.append(c)
    
    # State: dp[i][w][s] where:
    # i = current item index (0..N-1)
    # w = weight used so far (0..W)
    # s = state regarding the last item:
    #   s=0: last item was NOT selected (or no item yet)
    #   s=1: last item WAS selected and is part of a run of length 1
    #   s=2: last item WAS selected and is part of a run of length >= 2
    #
    # When we don't select item i:
    #   If previous state was s=0: new state is 0, no change in value
    #   If previous state was s=1: run of length 1 ends, bonus = 0, new state = 0
    #   If previous state was s=2: run of length >= 2 ends, but bonus was already added incrementally, new state = 0
    #
    # When we select item i:
    #   If previous state was s=0: start new run of length 1, gain D[i], new state = 1
    #   If previous state was s=1: extend run from 1 to 2, gain D[i] + 2*B (because L goes from 1 to 2, bonus goes from 0 to 2B, delta = 2B), new state = 2
    #   If previous state was s=2: extend run from L>=2 to L+1, gain D[i] + B (bonus increases by B), new state = 2
    
    # dp[w][s] = max value achievable considering items 0..i-1 with weight w and state s
    
    NEG_INF = -1
    
    # Initialize: before processing any item, state is (w=0, s=0) with value 0
    # dp[w][s]: use flat arrays for speed
    # s=0,1,2
    
    dp0 = [NEG_INF] * (W + 1)  # state 0
    dp1 = [NEG_INF] * (W + 1)  # state 1
    dp2 = [NEG_INF] * (W + 1)  # state 2
    
    dp0[0] = 0
    
    for i in range(N):
        di = D[i]
        ci = C[i]
        
        new_dp0 = [NEG_INF] * (W + 1)
        new_dp1 = [NEG_INF] * (W + 1)
        new_dp2 = [NEG_INF] * (W + 1)
        
        for w in range(W + 1):
            # From state 0
            v0 = dp0[w]
            if v0 != NEG_INF:
                # Don't select i
                if v0 > new_dp0[w]:
                    new_dp0[w] = v0
                # Select i: new run of length 1
                if w + ci <= W:
                    val = v0 + di
                    if val > new_dp1[w + ci]:
                        new_dp1[w + ci] = val
            
            # From state 1
            v1 = dp1[w]
            if v1 != NEG_INF:
                # Don't select i: run of length 1 ends, bonus 0
                if v1 > new_dp0[w]:
                    new_dp0[w] = v1
                # Select i: extend run 1->2, gain D[i] + 2B
                if w + ci <= W:
                    val = v1 + di + 2 * B
                    if val > new_dp2[w + ci]:
                        new_dp2[w + ci] = val
            
            # From state 2
            v2 = dp2[w]
            if v2 != NEG_INF:
                # Don't select i: run of length >=2 ends
                if v2 > new_dp0[w]:
                    new_dp0[w] = v2
                # Select i: extend run, gain D[i] + B
                if w + ci <= W:
                    val = v2 + di + B
                    if val > new_dp2[w + ci]:
                        new_dp2[w + ci] = val
        
        dp0 = new_dp0
        dp1 = new_dp1
        dp2 = new_dp2
    
    ans = 0
    for w in range(W + 1):
        if dp0[w] > ans:
            ans = dp0[w]
        if dp1[w] > ans:
            ans = dp1[w]
        if dp2[w] > ans:
            ans = dp2[w]
    
    print(ans)

main()

This editorial was generated by claude4.6opus-thinking.