Submission #1201074

#TimeUsernameProblemLanguageResultExecution timeMemory
1201074samuelandrianoo_Rabbit Carrot (LMIO19_triusis)C++20
0 / 100
3 ms5136 KiB
#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++;
            }
        }
    }

    //case 3 : awal sudah mencukupi pas
    ll cnt3 = 1e9;
        if (th[1] == m){
            cnt3 = 0;

            for (ll i = 2; i <= n - 1; i++){
                if (th[i + 1] - th[i - 1] <= m * 2 && ((th[i + 1] - th[i] > m) || (th[i] - th[i - 1] > m))){
                    th[i] = th[i - 1] + m;
                    cnt3++;
                }
                else if ((th[i + 1] - th[i - 1] > m * 2) && (th[i] - th[i - 1]) > m){
                    th[i] = th[i - 1] + m;
                    cnt3++;
                }
            }
            if (th[n] - th[n - 1] > m) cnt3++;
        }

    

   cout << min({cnt, cnt2, cnt3}) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...