771. Lighting the Weakest Town

n towns sit in a row, numbered 0 to n - 1. Town i already has s[i] generators. A generator in town j supplies power to every town within distance r of j, meaning every town x with |x - j| <= r. The POWER of a town is the number of generators supplying it.

You may build k more generators, each in any town you like, and any number of them may share a town. Print the largest value the WEAKEST town's power can be raised to.

s = 1 2 4 5 0, r = 1, k = 2 answer 5 s = 4 4 4 4, r = 0, k = 3 answer 4 s = 5 0 0 0 0 0 5, r = 1, k = 2 answer 2 s = 0 0 0, r = 1, k = 5 answer 5

## Why placing generators greedily by itself is not enough

The natural idea is "find the weakest town and build there", repeated k times. With k up to 10^9 that is not a loop you can run, and it is not even correct: building at the weakest town helps its neighbours too, and the right choice of position depends on how much power the towns to the right will still need.

Fix the TARGET instead. Ask: can every town be brought to power m using at most k new generators?

## The sweep that answers it

Compute each town's current power once, with a prefix sum over s and a window of radius r. Then sweep left to right maintaining the extra power contributed so far by generators you have decided to build:

feasible(m): add = array of n + 1 zeros, run = 0, used = 0 for i in 0 .. n - 1: run += add[i] p = base[i] + run if p < m: need = m - p used += need if used > k: return false run += need if i + 2r + 1 <= n - 1: add[i + 2r + 1] -= need # the new power expires here return true

Every shortfall is made up in one go, and the need generators are all placed at town min(n - 1, i + r), which is the FURTHEST town that still covers i.

## Why placing as far right as possible is optimal

Sweeping left to right, town i is the leftmost town still below m. Every town to its left already meets the target and, because generators only ever add power, will continue to.

Any generator that helps town i sits in [i - r, i + r]. Among those positions, i + r covers [i, i + 2r], and every other legal position q <= i + r covers [q - r, q + r], whose right end is at most i + 2r. So the set of towns helped by a generator at i + r includes every town at or after i that any other legal position helps. Since the towns before i no longer need help, choosing i + r dominates every alternative. Clamping to n - 1 when i + r runs off the end changes nothing, because coverage past the last town is wasted anyway.

The amount is forced: town i is short by exactly need, generators come in whole units, and building fewer leaves it short. So both the position and the count are optimal, and one left-to-right pass really does compute the minimum number of generators required for target m.

## Why the predicate is monotone

If k generators can lift every town to m, the same generators lift every town to m - 1. So the achievable targets form a prefix and the answer is the LAST true value: the midpoint rounds UP.

## The bounds

lo = 0. A town with no generator anywhere near it has power 0 and nothing can be guaranteed below that.

hi = sum(s) + k. No town can ever exceed the total number of generators in existence, and that total is the starting sum plus the k you add. This is the bound worth thinking about: it is not max(s), and it is not k.

## The boundary that breaks a careless implementation

Two.

The expiry index is i + 2r + 1, not i + r + 1. The generators went in at i + r and reach r further, so their help lasts through town i + 2r. Writing i + r + 1 retires the help halfway and reports far more generators are needed than really are.

And used must be tested immediately after each addition, not after the loop. It is not an overflow risk in 64 bits, but bailing out the moment the budget is exceeded is what keeps a hopeless target cheap, and a target that has already failed should not go on writing into the difference array.

## Relationship with problem 259

259 is the other maximise-the-minimum problem to read beside this one: place c items on a line so that the smallest gap between two of them is as large as possible. Both fix the target first, both test it with a single left-to-right greedy, and both take the LAST true value, so the midpoint rounds up in each.

The greedies sit at opposite ends of their options. 259 takes the next position as EARLY as the gap allows, leaving as much line as possible for the items still to come; here the generators go as FAR RIGHT as they can while still covering the town that needs them, so their help reaches furthest into the towns not yet checked. Both are the same instinct, which is to spend a forced choice in whichever direction leaves the remaining work easiest.

## Overflow

sum(s) reaches 10^10 and k reaches 10^9, so the upper bound is above 10^10 before the search even starts. need, run and used all live in that range. Every one of them must be 64-bit; in 32 bits the upper bound alone wraps negative and the search terminates immediately with the answer 0.

## Cost

O(n) for the base powers, then O(n) per check over O(log(sum + k)) checks.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ r ≤ n` - `0 ≤ k ≤ 10^9` - `0 ≤ s[i] ≤ 100000`