Overview

Select some jobs from \(N\) jobs, where a cost \(K\) is deducted for each pair of consecutively numbered jobs chosen, and find the maximum profit obtainable.

Analysis

In this problem, simply greedily selecting jobs with the highest rewards does not yield the optimal solution. This is because selecting consecutively numbered jobs incurs a penalty of \(K\), so to maximize profit, we need to consider not only “which jobs to select” but also “how much to minimize the penalty.”

For example, consider the following input:

N=3, K=5
A = [10, 8, 10]

If we select jobs 1 and 3, the reward is \(10 + 10 = 20\) with a penalty of \(0\), so the profit is \(20\). On the other hand, if we select all jobs, the reward is \(28\) but the penalty is \(2K = 10\), resulting in a profit of \(18\). As shown, greedy selection does not always lead to the optimal solution.

Therefore, we use dynamic programming (DP) to sequentially determine the optimal choices based on “whether to select or not select job \(i\) when considering up to job \(i\).”

Algorithm

We use dynamic programming (DP).

DP Table Definition

dp[i][0]: Maximum profit over the range from job \(1\) to \(i\) when job \(i\) is not selected dp[i][1]: Maximum profit over the same range when job \(i\) is selected

Transitions

For job \(i+1\), we perform the following transitions:

• When job \(i+1\) is not selected: dp[i+1][0] = max(dp[i][0], dp[i][1]) → Can transition from either previous state

• When job \(i+1\) is selected: dp[i+1][1] = max(dp[i][0] + A[i], dp[i][1] + A[i] - K) → If the previous job \(i\) was selected, subtract the penalty \(K\)

Initial conditions: - dp[0][0] = 0 (state where nothing is selected) - dp[0][1] = -∞ (invalid state)

Finally, max(dp[N][0], dp[N][1]) is the answer.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (However, by rolling the DP table with just 2 variables, the space complexity can be reduced to \(O(1)\))

Implementation Notes

• Be careful with DP indexing (whether it is 1-indexed or 0-indexed)

• Setting dp[0][1] to -inf in the initial state prevents invalid transitions

• sys.stdin.read is used for fast input reading

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # dp[i][0]: 仕事iを選ばないときの最大利益
    # dp[i][1]: 仕事iを選ぶときの最大利益
    dp = [[0]*2 for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = -float('inf')  # 無効な状態

    for i in range(N):
        # 仕事i+1を選ばない
        dp[i+1][0] = max(dp[i][0], dp[i][1])
        # 仕事i+1を選ぶ
        # 前の仕事を選んでいた場合は-Kのペナルティ
        dp[i+1][1] = max(dp[i][0] + A[i], dp[i][1] + A[i] - K)

    result = max(dp[N][0], dp[N][1])
    print(result)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.