Overview

We want to select some jobs to maximize the total reward, but each time we select both of two consecutively numbered jobs, we incur a penalty of \(K\) yen. The problem is to choose jobs that maximize the total profit.

Key Insight

The crucial observation is that penalties only depend on the relationship between adjacent numbers (\(i\) and \(i+1\)). In other words, the impact of whether we select job \(i\) is essentially determined only by whether we selected the immediately preceding job \(i-1\) (all earlier choices can be summarized by the state of the previous job).

A brute-force approach of “trying all subsets” would require \(2^N\) possibilities, which is far too slow for \(N \le 2 \times 10^5\). Instead, we use dynamic programming (DP) to update “the optimal value up to the current position.”

Organizing the conditions under which penalties occur:

• A penalty of \(K\) is deducted only when job \(i\) is selected and job \(i-1\) is also selected
• Otherwise (if either one is not selected), no penalty occurs

The key idea behind the DP is that it suffices to remember only “whether the previous job was also selected.”

Algorithm

We use a DP with 2 states \(dp0, dp1\) (think of the index \(i\) as the “current position”).

• \(dp0\): the maximum profit among all jobs considered so far, when the last (most recent) job is NOT selected
• \(dp1\): the maximum profit among all jobs considered so far, when the last (most recent) job IS selected

The transitions when processing job \(i\) (with reward \(A_i\)) are as follows.

1) New \(dp0\) (do not select job \(i\))

If we don’t select job \(i\), it doesn’t matter whether the previous job was selected or not — we simply take the maximum: - \(new0 = \max(dp0, dp1)\)

2) New \(dp1\) (select job \(i\))

If we select job \(i\), we split into cases based on the previous state.

• Transitioning from “previous not selected” (\(dp0\)): no penalty Profit is \(dp0 + A_i\)
• Transitioning from “previous also selected” (\(dp1\)): one more adjacent pair, so penalty \(K\) applies Profit is \(dp1 + A_i - K\)

Therefore, - \(new1 = \max(dp0 + A_i,\; dp1 + A_i - K)\)

We update from \(i=1\) onward, and the answer is \(\max(dp0, dp1)\) at the end.

Small Example

When \(A=[5,4,3],\; K=2\):

• Select job 1 (5): profit 5
• Also select job 2 (4), which is adjacent, so \(-2\): profit \(5+4-2=7\)
• Also select job 3 (3), which is again adjacent, so \(-2\): profit \(7+3-2=8\)

The DP can process this “subtract \(K\) when selecting consecutively” incrementally like this.

Complexity

• Time complexity: \(O(N)\) (a constant number of updates per job)
• Space complexity: \(O(1)\) (only two variables \(dp0, dp1\))

Implementation Notes

• By not maintaining a DP array and only updating \(dp0, dp1\), we save memory.

• Initialization is:

  • \(dp0=0\) (nothing selected yet)
  • \(dp1=A_1\) (select the first job)

• The problem requires “selecting at least one job,” but since \(A_i \ge 1\), the final \(\max(dp0,dp1)\) is always positive, so the empty set (0) can never be optimal (thus no special handling is needed).

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    K = next(it)
    A = [next(it) for _ in range(N)]

    dp0 = 0          # i not selected
    dp1 = A[0]       # i selected

    for i in range(1, N):
        ai = A[i]
        new0 = dp0 if dp0 > dp1 else dp1
        new1 = dp0 + ai
        cand = dp1 + ai - K
        if cand > new1:
            new1 = cand
        dp0, dp1 = new0, new1

    ans = dp0 if dp0 > dp1 else dp1
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.