这玩意儿不是长成一个下凸壳的右半部分吗

斜率单调非降，而且 delta 不超过 max{a[i]-a[i-1]} 啊

所以处理出来差分数组然后取 maxelement 为什么是错的捏

只有 65 分

换成 [1,1e12] 就过了

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10, inf = 1e9;
int n, k, a[N], b[N], dp[N][2], g[N][2];

inline pair <int, int> check(int mid) {
  for (int i = 1; i <= n; ++i) {
    dp[i][0] = dp[i - 1][0], g[i][0] = g[i - 1][0];
    if (dp[i - 1][1] <= dp[i][0]) {
      if (dp[i][0] == dp[i - 1][1]) g[i][0] = min(g[i][0], g[i - 1][1]);
      else g[i][0] = g[i - 1][1], dp[i][0] = dp[i - 1][1];
    }
    dp[i][1] = dp[i - 1][0] + a[i] - mid, g[i][1] = g[i - 1][0] + 1;
  }
  if (dp[n][0] < dp[n][1]) return {dp[n][0], g[n][0]};
  if (dp[n][0] == dp[n][1]) return {dp[n][0], min(g[n][0], g[n][1])};
  return {dp[n][1], g[n][1]};
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
  cin >> n >> k; for (int i = 1; i <= n; ++i) cin >> b[i];
  for (int i = 1; i < n; ++i) a[i] = b[i + 1] - b[i]; --n;
  int l = 0, r = *max_element(a + 1, a + 1 + n) + 10, res;
  while (l <= r) {
    int mid = (l + r) >> 1; auto tmp = check(mid);
    int val = tmp.first, num = tmp.second;
    if (num <= k) res = val + k * mid, l = mid + 1;
    else r = mid - 1;
  }
  cout << res << endl;
  return 0;
}