Official Analysis (C++)

Explanation

Before we start, append a $0$ to the end of the array and force that element to always be blocked. This makes talking about the problem easier while not affecting the answer.

We can binary search on the answer; to see how, let's see how we can check if a cost of at most $C$ is possible.

Let $\texttt{dp}[i]$ be the minimum cost only considering elements up to index $i$. Since we're taking the maximum over the blocked segments' sums, we don't have to worry about them as long as each of them is less than $C$; we only have to care about the sum of the blocked elements.

If $j$ is the smallest element we can start blocking from without having the sum of the new segment we create exceed $C$, then

which can be computed using a segment tree.

Implementation

Time Complexity: $O(n \log n \log S)$, where $S=\sum_{i=1}^n a_i$.

Copy
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

 Code Snippet: Segment Tree (from the module) (Click to expand)