#include<bits/stdc++.h>
#define int long long
using namespace std;
pair<int,int>dp[200005][2];
int ar[200005];
int inf=1e12;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>ar[i];
ar[0]=inf;
dp[0][0]={0,m};
dp[0][1]={-inf,0};
for(int i=1;i<=n;i++)dp[i][0]=dp[i][1]={-inf,inf};
for(int i=1;i<=n;i++){
//0 0
if(ar[i]<=dp[i-1][0].second)dp[i][0]=max(dp[i][0],{dp[i-1][0].first,ar[i]+m});
//1 0
if(ar[i]<=dp[i-1][1].second)dp[i][0]=max(dp[i][0],{dp[i-1][1].first,ar[i]+m});
//0 1
dp[i][1]=max(dp[i][1],{dp[i-1][0].first-1,dp[i-1][0].second+m});
//1 1
dp[i][1]=max(dp[i][1],{dp[i-1][1].first-1,dp[i-1][1].second+m});
}
int ans=min(-dp[n][0].first,-dp[n][1].first);
cout<<ans;
}
# | 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... |