Overview

This problem asks you to select one or more jobs from \(N\) jobs and maximize profit (total reward − total penalty), where selecting both jobs with consecutive numbers incurs a penalty of \(K\).

Analysis

Key Insight

In this problem, the decision of whether to accept job \(i\) depends only on whether you accepted the previous job \(i-1\). This is because penalties only occur for “pairs of consecutive numbers.”

Problem with Naive Approach

Enumerating all ways to select jobs gives \(2^N\) possibilities, which is far too slow for \(N \leq 2 \times 10^5\) (TLE).

Solution

We use Dynamic Programming (DP). By managing two states for each job—”accept/don’t accept”—and computing the current state from the previous job’s state, we can solve this efficiently.

Algorithm

State Definition

When considering up to job \(i\), we manage the following three states:

• prev_not_take_none: Maximum profit when not selecting job \(i\) and having selected no jobs yet
• prev_not_take_some: Maximum profit when not selecting job \(i\) and having selected one or more jobs
• prev_take: Maximum profit when selecting job \(i\) (necessarily having selected at least one job)

Transitions

For job \(i\):

When not accepting job \(i\): - curr_not_take_none = prev_not_take_none (maintain the state of having selected nothing) - curr_not_take_some = max(prev_not_take_some, prev_take) (inherit the state of having selected something before)

When accepting job \(i\): - curr_take = max(prev_not_take_none + A[i], prev_not_take_some + A[i], prev_take + A[i] - K) - If the previous job was not selected: gain \(A_i\) without penalty - If the previous job was selected: gain \(A_i\) while paying penalty \(K\)

Concrete Example

For \(N=3, K=5, A=[10, 3, 8]\):

Job	not_take_none	not_take_some	take
Initial	0	\(-\infty\)	10
i=1	0	10	max(0+3, \(-\infty\)+3, 10+3-5) = 8
i=2	0	10	max(0+8, 10+8, 8+8-5) = 18

Answer: \(\max(10, 18) = 18\) (selecting jobs 1 and 3)

Complexity

• Time complexity: \(O(N)\) (constant time processing for each job)
• Space complexity: \(O(1)\) (only storing the previous three state values)

Implementation Notes

1. Handling the “select at least one” constraint: A simple DP would include the state of selecting nothing, so we need to separately manage “the state of having selected nothing yet” and “the state of having selected one or more.”

2. Setting initial values: By setting the initial value of prev_not_take_some to \(-\infty\), we express that initially the state “having selected one or more but not selecting the current job” does not exist.

3. Space optimization: Instead of maintaining the entire array, we manage only the previous state with variables, keeping space complexity at \(O(1)\).

Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # dp[i][j] = maximum profit when considering up to job i
    # j = 0: do not accept job i
    # j = 1: accept job i
    
    # Initial state: start from selecting nothing
    # However, we ultimately need to select at least one
    
    INF = float('inf')
    
    # dp[0]: maximum profit when not accepting job i
    # dp[1]: maximum profit when accepting job i
    
    # Initially nothing is selected
    # prev_not_take: maximum profit when previous job was not accepted
    # prev_take: maximum profit when previous job was accepted
    
    prev_not_take = 0  # nothing selected
    prev_take = A[0]   # select job 0
    
    for i in range(1, N):
        # When not accepting job i
        # Either previous state is fine
        curr_not_take = max(prev_not_take, prev_take)
        
        # When accepting job i
        # If previous job was not accepted: no additional cost
        # If previous job was accepted: additional cost K
        curr_take = max(prev_not_take + A[i], prev_take + A[i] - K)
        
        prev_not_take = curr_not_take
        prev_take = curr_take
    
    # We need to select at least one in the end
    # prev_take has at least one selected
    # prev_not_take might have 0 selected
    
    # Find maximum when at least one is selected
    # prev_take always has at least one selected
    # Need to consider cases where prev_not_take has at least one selected
    
    # Redo the DP
    # dp[i][j][k]: considered up to i-th, j=select job i or not, k=selected at least one or not
    
    # prev_not_take_none: did not select previous job, haven't selected anything yet
    # prev_not_take_some: did not select previous job, selected at least one
    # prev_take: selected previous job (necessarily selected at least one)
    
    prev_not_take_none = 0
    prev_not_take_some = -INF
    prev_take = A[0]
    
    for i in range(1, N):
        # When not accepting job i
        curr_not_take_none = prev_not_take_none
        curr_not_take_some = max(prev_not_take_some, prev_take)
        
        # When accepting job i
        curr_take = max(prev_not_take_none + A[i], prev_not_take_some + A[i], prev_take + A[i] - K)
        
        prev_not_take_none = curr_not_take_none
        prev_not_take_some = curr_not_take_some
        prev_take = curr_take
    
    # Maximum value among states with at least one selected
    ans = max(prev_not_take_some, prev_take)
    print(ans)

solve()

---

This editorial was generated by claude4.5opus.