747. What the Second Runner Can Still Collect
A grid has exactly TWO rows and n columns. A runner starts at the top left, may move only
right or down, and must finish at the bottom right, so its path goes right along the top row,
drops down once, and continues right along the bottom row.
The first runner takes every value on its path and sets each of those cells to 0. The second runner then takes the best remaining path.
The first runner plays to MINIMISE the second runner's total. Print what the second runner collects.
``` top 2 5 4 -> 4 bottom 1 5 1
top 3 3 1 -> 4 bottom 8 5 2
top 1 3 1 15 -> 7 bottom 1 3 3 1 ```
## What a path leaves behind
A path that drops down at column c covers the top row from 0 to c and the bottom row from
c to n-1. So after the first runner drops at c, what remains is:
· the top row STRICTLY AFTER c
· the bottom row STRICTLY BEFORE c
Everything else is zero.
## The second runner can take only one of the two leftovers
The second runner also drops down at some column c2. Its path takes the top row up to c2
and the bottom row from c2 on.
If c2 <= c the top part is entirely inside the zeroed region, so it collects only the bottom
row from c2 to c-1, which is at most the whole bottom prefix before c. If c2 > c it
collects only the top row from c+1 to c2, at most the whole top suffix after c.
So the second runner's best is exactly
max( sum of top[c+1 ..], sum of bottom[.. c-1] )
and the first runner picks the c making that maximum as small as possible.
## The whole problem is one line of reasoning
Once you see that the leftovers are a SUFFIX of the top row and a PREFIX of the bottom row, and
that the second runner can reach only one of them, the answer is a minimum over n columns of
a maximum of two prefix quantities.
Both are ordinary prefix and suffix sums, so the sweep is O(n). Simulating both runners over
every pair of drop columns is O(n^2) and gives the same answer.
## Why it is a maximum inside and a minimum outside
The second runner maximises, because it moves second and takes the better of the two leftovers. The first runner minimises, because it chooses first and is trying to starve the second. Writing the two the wrong way round produces a plausible-looking answer that is wrong on almost every input.
## The two ends
Dropping at column 0 leaves the entire top suffix after column 0 and an empty bottom prefix.
Dropping at column n-1 leaves an empty top suffix and the entire bottom prefix before
n-1. Both must be considered, and a single-column grid gives 0 because both leftovers are
empty.
## Overflow
10^5 columns of 10^5 total 10^10.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ each value ≤ 100000`
Input
The first line contains an integer n.
The second line contains n integers, the top row.
The third line contains n integers, the bottom row.
Output
Print one integer, the total the second runner collects.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.