Treasure Hunt

Let $dp[i][0]$ be the maximum searched length after choosing directions for people $1$ through $i$, with person $i$ facing left. Let $dp[i][1]$ be the corresponding maximum when person $i$ faces right.

For convenience, set

$$A_0=B_0=0,\qquad A_{N+1}=L,\qquad B_{N+1}=0.$$

The initial values are $dp[0][0]=dp[0][1]=0$.

Suppose person $i$ faces left. If person $i-1$ also faces left, the newly covered length is $\min(A_i-A_{i-1},B_i)$.

If person $i-1$ faces right, person $i-1$ may already cover up to $B_{i-1}$ units of the gap between the two people. The uncovered part of that gap therefore has length $$, so person can newly cover

$$\min(B_i,\max(0,A_i-A_{i-1}-B_{i-1}))$$

units.

Thus,

$$dp[i][0]=\max\left( dp[i-1][0]+\min(A_i-A_{i-1},B_i), dp[i-1][1]+\min(B_i,\max(0,A_i-A_{i-1}-B_{i-1})) \right).$$

If person $i$ faces right, the newly searched interval does not overlap any previously searched interval by a positive length. Therefore,

$$dp[i][1]=\max(dp[i-1][0],dp[i-1][1])+\min(A_{i+1}-A_i,B_i).$$

The answer is $\max(dp[N][0],dp[N][1])$. Each transition takes constant time, so the time complexity is $O(N)$.

Solution written by GPT5.6