A supply convoy must cross n checkpoints, numbered 1 to n, strictly in order. Checkpoint i drains drain_i units of fuel from the convoy as it passes through. The convoy also carries a single auxiliary reserve tank holding reserve units of backup fuel. At exactly one checkpoint of the commander's choosing, the reserve tank may be activated: at that checkpoint only, the fuel actually consumed becomes max(0, drain_i - reserve) instead of drain_i (any unused reserve capacity is wasted, and the tank cannot be used again elsewhere). At every other checkpoint the convoy consumes the full drain_i. The convoy's fuel level must remain strictly greater than zero after crossing every single checkpoint. Assuming the commander picks the one checkpoint to apply the reserve to as wisely as possible, determine the minimum integer amount of starting fuel that guarantees the convoy can cross all n checkpoints.
n and reserve.n integers drain_1 ... drain_n.A single integer: the minimum starting fuel.
Example 1
Input
3 2 3 4 5
Expected
11
Explanation
Applying the reserve to the checkpoint with drain 5 reduces its consumption to max(0,5-2)=3. Total consumption becomes 3+4+3=10, and since all drains are positive the running total only grows, so the tightest constraint is after the last checkpoint: fuel must exceed 10, giving minimum starting fuel 11.
Example 2
Input
1 100 7
Expected
1
Explanation
There is only one checkpoint, and the reserve (100) fully covers its drain (7), so consumption there becomes max(0,7-100)=0. The convoy only needs fuel > 0 throughout, so the minimum starting fuel is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →