#include<bits/stdc++.h>
using namespace std;
int n;
int lim;
int a[200005];
namespace sub12567
{
long long dp[5005][5005];
void solve()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=5000;j++)
dp[i][j]=1e18;
for(int i=0;i<=5000;i++)dp[1][i]=abs(a[1]-i);
for(int i=2;i<=n;i++)
{
deque<int>dq;
int dd=0;
for(int j=0;j<=5000;j++)
{
int l=max(0,j-lim),r=min(5000,j+lim);
while(dd<=r)
{
while(dq.size()&&dp[i-1][dq.back()]>=dp[i-1][dd])dq.pop_back();
dq.push_back(dd);
dd++;
}
while(dq.size()&&dq.front()<l)dq.pop_front();
if(dq.size())dp[i][j]=dp[i-1][dq.front()]+abs(a[i]-j);
}
}
long long ans=1e18;
for(int i=0;i<=5000;i++)ans=min(ans,dp[n][i]);
cout<<ans;
}
}
namespace sub4
{
pair<long long,int>tree[200005];
void upd(int id,long long val,int cnt)
{
while(id<=n){tree[id].first+=val;tree[id].second+=cnt;id+=(id&(-id));}
}
pair<long long,int>get(int id)
{
pair<long long,int>ans={0,0};
while(id>0){ans.first+=tree[id].first;ans.second+=tree[id].second;id-=(id&(-id));}
return ans;
}
void solve()
{
vector<int>vec;
for(int i=1;i<=n;i++)vec.push_back(a[i]);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int i=1;i<=n;i++)
{
int k=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()+1;
upd(k,a[i],1);
}
long long ans=1e18;
for(int i=1;i<=n;i++)
{
long long sum=0;
int k=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()+1;
pair<long long,int>vv=get(k);
sum+=1LL*vv.second*a[i]-vv.first;
vv={get(n).first-vv.first,get(n).second-vv.second};
sum-=1LL*vv.second*a[i]-vv.first;
ans=min(ans,sum);
}
cout<<ans;
}
}
int maxx=0;
int main()
{
//freopen("safety.inp","r",stdin);
//freopen("safety.out","w",stdout);
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>lim;
for(int i=1;i<=n;i++){cin>>a[i];maxx=max(maxx,a[i]);}
if(n<=5000&&maxx<=5000){sub567::solve();return 0;}
if(lim==0){sub4::solve();return 0;}
return 0;
}
Compilation message
safety.cpp: In function 'int main()':
safety.cpp:85:25: error: 'sub567' has not been declared
85 | if(n<=5000&&maxx<=5000){sub567::solve();return 0;}
| ^~~~~~
