Doors and Keys

The main trap is thinking the one-key carrying limit makes the state tiny. Nope. You can only carry one key at a time, but you can pile many keys in a room, so the real cost is the walking needed to shuttle that pile forward.

Process doors from left to right. Before door $i$, suppose we are in room $i$. Define $f[j]$ as the minimum time when we can be in room $i$ with exactly $j$ spare keys intentionally available at this frontier for future use. A key may be lying in the room or currently carried; we do not need to distinguish those, because the next movement cost is the same.

If $s_i=1$, room $i$ has a new key. We may ignore it, or add it to the frontier pile for free:

$$f[j+1] = \min(f[j+1], f[j]).$$

Now handle door $i$.

First, if we wait until the door opens automatically, then we can cross no earlier than time $\max(f[j], a_i)$. If we want to preserve all $j$ spare keys on the right side, the crossing/shuttling cost is:

$$c(j)=\begin{cases}1,&j=0,\\2j-1,&j>0.\end{cases}$$

So:

$$g[j] = \min(g[j], \max(f[j], a_i)+c(j)).$$

Second, if $j>0$, we can spend one key to open the door immediately. The first key is consumed while crossing, and the other $j-1$ keys must be shuttled over if we want them available for later. This still costs $2j-1$ seconds total:

$$g[j-1] = \min(g[j-1], f[j]+2j-1).$$

Why is $2j-1$ correct? For an open door and $j>0$, carry one key right in $1$ second. For each of the remaining $j-1$ keys, go left and come back right, costing $2$ more seconds each. Total $1+2(j-1)=2j-1$. For a closed door opened by a key, the first carried key is consumed, but the timing is identical.

After processing door $i$, the answer for room $i+1$ is $g[0]$. Positive key counts mean we spent extra time hauling keys for later doors. For the current target alone, unused future keys are dead weight; leaving them behind can only help. The DP still keeps all $g[j]$ because later answers are independent and may need those slower-but-better-stocked states.

Now the important optimization: we do not keep all possible $j$. Let

$$M = \max_i a_i + n.$$

A dumb but valid strategy is to wait in room $1$ until all doors have opened, then walk right, so every answer is at most $M$.

Also, any state that transports $j$ spare keys across the frontier has time at least $j^2$. This follows by induction: before using a room's fresh key, having $j$ keys means at least roughly $(j-1)^2$ time has already been paid, and moving those $j$ keys across the next door adds $2j-1$, giving $j^2$. So if $j^2>M$, that state can never improve an answer; the wait-and-walk strategy already beats it. Carrying that many keys is just cardio with extra steps.

Therefore keep only $L=\lfloor\sqrt M\rfloor+O(1)$ states. Since $a_i,n\le 2\cdot 10^5$, this is under about $640$ states per door.

Edge cases are naturally handled: with no keys only the automatic-opening transition works; if $a_i=0$, crossing can happen during second $0$ and arrival time is $1$; if a key is in the current room, adding it costs no time.

The complexity is $O(nL)$ per test case, where $L=O(\sqrt{\max a+n})$, and the memory usage is $O(L)$.