50pts 球条玄关

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
const ll INF = 1e18;
ll n, k, d, a[N], dp[N], tr[N * 4];
void upd(int u, int l, int r, int p, ll v){
    if(l == r){tr[u] = v; return;}
    int m = (l + r) / 2;
    if(p <= m) upd(u * 2, l, m, p, v);
    else upd(u * 2 + 1, m + 1, r, p, v);
    tr[u] = min(tr[u * 2], tr[u * 2 + 1]);
}
ll que(int u, int l, int r, int ql, int qr){
    if(ql > qr) return INF;
    if(ql <= l && r <= qr) return tr[u];
    int m = (l + r) / 2;
    ll res = INF;
    if(ql <= m) res = min(res, que(u * 2, l, m, ql, qr));
    if(qr > m) res = min(res, que(u * 2 + 1, m + 1, r, ql, qr));
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> d;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = 0; i < N * 4; i++) tr[i] = INF;
    upd(1, 0, n, 0, 0);
    for(int i = 1; i <= n; i++){
        ll low = a[i] - (ll)(k-1) * d;
        int pos = lower_bound(a + 1, a + n + 1, low) - a;
        int L = max(0, max(pos - 1, i - (int)k));
        int R = i - 1;
        ll mn = que(1, 0, n, L, R);
        dp[i] = mn + 1;
        upd(1, 0, n, i, dp[i]);
    }
    cout << dp[n] * k - n << endl;
    return 0;
}