Hints: Roadworks
Solve G0 first. There every road is open on day $1$, and an optimal plan is: walk monotonically from $x$, then camp at one house $c$.
The full problem only changes when each road exists.
Answer to Hint 1: In G0 the answer is
$$ \max_c \bigl( (k - T[c] + 1)\, h_c + \text{walk}(x,c) \bigr), $$where $T[c]$ is the earliest day you can collect at $c$. See the G0 hints for how to compute $T$ and $\text{walk}$.
Answer to Hint 2: For general $d_i$, build $T[i]$ with two sweeps from $x$:
- to the right: $T[i+1] = \max(T[i]+1, d_i)$, but $T[x+1]=1$ if $d_x=1$;
- to the left: $T[i] = \max(T[i+1]+1, d_i)$, but $T[x-1]=1$ if $d_{x-1}=1$.
Answer to Hint 3: The G0 camp formula is still a valid strategy in G: you may always take $\max\limits_c \text{score}(c)$ as one candidate for the answer.
It is not always optimal when a better peak opens only after you have waited at a smaller one.
Answer to Hint 5: Sort houses by $T[i]$. Let $\mathrm{dp}[i]$ = best total just before collecting at $i$ on day $T[i]$, with $\mathrm{dp}[i]=0$ initially.
Always relax camp at $i$:
$$ \text{ans} \leftarrow \max(\text{ans},\ \mathrm{dp}[i] + (k - T[i] + 1)\, h_i). $$Answer to Hint 6: To hop from $i$ to a higher $j$, you need $|j-i| \le T[j]-T[i]$ (enough days between first collections).
Otherwise skip that edge.
Answer to Hint 7: If the hop is feasible, profit is
$$ \mathrm{dp}[i] + \bigl(T[j]-T[i]-|j-i|+1\bigr)\, h_i + \sum_{\text{houses strictly between } i,j} h. $$Use prefix sums for the between-houses sum (endpoints excluded).
Answer to Hint 8: Try only $j$ = nearest higher to the left and nearest higher to the right of $i$. Update $\mathrm{dp}[j]$ with the formula above.
The final answer is the maximum ans from all camping relaxations.
model_sol.cpp is the camp view; quadratic_dp.cpp here is the peak view for general $d_i$.