Hints: G0. Roadworks (all roads ready)
G0 is a path: each day you move to an adjacent house or stay, then gain $h_j$ at your current house. All roads exist from day $1$.
For small $k$, what does a day-by-day DP look like?
Answer to Hint 1: Let $\mathrm{dp}[s][i]$ be the best total after day $s$ while at house $i$. Each step uses only $i - 1$, $i$, $i + 1$.
That costs $O(nk)$ and is too slow for $k \le 10^9$.
Answer to Hint 2: On an optimal plan you never need to reverse direction: you only go left, only go right, or never leave the start (you may stay on a day).
So your walk is monotone along the line until you stop moving.
Answer to Hint 3: You also never need to camp (stay two or more days in a row) before your final house.
Optimal shape: walk toward some house $c$ (collecting at most once per house on the way), then camp at $c$ for all remaining days.
Answer to Hint 4: The whole problem becomes: choose a camp house $c$. Everything else is forced (shortest monotone walk from $x$ to $c$, then stay).
So you only need the best profit for each candidate $c$.
Answer to Hint 5: Define $T[i]$ = the earliest day you can collect at house $i$ (after that day’s move).
If $T[c] > k$, you can never reach $c$ in time — ignore it.
Answer to Hint 6: With every road open on day $1$ (0-indexed start $x$):
- $T[x] = 1$;
- $T[x - 1] = T[x + 1] = 1$ when those neighbors exist (step there on day $1$);
- farther left: $T[i] = T[i + 1] + 1$ for $i \le x - 2$;
- farther right: $T[i] = T[i - 1] + 1$ for $i \ge x + 2$.
Example $n = 5$, $x = 2$: $T = [2, 1, 1, 1, 2]$.
Answer to Hint 8: While walking from $x$ to $c$, you earn $h$ on each strictly between house once (endpoints are handled separately).
If $\mathrm{pref}$ is prefix sums of $h$, then
$$ \sum_{\text{strictly between } x \text{ and } c} h = \mathrm{pref}[\max(x,c) - 1] - \mathrm{pref}[\min(x,c)] $$(adjust indices to your 0-based $\mathrm{pref}$ layout).
Answer to Hint 9: After the first collection at $c$ on day $T[c]$, you can still collect on days $T[c], T[c] + 1, \ldots, k$. That is
$$ k - T[c] + 1 $$days at $h_c$.
Answer to Hint 10: Total profit if you camp at $c$:
$$ \underbrace{(k - T[c] + 1) \cdot h_c}_{\text{camp}} + \underbrace{\sum_{\text{strictly between } x,c} h}_{\text{walk}}. $$The answer is $\max\limits_c$ of this value over all $c$ with $T[c] \le k$.
Answer to Hint 11: Walkthrough ($n = 5$, $k = 10$, $x = 3$ in 1-based, $h = [14,2,3,5,6]$).
$T = [2,1,1,1,2]$. Best $c = 0$: walk contributes $h_2 = 2$ (only house strictly between $0$ and $2$), camp $14 \times 9 = 126$, total $128$.
The full G problem uses the same $T[i]$ idea from road days $d_i$, and may need extra transitions between peaks when roads open slowly.