【悬关】wqs 二分 WA on #22，96 pts 求调

#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ll long long
using namespace std;
const int N = 1e6 + 5;
inline int read () {
	char c = getchar();	
	int res = 0, f = 1;
	while (!isdigit(c)) {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c)) res = (res << 3) + (res << 1) + (c ^ '0'), c = getchar();
	return f * res;
}
int n, K, a[N], g[N][2];
ll l = 1, r = 1ll << 31, mid, ans, f[N][2];
inline int check (int k) {
	f[0][0] = 0, f[0][1] = -1e12;
	FOR(i, 1, n) {
		if (f[i - 1][0] - k > f[i - 1][1]) {
			g[i][1] = g[i - 1][0] + 1;			
			f[i][1] = f[i - 1][0] - k + a[i];
		} else g[i][1] = g[i - 1][1], f[i][1] = f[i - 1][1] + a[i];
		if (f[i - 1][0] > f[i - 1][1]) f[i][0] = f[i - 1][0], g[i][0] = g[i - 1][0];
		else f[i][0] = f[i - 1][1], g[i][0] = g[i - 1][1];
	}
	if (f[n][0] > f[n][1]) return g[n][0];
	return g[n][1];
}
int main () {
	n = read(), K = read();
	FOR(i, 1, n) scanf("%d", &a[i]);
	while (l <= r) {
		mid = l + r >> 1;
		if (check(mid) >= K) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	check(ans);
	printf("%lld", max(f[n][0], f[n][1]) + ans * K);
	return 0;
}