WQS 二分的写法，但是不知道在哪里 WA 了 qwq

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

int a[500100];
long long f[500100][2],g[500100][2];
int n,k;

bool check(int x)
{
    for(int i=1; i<=n; 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];

        f[i][1]=f[i-1][0]+a[i]+x; g[i][1]=g[i-1][0]+1;
    }
    return f[n][0]<f[n][1] ? g[n][1]<k : g[n][0]<k;
}
int erfen(int l, int r)
{
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid+1))
        l=mid+1;
        else
        r=mid;
    }
    return l;
}
int main()
{
    cin>>n>>k;
    for(int i=1; i<=n; i++)
    scanf("%d", &a[i]);

    long long p=check(0) ? 0 : erfen(0, 1e7);

    for(int i=1; i<=n; i++)
    {
        f[i][0]=max(f[i-1][0], f[i-1][1]);
        f[i][1]=f[i-1][0]+a[i]+p;
    }
    cout<<max(f[n][0], f[n][1])-k*p;
    return 0;
}