Editorial: G. Roadworks

Read G0 editorial first. When every road opens on day $1$, an optimal plan is:

1. Walk monotonically from the start $x$ toward some house $c$.
2. Camp at $c$ for all remaining days.

The answer is a single maximum over camp sites $c$ using arrival times $T[i]$ and a prefix-sum “walk” term.

The full problem only changes when houses become reachable. Sometimes you must earn at a smaller peak before a larger one is available — then one camp is not enough. The fix is a short DP on top of the same $T[i]$.

Road $i$ (between houses $i$ and $i + 1$ in 1-based numbering) opens on day $d_i$. Each day: roads with $d_i = s$ open, then you move, then you collect.

Let $T[i]$ be the earliest day you can collect at house $i$ (0-indexed start $x$).

Right sweep ($i = x, x+1, \ldots, n-2$):

with the exception $T[x+1] = 1$ when $i = x$ and $d_x = 1$ (neighbor reachable on day $1$).

Left sweep ($i = x-1, x-2, \ldots, 0$):

with $T[x-1] = 1$ when $i = x-1$ and $d_{x-1} = 1$.

This is exactly G0 when all $d_i = 1$.

Even in the full problem, you may still walk once from $x$ and camp forever at some $c$. That is the G0 score:

where $\text{walk}(x,c)$ sums $h$ on houses strictly between $x$ and $c$ (see G0 editorial). Take the maximum over $c$ with $T[c] \le k$.

For G0 this is the answer. For G it is only one type of strategy.

Suppose a high house $j$ is unreachable until late, but a medium house $i$ on the way has decent $h_i$. You might:

• collect at $i$ for several days while waiting,
• then walk to $j$ when the roads allow,
• then camp at $j$.

That is two peaks in increasing hospitality, not a single camp from $x$.

On a line, any such chain only needs to jump to the next strictly higher house to the left or right — lower houses are never useful as intermediate peaks.

Process houses in increasing $T[i]$ (break ties by index).

$\mathrm{dp}[i]$ = best total just before you collect at $i$ on day $T[i]$.

• Initialize $\mathrm{dp}[i] = 0$ for all $i$ (in particular every house with $T[i] = 1$ can be reached on day $1$ with zero prior gain).

Camp at $i$ forever:

Hop to a higher peak $j$ ($h_j > h_i$), only if

While moving from $i$ toward $j$:

• $|j-i|$ days walk one step along the segment;
• the remaining $T[j] - T[i] - |j-i| + 1$ days you can stand on $i$ and collect $h_i$;
• each interior house pays once (prefix sum on the open interval between $i$ and $j$).

Only try $j$ = nearest index to the right with $h_j > h_i$, and nearest to the left with $h_j > h_i$ (find with simple loops — $O(n^2)$ total).

The final answer is the maximum $\text{ans}$ over all camping updates.

If $h_{j'} > h_i$ and $j'$ lies beyond a nearer higher $j$ on the same side, any route that reaches $j'$ must pass the region of $j$ first. Waiting at $i$ until $j$ is usable, then moving to $j$, dominates skipping $j$ when only strictly higher peaks matter.

• $T[i]$: $O(n)$.
• Nearest higher left/right by brute loops: $O(n^2)$.
• DP: $O(n)$ states, $O(1)$ transitions each.

Total: $O(n^2)$ per test case (fits the sum of $n \le 2 \cdot 10^5$ with a tight implementation, or use a stack later for $O(n)$).

problem-g0/model_sol.cpp is only the camp branch (Step 2). It is correct for G0.

problem-g/quadratic_dp.cpp adds Step 4’s peak hops with the same $T[i]$ and prefix sums. On G0 data both approaches agree.

1. Wrong left sweep: $T[i] = \max(T[i+1]+1, d_i)$ for $i$ decreasing from $x-1$.
2. Transition to every $j$ with $h_j > h_i$ — use only nearest higher on each side.
3. sum_between must exclude both endpoints.
4. Use 64-bit integers for products with large $k$ and $h$.