考虑恰好选 \(k\) 个子段怎么做。
设恰好选 \(i\) 个子段的和最大值为 \(h_k\)。可以得到 \(h_{i + 1} - h_i \le h_i - h_{i - 1}\)，因为 \(h_i \to h_{i + 1}\) 的过程就是多选一个子段，贡献肯定不如上一次选即 \(h_{i - 1} \to h_i\) 大。如果它不成立，那我们可以交换 \(h_{i - 1} \to h_i\) 和 \(h_i \to h_{i + 1}\) 选的段从而得到更大的 \(h_k\)，矛盾。
那么 \((i, h_i)\) 构成一个上凸包。接下来是经典的 wqs 二分，二分直线斜率切这个上凸包，dp 一遍求出最大截距，这样二分即可找到过 \((k, h_k)\) 且与上凸包相切的直线方程，就能得到 \(h_k\)。
dp 的过程是平凡的。设 \(f_i\) 为 \([1, i]\) 个中选了若干个子段，它们的和最大值，设 \(g_i\) 为在取到最大值的基础上，选的段数最小值。因为当有一些点和 \((k, h_k)\) 共线时，我们希望最后算出来是最左边的点，从而得到这条直线。
\(f_i\) 有转移 \(f_i = \max(f_{i - 1}, \max\limits_{j = 1}^i (f_{j - 1} + \sum\limits_{p = j}^i a_p))\)。令 \(b_i = \sum\limits_{j = 1}^i a_j\)，维护前缀最大的 \(f_i - b_i\) 和在它最大的基础上最小的 \(g_i\)，dp 即可做到 \(O(n)\)。
如果只是限制最多选 \(k\) 个，那如果 \((k, h_k)\) 在左半边（即最高点的左边），那 \(\forall i \in [1, k), h_k \ge h_i\)，当作恰好 \(k\) 个处理即可；如果它在右半边，二分斜率时下界设置为 \(0\)，那么它就不能被截到。这种情况，直接求出 \(\max\limits_{i = 1}^n h_i\) 即可。这里也可以用上面的 dp 方法。
总时间复杂度 \(O(n \log V)\)，\(V\) 是值域。
code
// Problem: P6821 [PA2012]Tanie linie
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6821
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll n, m, a[maxn], b[maxn], f[maxn], g[maxn];
inline pii calc(ll x) {
ll mx = 0, cnt = 1;
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1];
g[i] = g[i - 1];
ll val = mx + b[i] - x;
if (val > f[i]) {
f[i] = val;
g[i] = cnt;
} else if (val == f[i]) {
g[i] = min(g[i], cnt);
}
val = f[i] - b[i];
if (val > mx) {
mx = val;
cnt = g[i] + 1;
} else if (val == mx) {
cnt = min(cnt, g[i] + 1);
}
}
return make_pair(f[n], g[n]);
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
b[i] = b[i - 1] + a[i];
}
ll l = 0, r = 2e9, ans = -inf;
while (l <= r) {
ll mid = (l + r) >> 1;
pii p = calc(mid);
if (p.scd <= m) {
ans = p.fst + m * mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == -inf) {
ans = calc(0).fst;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}