Kattis Estimation

#include <bits/stdc++.h>
#define int long long

using namespace std;

void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}

const int NMAX = 2e3 + 3;
const int INF = 1e18L;
int a[NMAX], cost[NMAX][NMAX], dp[NMAX];

void min_self(int &a, int b) {
  a = min(a, b);
}

void solve() {
  int N, K;
  cin >> N >> K;
  for (int i = 1; i <= N; ++i)
    cin >> a[i];
  for (int i = 1; i <= N; ++i) {
    priority_queue<int> lower;
    priority_queue<int,vector<int>,greater<int>> upper;
    int sum_lower = 0, sum_upper = 0;
    for (int j = i; j <= N; ++j) {
      sum_lower += a[j];
      lower.emplace(a[j]);
      if (lower.size() > upper.size() + 1 || (!upper.empty() && lower.top() > upper.top())) {
        int aux = lower.top();
        lower.pop();
        sum_lower -= aux, sum_upper += aux;
        upper.emplace(aux);
      }
      if (upper.size() > lower.size()) {
        int aux = upper.top();
        upper.pop();
        sum_lower += aux, sum_upper -= aux;
        lower.emplace(aux);
      }
      int median = lower.top();
      cost[i][j] = lower.size() * median - sum_lower + sum_upper - upper.size() * median;
    }
  }
  for (int i = 1; i <= N; ++i)
    dp[i] = INF;
  for (int k = 0; k < K; ++k)
    for (int i = N - 1; i >= 0; --i)
      for (int j = i + 1; j <= N; ++j)
        min_self(dp[j], dp[i] + cost[i + 1][j]);
  cout << dp[N] << '\n';
}

int32_t main() {
  fastIO();
  solve();
  return 0;
}