Overview

This is a problem where you visit \(N\) rooms in order and maximize the total reward by accepting jobs to either “load” or “unload” luggage. However, you must satisfy the conditions that “you can carry at most \(K\) items at a time” and “you must end with exactly \(0\) items.”

Analysis

In this problem, your next action is determined by the current “room number” and “number of items you are carrying,” so it can be solved using dynamic programming (DP).

1. State Definition

We define the state at the time of visiting each room as follows: - dp[i][j]: The maximum reward when you have visited up to room \(i\) and are carrying \(j\) items.

2. Transition Rules

Depending on the job type \(T_i\) and reward \(A_i\) at room \(i\), the transitions are as follows:

Loading job (\(T_i = 1\))

• Accept: The number of items increases from \(j-1\) to \(j\). dp[i][j] = dp[i-1][j-1] + A_i
• Decline: The number of items remains \(j\). dp[i][j] = dp[i-1][j]
• Combining these: dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + A_i).

Unloading job (\(T_i = 0\))

• Accept:
  • If you originally have \(j+1\) items, you unload one to have \(j\) items.
  • If you originally have \(0\) items, unloading still leaves you with \(0\) items (only when \(j=0\)). dp[i][j] = dp[i-1][j+1] + A_i (When \(j=0\): dp[i][0] = max(dp[i-1][0] + A_i, dp[i-1][1] + A_i))
• Decline: The number of items remains \(j\). dp[i][j] = dp[i-1][j]
• Combining these: dp[i][j] = max(dp[i-1][j], dp[i-1][j+1] + A_i).

3. Narrowing the Range by Constraints

• Upper limit on items: We always need \(0 \leq j \leq K\).
• Final condition: Since we must end with \(0\) items, if at room \(i\) you are carrying more items than the number of remaining rooms \((N-i)\), it is impossible to return to \(0\) items no matter what. In other words, we always need \(j \leq N-i\).

Algorithm

We prepare a 1-dimensional array dp[j] and update it sequentially from room \(1\) to \(N\).

1. Initialization: Set dp[0] = 0 and all other values to a very small value (\(-\infty\)).
2. For each room \(i\):
   • Compute the maximum number of items you can carry at the current room: M_curr = min(K, i, N - i).
   • When \(T_i = 1\):
     • Loop j from M_curr down to \(1\) in reverse order, updating dp[j] = max(dp[j], dp[j-1] + A_i).
   • When \(T_i = 0\):
     • Loop j from \(0\) to M_curr, updating dp[j] = max(dp[j], dp[j+1] + A_i).
3. Answer: The final value of dp[0] is the answer.

※ The reason for looping in reverse order when \(T_i = 1\) is to prevent accepting the same room’s job multiple times in a single update (i.e., items cascading as \(j-1 \to j \to j+1\)).

Complexity

• Time complexity: \(O(NK)\)
  • For each of the \(N\) rooms, we loop over up to \(K\) item counts.
  • Since \(NK \leq 10^7\) by the constraints, this fits within the time limit even in Python if implemented efficiently.
• Space complexity: \(O(K)\)
  • Since we only maintain a 1-dimensional DP table, memory usage is very low.

Implementation Notes

• Fast I/O: Since \(N\) and \(K\) can be large, reading all input at once using sys.stdin.read().split() or similar methods is faster.

• Unreachable states: Set the initial values of dp to a sufficiently small value like \(-10^{18}\), and be careful that negative infinity is not offset by rewards during computation.

• Range optimization: By resetting states where \(N - i < j\) to -INF, we correctly exclude routes that cannot end with \(0\) items.

  Source Code

import sys

def solve():
    # Fast I/O: Read all input at once and split into strings
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Parse N and K from the first two elements
    N = int(input_data[0])
    K = int(input_data[1])
    
    # dp[j] stores the maximum reward with exactly j packages.
    # Initialize with a very small number to represent unreachable states.
    INF = 10**18
    dp = [-INF] * (K + 1)
    dp[0] = 0
    
    # M_prev tracks the maximum possible number of packages in the previous step.
    M_prev = 0
    
    # Iterate through each room
    idx = 2
    for i in range(1, N + 1):
        T = int(input_data[idx])
        A = int(input_data[idx+1])
        idx += 2
        
        # M_curr is the maximum number of packages possible at step i.
        # It is constrained by K, the current step i, and the remaining steps N-i.
        M_curr = i
        if K < M_curr: M_curr = K
        if N - i < M_curr: M_curr = N - i
        
        if T == 1:
            # Load a package: dp[j] = max(dp[j], dp[j-1] + A)
            # We iterate backwards to use the values from the previous state (i-1).
            for j in range(M_curr, 0, -1):
                # j-1 is guaranteed to be <= M_prev because M_curr <= M_prev + 1.
                prev_val = dp[j-1]
                if prev_val > -INF // 2:
                    v = prev_val + A
                    if v > dp[j]:
                        dp[j] = v
        else:
            # Unload a package:
            # If j > 0, accept T=0 to go from j packages to j-1 packages.
            # If j = 0, accept T=0 to stay at 0 packages.
            
            # Update state for 0 packages:
            # new_dp[0] = max(dp[0] + A, dp[1] + A, dp[0])
            # Since A >= 1, this simplifies to max(dp[0], dp[1]) + A.
            v0 = dp[0]
            if M_prev >= 1:
                v1 = dp[1]
                if v1 > v0:
                    v0 = v1
            
            if v0 > -INF // 2:
                dp[0] = v0 + A
            
            # Update state for j > 0 packages:
            # new_dp[j] = max(dp[j], dp[j+1] + A)
            for j in range(1, M_curr + 1):
                if j + 1 <= M_prev:
                    v_next = dp[j+1]
                    if v_next > -INF // 2:
                        v = v_next + A
                        if v > dp[j]:
                            dp[j] = v
        
        # Clean up: Any state j > M_curr is now impossible due to N-i constraint.
        # Since M_curr decreases by at most 1, we only need to reset the previous boundary.
        if M_prev > M_curr:
            dp[M_prev] = -INF
            
        M_prev = M_curr
        
    # The answer is the maximum reward with 0 packages remaining at the end.
    # Because declining all jobs is always an option, the result is at least 0.
    print(max(0, dp[0]))

if __name__ == '__main__':
    solve()

---

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