TLE求助

/*
	Luogu name: Symbolize
	Luogu uid: 672793
*/
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=1e7+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
long long n,m,a[N],s[N],f[N],q[N],g[N];
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
long long calc(int l,int r)
{
	int mid=l+r>>1;
	return (mid-l+1)*a[mid]-(s[mid]-s[l-1])+(s[r]-s[mid])-(r-mid)*a[mid];
}
int find(int i,int j)
{
	if(f[i]+calc(i+1,n)<f[j]+calc(j+1,n)) return n+1;
	int l=j,r=n,ans=0;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(f[i]+calc(i+1,mid)>f[j]+calc(j+1,mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	return ans;
}
bool check(int x)
{
	int hh=1,tt=1;
	q[hh]=0;
	rep1(i,1,n)	
	{
		while(hh<tt&&find(q[hh],q[hh+1])<=i) ++hh;
		f[i]=f[q[hh]]+calc(q[hh]+1,i)+x;
		g[i]=g[q[hh]]+1;
		while(hh<tt&&find(q[tt-1],q[tt])>=find(q[tt],i)) --tt;
		q[++tt]=i;
	}
	return g[n]<=m;
}
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	m=read();
	rep1(i,1,n) a[i]=read();
	sort(a+1,a+n+1);
	rep1(i,1,n) s[i]=s[i-1]+a[i];
	int l=0,r=5e11,ans=-1;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	check(ans);
	cout<<f[n]-ans*m<<"\n";
	return 0;
}