arc100_a: Linear Approximation

By observation, we can see that the answer is always the median of A[i] - i array. We can prove by moving any cut toward the median, and it will improve the solution. Note for the even N case either cut would do.

arc100_b: Equal Cut

Multi-dimension problem. We use the standard technique of searching on one, and analysis on others.

So we brute force on the central cut.

Claim: if we fix the central cut, we can directly infer the value of the other two cuts

Proof:

1. For each half, the cut closet to sum(seg)/2 max min and min max AT THE SAME TIME, because the overall sum is same.

2. If the global optimals are the on the same side, then we found it already.

3. If the global optimals are on the different side, then it must be min of both sides and max of both sides. Note that we can not move up min or max any further, so no other choices are possible, i.e, we min max and max min AT THE SAME TIME

I was able to get greedy insight during the contest, but missing the A[i] > 0 requires means I was not able to come up with theliner time method!!!