PROG-T1107: Jump

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;

int period[N + 1], sorted[N + 1], nPeriod, mxJump, mxCons;

bool canSkip(int x){
    int cnt = 0;
    int classCnt = 0;
    bool isSkipping = false;

    for(int i = 1; i <= nPeriod; ++i){
        if(period[i] > x && !isSkipping){
            ++cnt;
            isSkipping = true;
            ++classCnt;
            if(classCnt == mxCons){
                isSkipping = false;
                classCnt = 0;
            }
        } else if(isSkipping){
            ++classCnt;
            if(classCnt == mxCons){
                isSkipping = false;
                classCnt = 0;
            }
        }
    };

    if(cnt > mxJump){
        return false;
    }
    return true;
}

int main(){

    scanf("%d%d%d", &nPeriod, &mxJump, &mxCons);
    int mx = 1;
    for(int i = 1; i <= nPeriod; ++i){
        scanf("%d", &period[i]);
        sorted[i] = period[i];
        mx = max(mx, period[i]);
    }
    sort(sorted + 1, sorted + nPeriod + 1);

    int l = 1;
    int r = nPeriod;
    int ans = mx;
    while(l <= r){
        int m = (l + r) / 2;
        if(canSkip(sorted[m])){
            ans = min(ans, sorted[m]);
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    cout << ans;

    return 0;
}