Editorial: G0. Roadworks (all roads ready)

Houses $1, \ldots, n$ lie in a row; every adjacent pair is connected from day $1$. You start at house $x$. Each day you may move to a neighbor or stay, then add $h_j$ for your current house $j$. Maximize total satisfaction after $k$ days.

This is G. Roadworks with every road-opening day $d_i = 1$.

Let $\mathrm{dp}[s][i]$ be the best total after day $s$ while at house $i$:

That is $O(nk)$ — impossible for $k \le 10^9$.

We need to describe an optimal plan without iterating every day.

Two structural facts (you can justify by exchange arguments on small counterexamples):

1. Monotone movement. You never go left and later go right (or the reverse). An optimal plan only moves left, only moves right, or never leaves $x$.

2. Single camp. You never spend two or more consecutive days at a house and then walk farther away. All multi-day “farming” happens at one final house $c$.

So an optimal strategy is:

1. Walk monotonically from $x$ toward some house $c$ (at most one day’s collection per house along the way).
2. Camp at $c$ for every remaining day.

The entire problem reduces to choosing the camp house $c$.

Let $T[i]$ be the earliest day $s$ such that you can collect $h_i$ on day $s$ (after the move on that day).

With all roads open on day $1$, using 0-indexed start $x$:

Example ($n = 5$, 1-based start $3$, index $x = 2$): $T = [2, 1, 1, 1, 2]$.

Pitfall: $T[i] = 1 + |i - x|$ is wrong (it gives $T[x \pm 1] = 2$). Neighbors must be $1$.

If $T[c] > k$, house $c$ is unreachable — skip it.

Split earnings into two parts.

You move monotonically along the segment between $x$ and $c$. Each interior house on that segment contributes its $h$ once (the day you step through). The endpoints $x$ and $c$ are not included in this middle sum:

• $x$ is handled by the start (if $c = x$, there is no walk at all).
• $c$ is counted in the camping term below.

With prefix sums $\mathrm{pref}$ on $h$ (0-indexed, $\mathrm{pref}[i] = \sum_{t=0}^{i} h_t$):

You first collect at $c$ on day $T[c]$, then can stay through day $k$. That is $k - T[c] + 1$ collections at $h_c$:

Answer: $\max\limits_{c \,:\, T[c] \le k} \text{score}(c)$.

Input: $n = 5$, $k = 10$, $x = 3$ (1-based), $h = [14, 2, 3, 5, 6]$.

0-indexed $x = 2$, $T = [2, 1, 1, 1, 2]$.

Best: camp at house $1$ (index $0$), total 128.

Interpretation: day $1$ move toward house $1$ and collect along the way; from day $2$ onward live at house $1$.

1. Build $T$ in $O(n)$.
2. Build prefix sums in $O(n)$.
3. For each $c = 0, \ldots, n - 1$ with $T[c] \le k$, compute $\text{score}(c)$ in $O(1)$.

Time: $O(n)$ per test case. Memory: $O(n)$.

The reference code in model_sol.cpp follows exactly this camp formulation.

G0 is special because every road exists on day $1$, so a single monotone walk plus one camp is always optimal.

In the full problem, road $i$ opens on day $d_i$. Then:

• $T[i]$ is computed from the $d_i$ schedule (two sweeps from $x$, same neighbor-day-$1$ exceptions when $d_i = 1$).
• You may need to collect at a lower peak before a higher peak becomes reachable later. That is no longer captured by one camp house.

The full solution keeps the camp formula as one way to finish, and adds a small DP over hops to strictly higher houses (see G editorial). For G0 alone, the camp formula is enough.

1. Using $1 + |i - x|$ instead of the neighbor rule for $T$.
2. Including endpoint houses in sum_between (double-counts $h_c$ or $h_x$).
3. Using $k - \mathrm{dist}$ instead of $k - T[c] + 1$ for camping days.
4. Forgetting long long when $k$ and $h$ are large.