RT，萌新刚学wqs，本来是在做花姐姐的加强版，然后写出了代码看着花姐姐的题解改了改，拿来交这道题，只有10分/kk

求助/kel

#include<cstdio>
const int M=5e5+5;
typedef long long ll;
int n,m,s,t,q[M],r[M],cnt[M];
ll a[M],dp[M],sum[M];
inline ll calc(const int&L,const int&R){
    int mid=L+R>>1;
    return a[mid]*((mid<<1)-L-R+1)-(sum[mid]<<1)+sum[L-1]+sum[R];
}
inline ll trans(const int&L,const int&R){
    return dp[L]+calc(L+1,R);
}
inline int check(const int&k){
    int i,L,R,mid;
    s=0;t=0;q[0]=0;r[0]=1;
    for(i=1;i<=n;++i){
        while(s<t&&r[s]<i)++s;
        if(r[s]>i)--s;
        dp[i]=trans(q[s],i)+k;cnt[i]=cnt[q[s]]+1;
        while(t&&trans(q[t],r[t])>=trans(i,r[t]))--t;
        L=r[t];R=n;
        while(L<R){
            mid=L+R>>1;
            if(trans(q[t],mid)>=trans(i,mid))R=mid;
            else L=mid+1;
        }
        if(L<n)q[++t]=i,r[t]=L;
    }
    return cnt[n];
}
signed main(){
    int i,L=0,R=1e9,mid;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i){
        scanf("%lld",a+i);
        sum[i]=sum[i-1]+a[i];
    }
    while(L<R){
        mid=L+R>>1;
        if(check(mid)>m)L=mid+1;
        else R=mid;
    }
    check(L);
    printf("%lld",dp[n]-1ll*m*L);
}