时间复杂度也是对的，数组也开的够大了

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

const int N = 2e7 + 10;

#define int long long
#define X(j) (s2[j])
#define Y(j) (f[j] + s1[j])
#define FOR(i,a,b) for(int i = a;i <= b;i++)
#define _FOR(i,a,b) for(int i = a;i >= b;i--)

template<typename T> void read(T &x)
{
    x = 0;int f = 1;
    char c = getchar();
    for(;!isdigit(c);c = getchar()) if(c == '-') f = -1;
    for(;isdigit(c);c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n,m,maxx;
int q[N],l,r;
int a[N],s1[N],s2[N],f[N];
long double slope(int k,int j)
{
	if(X(k) == X(j)) 
	{
		if(Y(j) < Y(k)) return -1e18;
		return 1e18;
	}
	return (long double) (1.0 * (Y(j) - Y(k)) / (X(j) - X(k)));
} 

signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	read(n),read(m);
	FOR(i,1,n) 
	{
		read(a[i]);
		maxx = max(maxx,a[i]);
	}
	maxx += m;
	FOR(i,1,n) s2[a[i]]++,s1[a[i]] += a[i];
	FOR(i,1,maxx) s1[i] += s1[i - 1],s2[i] += s2[i - 1];
	q[1] = 0;
	l = r = 1;
	FOR(i,1,maxx)
	{
		if(i >= m)
		{
			while(l < r && slope(q[r - 1],q[r]) >= slope(q[r],i - m)) --r;
			q[++r] = i - m;
		}
		while(l < r && slope(q[l],q[l + 1]) <= i) ++l;
		int tmp = q[l];
		f[i] = f[tmp] + i * (s2[i] - s2[tmp]) - s1[i] + s1[tmp];
	}
	int minx = 1e18;
	FOR(i,maxx - m,maxx) minx = min(minx,f[i]);
	printf("%lld\n",minx);
    return 0;
}