TESTROOMS (CSPTST 2022-2023)

#define task "TESTROOMS"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e4 + 5;
constexpr ll Inf = 1e17;

template <class T>
void readInt(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

struct ConvexHullTrick
{
    ll A[N], B[N];
    int piv, line[N], szline, szpoint;
    ld point[N];

    ConvexHullTrick()
    {
        szline = 0;
        szpoint = 0;
        piv = 0;
        point[szpoint++] = -Inf;
    }

    void Reset()
    {
        szline = 0;
        szpoint = 0;
        piv = 0;
        point[szpoint++] = -Inf;
    }

    ld ff(int x, int y)
    {
        return (ld)1.0 * (B[x] - B[y]) / (A[y] - A[x]);
    }

    void Add(int x)
    {
        while (szline > 1 || (szline == 1 && A[line[szline - 1]] == A[x]))
        {
            if (A[line[szline - 1]] == A[x])
            {
                if (B[line[szline - 1]] <= B[x])
                    break;
                else
                {
                    --szline;
                    if (!szline == 0)
                        --szpoint;

                    piv = min(piv, szpoint - 1);
                }
            }
            else
            {
                if (ff(line[szline - 1], x) <= ff(x, line[szline - 2]))
                {
                    --szline;
                    if (!szline == 0)
                        --szpoint;

                    piv = min(piv, szpoint - 1);
                }
                else
                    break;
            }
        }

        if (szline == 0 || A[line[szline - 1]] != A[x])
        {
            if (szline != 0)
                point[szpoint++] = ff(x, line[szline - 1]);
            line[szline++] = x;
        }
    }

    int Get(ll x)
    {
        while (piv < szpoint && point[piv] <= x)
            ++piv;

        return line[piv - 1];
    }
} calf, calg;

int n, k;
ll a[N], x[N], f[N], g[N], f1[N];

void Read()
{
    // cin >> n >> k;
    readInt(n), readInt(k);

    for (int i = 1; i <= n; ++i)
        // cin >> x[i];
        readInt(x[i]);
}

void Solve()
{
    sort(x + 1, x + n + 1);

    for (int i = 1; i <= n; ++i)
    {
        a[i] = a[i - 1] + x[i];
        f1[i] = f1[i - 1] + x[i] - x[(i + 1) / 2];
    }

    for (int j = 2; j <= k; ++j)
    {
        for (int i = j - 1; i <= n; ++i)
        {
            if (i >= j)
            {
                int optg = calg.Get(x[i]);

                g[i] = f1[optg] + x[i] * (i - optg) - (a[i] - a[optg]);
                calf.A[i] = -x[i];
                calf.B[i] = g[i] - a[i] + x[i] * i;
                calf.Add(i);

                int optf = calf.Get(i);
                f[i] = g[optf] + (a[i] - a[optf]) - x[optf] * (i - optf);
            }

            // cout << f[i] << (i == n ? "\n" : " ");

            calg.A[i] = -i;
            calg.B[i] = f1[i] + a[i];
            calg.Add(i);
        }

        calf.Reset();
        calg.Reset();
        swap(f, f1);
    }

    cout << f1[n];
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Solve();
}

/*
5 5
1 1 2 3 5
*/

/*
g(i) + (a_t - a_i) - x_i * (t - i) < g(j) + (a_t - a_j) - x_j * (t - j)
g(i) - a_i + i * x_i - x_i * t < g(j) - a_j + j * x_j - x_j * t



f(i) + x_t * (t - i) - (a_t - a_i) < f(j) + x_t * (t - j) - (a_t - a_j)
f(i) - x_t * i + a_i < f(j) - x_t * j + a_j

Khi f(t) va g(t) dat min, y=at + b cung dat min => Convexhull trick
*/