#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
const ll mod = 1000000007;
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int main(){
fastio();
ll n, m, arr[200005], cnt = 0, sec[200005], th[200005];
cin >> n >> m;
for (ll i = 1; i <= n; i++){
cin >> arr[i];
sec[i] = arr[i];
th[i] = arr[i];
}
//case 1 : seadanya
if (arr[1] > m){
cnt++;
arr[1] = m;
}
for (ll i = 2; i <= n - 1; i++){
if (arr[i + 1] - arr[i - 1] <= m * 2 && ((arr[i + 1] - arr[i] > m) || (arr[i] - arr[i - 1] > m))){
arr[i] = arr[i - 1] + m;
cnt++;
}
else if ((arr[i + 1] - arr[i - 1] > m * 2) && (arr[i] - arr[i - 1]) > m){
arr[i] = arr[i - 1] + m;
cnt++;
}
}
if (arr[n] - arr[n - 1] > m) cnt++;
//case 2 : maximalin yang pertama dulu
ll cnt2 = 1e9;
if (sec[1] < m){
cnt2 = 0;
sec[1] = m;
cnt2++;
for (ll i = 2; i <= n - 1; i++){
if (sec[i + 1] - sec[i - 1] <= m * 2 && ((sec[i + 1] - sec[i] > m) || (sec[i] - sec[i - 1] > m))){
sec[i] = sec[i - 1] + m;
cnt2++;
}
else if ((sec[i + 1] - sec[i - 1] > m * 2) && (sec[i] - sec[i - 1]) > m){
sec[i] = sec[i - 1] + m;
cnt2++;
}
}
}
cout << min(cnt, cnt2) << endl;
}
# | 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... |