Overview

This problem asks us to maximize the sum of “beauty” values of selected plots and “bonus beauty” obtained based on the length of consecutively selected plots (maximal contiguous intervals), subject to a budget constraint of \(W\). This is a Dynamic Programming (DP) problem that extends the classic “knapsack problem” with bonus conditions when adjacent elements are selected.

Analysis

1. Difference from the Simple Knapsack Problem

In the standard knapsack problem, the value obtained from each item is independent of whether you “select” or “don’t select” it. However, in this problem, “whether the previous plot was selected and how many consecutive plots have been selected” affects the bonus beauty gained when selecting a new plot.

2. Organizing the Bonus Conditions

When the length of a maximal contiguous interval is \(L\), the bonus obtained is as follows: - When \(L = 1\): \(0\) - When \(L = 2\): \(2 \times B\) - When \(L = 3\): \(3 \times B\) - When \(L \geq 2\): \(L \times B\)

How should we accumulate this bonus as we select plots one by one from left to right? Based on the previous state (the current consecutive length), we design the bonus addition method when newly selecting plot \(i\) as follows:

1. When the previous plot was not selected (current consecutive length is \(0\))
   • Selecting plot \(i\) makes the consecutive length \(1\).
   • No bonus is generated at this point, so the added value is only the beauty \(D_i\) of plot \(i\).
2. When the previous consecutive length is \(1\)
   • Selecting plot \(i\) makes the consecutive length \(2\).
   • Since the length becomes \(2\), a bonus of \(2 \times B\) is generated all at once, including the retroactive portion.
   • Therefore, the added value is \(D_i + 2 \times B\).
3. When the previous consecutive length is \(2\) or more
   • Selecting plot \(i\) increases the consecutive length by \(1\) (e.g., \(2 \to 3\)).
   • For each increase of \(1\) in length, an additional bonus of \(B\) is generated.
   • Therefore, the added value is \(D_i + B\).

With this reasoning, we can see that the “previous state” we need to remember is not the specific length, but just three states: “\(0\) (not selected)”, “\(1\) (length \(1\))”, and “\(2\) (length \(2\) or more)” are sufficient.

Algorithm

We solve this using Dynamic Programming (DP).

DP Table Definition

• dp[w][s] := The maximum beauty (including bonuses) when the total cost of plots selected so far is \(w\) and the consecutive state of the last plot is \(s\).

Here, state \(s\) takes the following three values: - \(s = 0\): The previous plot was not selected (current consecutive length is \(0\)) - \(s = 1\): Current consecutive length is \(1\) - \(s = 2\): Current consecutive length is \(2\) or more

Initial State

• dp[0][0] = 0
• All other dp[w][s] are \(-\infty\) (representing unreachable states)

Transitions

For plot \(i\) (\(0 \leq i < N\)), we consider transitions from the current DP table to the next DP table next_dp. For each \(w\) (\(0 \leq w \leq W\)), we perform the following transitions:

1. Transitions from \(s = 0\)

• Not selecting plot \(i\):
  • The state remains \(s = 0\). Neither cost nor beauty increases.
  • next_dp[w][0] = max(next_dp[w][0], dp[w][0])
• Selecting plot \(i\) (when \(w + C_i \leq W\)):
  • The state becomes \(s = 1\), and beauty \(D_i\) is obtained (bonus is \(0\)).
  • next_dp[w + C_i][1] = max(next_dp[w + C_i][1], dp[w][0] + D_i)

2. Transitions from \(s = 1\)

• Not selecting plot \(i\):
  • The consecutive sequence is broken, so the state returns to \(s = 0\).
  • next_dp[w][0] = max(next_dp[w][0], dp[w][1])
• Selecting plot \(i\) (when \(w + C_i \leq W\)):
  • The consecutive length becomes \(2\), so the state becomes \(s = 2\), and beauty \(D_i\) and bonus \(2 \times B\) are obtained.
  • next_dp[w + C_i][2] = max(next_dp[w + C_i][2], dp[w][1] + D_i + 2 * B)

3. Transitions from \(s = 2\)

• Not selecting plot \(i\):
  • The consecutive sequence is broken, so the state returns to \(s = 0\).
  • next_dp[w][0] = max(next_dp[w][0], dp[w][2])
• Selecting plot \(i\) (when \(w + C_i \leq W\)):
  • The consecutive length remains \(2\) or more and extends by \(1\) more, so the state stays at \(s = 2\), and beauty \(D_i\) and additional bonus \(B\) are obtained.
  • next_dp[w + C_i][2] = max(next_dp[w + C_i][2], dp[w][2] + D_i + B)

After completing transitions for all plots, the maximum value among all dp[w][s] is the answer.

Complexity

• Time Complexity: \(O(N \times W)\) For \(N\) plots, we iterate over budget \(W\) and \(3\) states, so the overall complexity is \(O(3 \times N \times W) = O(NW)\). Given the constraints \(N \leq 2000\), \(W \leq 20000\), the total number of operations is approximately \(1.2 \times 10^8\), which comfortably fits within the time limit.

• Space Complexity: \(O(W)\) The DP table only needs information from the previous step (up to plot \(i-1\)) to compute the next step. Therefore, by preparing two arrays of size \(O(W)\) (dp and next_dp) and alternating between them (swapping), we can reduce the space complexity to \(O(W)\).

Implementation Notes

• Initialization caution: Since we are finding the maximum beauty, initial values must be initialized with a sufficiently small value (\(-\infty\)). In C++, it is safe to define a sufficiently large value like 1e18 as INF and initialize with -INF.

• Memory optimization: By maintaining only two rows—the current row and the next row—like vector<vector<long long>> dp(W + 1, vector<long long>(3, -INF)), we can dramatically reduce space complexity and also improve cache efficiency.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, W;
    long long B;
    if (!(cin >> N >> W >> B)) return 0;

    vector<long long> D(N);
    vector<int> C(N);
    for (int i = 0; i < N; ++i) {
        cin >> D[i] >> C[i];
    }

    // dp[w][s]
    // s = 0: current segment length is 0 (last item not chosen)
    // s = 1: current segment length is 1
    // s = 2: current segment length is >= 2
    vector<vector<long long>> dp(W + 1, vector<long long>(3, -INF));
    vector<vector<long long>> next_dp(W + 1, vector<long long>(3, -INF));
    dp[0][0] = 0;

    for (int i = 0; i < N; ++i) {
        for (int w = 0; w <= W; ++w) {
            next_dp[w][0] = -INF;
            next_dp[w][1] = -INF;
            next_dp[w][2] = -INF;
        }

        long long cur_D = D[i];
        int cur_C = C[i];

        for (int w = 0; w <= W; ++w) {
            // Transition from s = 0
            if (dp[w][0] != -INF) {
                // Option 1: Do not choose flowerbed i
                if (dp[w][0] > next_dp[w][0]) {
                    next_dp[w][0] = dp[w][0];
                }
                // Option 2: Choose flowerbed i
                if (w + cur_C <= W) {
                    long long val = dp[w][0] + cur_D;
                    if (val > next_dp[w + cur_C][1]) {
                        next_dp[w + cur_C][1] = val;
                    }
                }
            }
            // Transition from s = 1
            if (dp[w][1] != -INF) {
                // Option 1: Do not choose flowerbed i
                if (dp[w][1] > next_dp[w][0]) {
                    next_dp[w][0] = dp[w][1];
                }
                // Option 2: Choose flowerbed i
                if (w + cur_C <= W) {
                    long long val = dp[w][1] + cur_D + 2 * B;
                    if (val > next_dp[w + cur_C][2]) {
                        next_dp[w + cur_C][2] = val;
                    }
                }
            }
            // Transition from s = 2
            if (dp[w][2] != -INF) {
                // Option 1: Do not choose flowerbed i
                if (dp[w][2] > next_dp[w][0]) {
                    next_dp[w][0] = dp[w][2];
                }
                // Option 2: Choose flowerbed i
                if (w + cur_C <= W) {
                    long long val = dp[w][2] + cur_D + B;
                    if (val > next_dp[w + cur_C][2]) {
                        next_dp[w + cur_C][2] = val;
                    }
                }
            }
        }
        dp.swap(next_dp);
    }

    long long ans = 0;
    for (int w = 0; w <= W; ++w) {
        for (int s = 0; s < 3; ++s) {
            ans = max(ans, dp[w][s]);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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