#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'
const int k = 5000;
inline void solve(){
int n, h;
cin>>n>>h;
int a[n];
for(int i=0; i<n; i++) cin>>a[i];
int dp[n][k+1];
for(int j=0; j<=k; j++) dp[0][j] = abs(a[0] - j);
for(int i=1; i<n; i++){
deque<pair<int,int>> dq;
for(int j=0; j<=min(h, k); j++){
while(!dq.empty() and dq.back().second >= dp[i-1][j]) dq.pop_back();
dq.push_back({j, dp[i-1][j]});
}
dp[i][0] = dq.front().second + a[i];
for(int j=1; j<=k; j++){
if(dq.front().first == j-h-1) dq.pop_front();
if(j+h <= k){
while(!dq.empty() and dq.back().second >= dp[i-1][j+h]) dq.pop_back();
dq.push_back({j+h, dp[i-1][j+h]});
}
dp[i][j] = dq.front().second + abs(a[i] - j);
}
}
int ans = inf;
for(int j=0; j<=k; j++) ans = min(ans, dp[n-1][j]);
cout<<ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |