Overview

This problem asks you to visit \(N\) rooms in order, selectively accepting loading/unloading tasks to maximize your reward. The number of items you carry must always be at most \(K\) and must be \(0\) at the end. We solve this with DP.

Analysis

State Definition

When processing rooms from left to right, the only information that affects future choices is “how many items are you currently carrying?” So we define the following DP:

\[dp[j] = \text{the maximum total reward so far when currently carrying } j \text{ items}\]

The initial state is \(dp[0] = 0\), and all others are \(-\infty\) (unreachable).

Transition Logic

At each room, there are two choices: “accept” or “decline” the task. If you decline, \(dp[j]\) remains unchanged. If you accept, the transition depends on the type of task.

Loading task (\(T_i = 1\)): - Accepting from a state with \(j-1\) items results in \(j\) items - \(dp[j] \leftarrow \max(dp[j],\ dp[j-1] + A_i)\) (\(j = 1, 2, \ldots, K\)) - Similar to the 0-1 knapsack, we process \(j\) in reverse order from \(K\) down to \(1\) to prevent applying the same task multiple times

Unloading task (\(T_i = 0\)): - Accepting from a state with \(j+1\) items results in \(j\) items (\(j \geq 1\)) - Even with \(0\) items, you can accept the task — items stay at \(0\) and you just receive the reward - For \(j = 0\): \(dp[0] \leftarrow \max(dp[0],\ dp[1]) + A_i\) - For \(j \geq 1\): \(dp[j] \leftarrow \max(dp[j],\ dp[j+1] + A_i)\) - Since the transition is \(j+1 \to j\) (large → small), we process \(j\) in ascending order from \(0\) to \(K-1\)

Concrete Example

For \(N=3, K=2\), with tasks \((1,5), (1,3), (0,4)\):

After processing	\(dp[0]\)	\(dp[1]\)	\(dp[2]\)
Initial	0	\(-\infty\)	\(-\infty\)
Room 1 (load, 5)	0	5	\(-\infty\)
Room 2 (load, 3)	0	5	8
Room 3 (unload, 4)	9	12	8

The answer is \(dp[0] = 9\) (accept rooms 1 and 3).

Algorithm

1. Initialize \(dp[0] = 0\), \(dp[1], \ldots, dp[K] = -\infty\)
2. For each room \(i = 1, 2, \ldots, N\):
   • \(T_i = 1\) (load): For \(j = K, K-1, \ldots, 1\) in that order, \(dp[j] \leftarrow \max(dp[j],\ dp[j-1] + A_i)\)
   • \(T_i = 0\) (unload):
     • \(j = 0\): \(dp[0] \leftarrow \max(dp[0], dp[1]) + A_i\) (if \(dp[0]\) is valid)
     • \(j = 1, 2, \ldots, K-1\): \(dp[j] \leftarrow \max(dp[j],\ dp[j+1] + A_i)\)
3. The answer is \(\max(dp[0],\ 0)\)

Complexity

• Time complexity: \(O(NK)\) (scanning item states \(0 \sim K\) for each room)
• Space complexity: \(O(K)\) (size of the DP array)

Under the constraint \(NK \leq 10^7\), this runs sufficiently fast.

Implementation Notes

• The direction of the loop is crucial. For loading tasks, scan in reverse order (large → small); for unloading tasks, scan in ascending order (small → large). Otherwise, a single task may trigger multiple transitions, causing a bug. This is the same idea as in the 0-1 knapsack problem.

• When \(T_i = 0\) and \(j = 0\), don’t forget to handle the special case where you can accept the task even with no items (receiving only the reward). Transitions from both \(dp[0]\) and \(dp[1]\) are possible.

• For \(dp[K]\) during an unloading task, there is no transition from \(dp[K+1]\), so the loop range \(j = 1, \ldots, K-1\) is sufficient.

• Since not accepting any task (reward \(0\)) is also valid, output \(\max(dp[0], 0)\) at the end.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    NEG_INF = -(1 << 60)
    dp = [NEG_INF] * (K + 2)  # dp[0..K], extra slot K+1 for convenience
    dp[0] = 0
    
    for i in range(N):
        t = int(data[idx]); idx += 1
        a = int(data[idx]); idx += 1
        
        if t == 1:
            # Pick up cargo: from state j-1 to j
            # Iterate j from K down to 1
            for j in range(K, 0, -1):
                val = dp[j - 1] + a
                if val > dp[j]:
                    dp[j] = val
        else:
            # Drop cargo: from state j+1 to j (j>=1), or from state 0 to 0
            # For j=0: new = max(dp[0], dp[0]+a, dp[1]+a)
            # Since a>=1, dp[0]+a > dp[0] when dp[0] is valid
            # For j>=1: new = max(dp[j], dp[j+1]+a)
            
            # j=0 special case
            candidate0 = dp[0]
            candidate1 = dp[1] if K >= 1 else NEG_INF
            best = candidate0 if candidate0 > candidate1 else candidate1
            if best != NEG_INF:
                val = best + a
                if val > dp[0]:
                    dp[0] = val
            
            # j=1..K-1: accept from j+1
            for j in range(1, K):
                val = dp[j + 1] + a
                if val > dp[j]:
                    dp[j] = val
    
    ans = dp[0] if dp[0] > 0 else 0
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.