description: Alice has an integer sequence a of length n and all elements are different. She will choose a subsequence of a of length m, and defines the value of a subsequence a_{b_1},a_{b_2},…,a_{b_m} as $$$∑_{i = 1}^m (m ⋅ a_{b_i}) - ∑_{i = 1}^m ∑_{j = 1}^m f(min(b_i, b_j), max(b_i, b_j)), where f(i, j) denotes \min(a_i, a_{i + 1}, \ldots, a_j)$$$.
  
  Alice wants you to help her to maximize the value of the subsequence she choose.
  
  A sequence s is a subsequence of a sequence t if s can be obtained from t by deletion of several (possibly, zero or all) elements.
  
  Input
  
  The first line contains two integers n and m (1 ≤ m ≤ n ≤ 4000).
  
  The second line contains n distinct integers a_1, a_2, …, a_n (1 ≤ a_i < 2^{31}).
  
  Output
  
  Print the maximal value Alice can get.
  
  Examples
  
  Input
  
  
  6 4
  15 2 18 12 13 4
  
  
  Output
  
  
  100
  
  
  Input
  
  
  11 5
  9 3 7 1 8 12 10 20 15 18 5
  
  
  Output
  
  
  176
  
  
  Input
  
  
  1 1
  114514
  
  
  Output
  
  
  0
  
  
  Input
  
  
  2 1
  666 888
  
  
  Output
  
  
  0
  
  Note
  
  In the first example, Alice can choose the subsequence [15, 2, 18, 13], which has the value 4 ⋅ (15 + 2 + 18 + 13) - (15 + 2 + 2 + 2) - (2 + 2 + 2 + 2) - (2 + 2 + 18 + 12) - (2 + 2 + 12 + 13) = 100. In the second example, there are a variety of subsequences with value 176, and one of them is [9, 7, 12, 20, 18].
solution: #include <bits/stdc++.h>
  namespace wxy {
  const long long N = 4005, inf = 1ll << 31;
  long long f[N][N], tot;
  long long a[N], size[N];
  long long n, m, ls[N], rs[N];
  void calc(long long &u, long long l, long long r) {
    if (!u) u = ++tot;
    long long rt = 0;
    size[u] = 1;
    if (l == r) {
      f[u][1] = (m - 1) * a[l];
      return;
    }
    for (long long i = l; i <= r; i++)
      if (a[rt] > a[i]) rt = i;
    if (rt != l) calc(ls[u], l, rt - 1);
    if (rt != r) calc(rs[u], rt + 1, r);
    for (long long i = 0; i <= std::min(size[ls[u]], m); i++)
      for (long long j = 0; j <= std::min(size[rs[u]], m); j++) {
        if (i + j == 0) continue;
        long long val = f[ls[u]][i] + f[rs[u]][j];
        if (i + j <= m)
          f[u][i + j] = std::max(f[u][i + j], val - 2 * i * j * a[rt]);
        else
          break;
        if (i + j + 1 <= m)
          f[u][i + j + 1] =
              std::max(f[u][i + j + 1], val + m * a[rt] - 2 * i * j * a[rt] -
                                            2 * (i + j) * a[rt] - a[rt]);
      }
    size[u] += size[ls[u]] + size[rs[u]];
  }
  inline long long get(long long l, long long r) {
    long long res = 0;
    for (long long i = l; i <= r; i++) {
      res += m * a[i];
      for (long long j = l; j <= r; j++) {
        long long val = inf;
        for (long long k = std::min(i, j); k <= std::max(i, j); k++)
          val = std::min(val, a[k]);
        std::cout << val << std::endl;
        res -= val;
      }
    }
    return res;
  }
  inline void main() {
    memset(f, 0xcf, sizeof f);
    std::cin >> n >> m;
    for (long long i = 1; i <= n; i++) std::cin >> a[i];
    for (long long i = 0; i <= n; i++) f[i][0] = 0;
    a[0] = inf;
    long long rt = 0;
    calc(rt, 1, n);
    std::cout << f[1][m];
  }
  }  // namespace wxy
  signed main() {
    wxy::main();
    return 0;
  }
  