Explanation

The final answer will be of the form $k_1 c_1 + k_2 c_2 + \dots + k_n c_n$. The sequence $k$ is a series of "mountains" and "valleys", the valleys occuring at the indicies of the schools and the mountains occuring at the midpoints between two schools. By partitioning this sequence along these points, we get a series of sequences that are increasing by $1$ or decreasing by $1$. Define the DP states as follows:

• $f_{i,m}$ - minimum distance considering the first $i$ elements using $m$ schools ending at a valley
• $g_{i,m}$ - minimum distance considering the first $i$ elements using $m$ schools ending at a mountain

The transitions are the following:

The transitions take linear time, but can be optimized to amortized constant time using convex hull trick.

Define the following:

• $t_k = \sum_{i = 1}^k c_i$
• $p_k = \sum_{i = 1}^k c_i \cdot i$
• $s_k = \sum_{i = 1}^k c_i \cdot (n - i + 1)$

These can be precomputed in $\mathcal{O}(n)$ time.

The DP equations becomes:

With a bit of rearranging:

Because both the slopes and the query points are monotonic, this can be maintained using a deque in amortized $\mathcal{O}(1)$. The total complexity is $\mathcal{O}(nm)$.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

namespace geo {
const double EPS = 1e-9;

template <typename T> class point {
	static_assert(is_arithmetic<T>::value, "T must be an arithmetic type");

  public: