Explanation

First, given some set of cakes $S$, it is always optimal to arrange them in sorted order by color. To prove this, consider inductively adding the cakes in ascending order. It can be shown that placing the cake between the greatest one added so far and the smallest one is always optimal. Thus, the total color is $2(\max(S) - \min(S))$.

Sort the cakes by color. For any set of cakes, the smallest is the leftmost one and the largest is the rightmost one. The task now becomes choosing some range $[l, r]$ that maximizes the sum of the $m$ largest beauty values, minus $2 \cdot (C_r - C_l)$.

Let $\texttt{opt}(l)$ be the optimal right endpoint for some left endpoint. We can observe that $\texttt{opt}$ is a non-decreasing function (the proof of this has been left as an exercise to the reader). This motivates a divide and conquer solution.

Suppose we know that $\texttt{opt}(i) \in [p, q]$ for $i \in [l, r]$. If $p = q$, then we are done. Otherwise, let $m = \lfloor \frac{l+r}{2}\rfloor$, and compute $\texttt{opt}(m)$. We now know that $\texttt{opt}(i)$ lies in the range $[p, \texttt{opt(m)}]$ for $i \in [l, m)$, and in the range $[\texttt{opt}(m), q]$ for $i \in (m, r]$. We can then recurse. By the master theorem, this will run in $\tilde{\mathcal{O}}(n)$ time.

The only step left is to compute the sum of the $m$ largest values in a range. This can be done with a variety of data structures in logarithmic time.

Time Complexity: $\mathcal{O}(n\log^2n)$

Implementation

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

namespace std {

template <class Fun> class y_combinator_result {
	Fun fun_;

  public:
	template <class T>