调了一个下午，道心破碎。

只支持微信。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,m,l,r=1e9,mid,head1,tail1,head2,tail2,a[N],s[N],g[N],f[N],cntf[N],cntg[N],q1[N],q2[N];
int YF(int i){
	return g[i]-s[i]+i*a[i];
}
int XF(int i){
	return a[i];
}
int YG(int i){
	return f[i]+s[i];
}
int XG(int i){
	return i;
}
void check(int x){
	head1=head2=1;
	tail1=tail2=0;
	q2[++tail2]=0;
	for(int i=1;i<=n;i++){
		while(head2<tail2&&YG(q2[head2+1])-YG(q2[head2])<=a[i]*(XG(q2[head2+1])-XG(q2[head2]))) head2++;
		g[i]=f[q2[head2]]+(i-q2[head2])*a[i]-(s[i]-s[q2[head2]]);
		while(head1<tail1&&(YF(q1[tail1])-YF(q1[tail1-1]))*(XF(q1[tail1])-XF(i))>=(YF(q1[tail1])-YF(i))*(XF(q1[tail1])-XF(q1[tail1-1]))) tail1--;
		q1[++tail1]=i;
		cntg[i]=cntf[q2[head2]];
		while(head1<tail1&&YF(q1[head1+1])-YF(q1[head1])<=i*(XF(q1[head1+1])-XF(q1[head1]))) head1++;
		f[i]=g[q1[head1]]+(s[i]-s[q1[head1]])-(i-q1[head1])*a[q1[head1]]+x;
		while(head2<tail2&&(YG(q2[tail2])-YG(q2[tail2-1]))*(XG(q2[tail2])-XG(i))>=(YG(q2[tail2])-YG(i))*(XG(q2[tail2])-XG(q2[tail2-1]))) tail2--;
		q2[++tail2]=i;
		cntf[i]=cntg[q1[head1]]+1;
	}
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
	while(l<=r){
		mid=l+r>>1;
		check(mid);
		if(cntf[n]<=m) r=mid-1;
		else l=mid+1;
	}
	check(l);
	printf("%lld",f[n]-m*l);
	return 0;
}