90pts 求调

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[300005], f[300005], g[300005];
signed main() {
    int n, k; cin >> n >> k;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    int L = -1e6, R = 1e6, ans = 0;
    while(L <= R) {
        int mid = (L + R) >> 1;
        for(int i = 1;i <= n;i++) a[i] -= mid;
        f[0] = 0; f[1] = max(0ll, a[1]);
        if(f[1] == 0) g[1] = 0; else g[1] = 1;
        for(int i = 2;i <= n;i++) {
            if(f[i-1] > (f[i-2] + a[i]))
                g[i] = g[i-1], f[i] = f[i-1];
            else g[i] = g[i-2] + 1, f[i] = f[i-2] + a[i];
        } if(g[n] <= k) ans = max(ans, f[n] + g[n] * mid), R = mid - 1;
        else L = mid + 1;
        for(int i = 1;i <= n;i++) a[i] += mid;
    } cout << ans << endl;
    return 0;
}