RT

#include<bits/stdc++.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define db double
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f3f
#define INF 0x7f7f7f7f7f
using namespace std;
namespace Iwara{
	template<class T> T MAX(T x,T y){
		return x>y?x:y;
	}
	template<class T,class ... Arg> T MAX(T x,T y,Arg ... arg){
		return MAX(x>y?x:y,arg...);
	}
	template<class T> T MIN(T x,T y){
		return x<y?x:y;
	}
	template<class T,class ... Arg> T MIN(T x,T y,Arg ... arg){
		return MIN(x<y?x:y,arg...);
	}
	template<class T> T lowbit(T x){
		return x&-x;
	}
	template<class T> void SWAP(T &x,T &y){
		T qwq;
		qwq=x;
		x=y;
		y=qwq;
		return;
	}
}
using namespace Iwara;
const ll MAXN=4e6+5;
ll n,m,maxt=0,cnt[MAXN],sum[MAXN];
// dp[i]=min(dp[j]+sum(j<=t[k]<=i,i-t[k]))
// dp[i]=min(dp[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]))
// dp[i]=min(dp[j]+cnt[i]*i-cnt[j]*i-sum[i]+sum[j])
// dp[i]=cnt[i]*i-sum[i]+min(dp[j]-cnt[j]*i+sum[j])
// dp[i]-cnt[i]*i+sum[i]=dp[j]-cnt[j]*i+sum[j]
// cnt[j]*i+dp[i]-cnt[i]*i+sum[i]=dp[j]+sum[j]
// y=dp[j]+sum[j] x=cnt[j] k=i b=dp[i]-cnt[i]*i+sum[i]
ll l=1,r=0;
struct point{
	ll id;
	db X,Y;
};
point q[MAXN];
db get_k(point p1,point p2){
	return p1.X==p2.X?INF:(p2.Y-p1.Y)/(p2.X-p1.X);
}
ll dp[MAXN];
int main(){
	cin>>n>>m;
	for(ll i=1,t;i<=n;i++){
		cin>>t;
		maxt=MAX(maxt,t);
		cnt[t]++;
		sum[t]+=t;
	}
	for(int i=1;i<maxt+m;i++)cnt[i]+=cnt[i-1],sum[i]+=sum[i-1];
//	cout<<maxt+m<<endl;
	for(int i=0;i<maxt+m;i++){
		if(i-m>=0){
			point p;
			p.id=i-m,p.X=cnt[i-m],p.Y=dp[i-m]+sum[i-m];
			while(l<r&&get_k(q[r-1],q[r])>=get_k(q[r],p))r--;
			q[++r]=p;
		}
		while(l<r&&get_k(q[l],q[l+1])<=i)l++;
		dp[i]=cnt[i]*i-sum[i];
		ll j=q[l].id;
		if(l<=r)dp[i]=MIN(dp[i],dp[j]+(cnt[i]-cnt[j])*i-sum[i]+sum[j]);
//		for(int qwq=l;qwq<=r;qwq++)cout<<q[qwq].id<<" ";
//		cout<<endl;
//		cout<<i<<" "<<j<<" "<<dp[i]<<endl;
//		cout<<l<<" "<<r<<endl;
	}
	ll ans=INF;
	for(int i=maxt;i<maxt+m;i++)ans=MIN(ans,dp[i]);
	cout<<ans;
	return 0;
}

这个程序为什么WA