Загрузка данных


#include <stdio.h>
#include <stdlib.h>

// Функция для сравнения двух чисел (для qsort)
int compare(const void *a, const void *b) {
    long long val1 = *(const long long*)a;
    long long val2 = *(const long long*)b;
    if (val1 < val2) return -1;
    if (val1 > val2) return 1;
    return 0;
}

// Бинарный поиск: первый индекс, где элемент >= target
int lower_bound(long long *arr, int size, long long target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// Бинарный поиск: первый индекс, где элемент > target
int upper_bound(long long *arr, int size, long long target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int main() {
    int n;
    long long k, p;
    
    // Считываем входные данные
    if (scanf("%d %lld %lld", &n, &k, &p) != 3) {
        return 0;
    }

    long long *a = (long long*)malloc(n * sizeof(long long));
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }

    // Сортируем массив
    qsort(a, n, sizeof(long long), compare);

    int max_len = 0;
    int L = 0;

    // Метод двух указателей
    for (int R = 0; R < n; R++) {
        // Сдвигаем левый указатель, пока разница между max и min не станет <= 2p
        while (L <= R && a[R] - a[L] > 2 * p) {
            L++;
        }

        // Проверяем, можно ли уложиться в k изменений
        // Ищем границы допустимого интервала [a[R] - p, a[L] + p]
        long long low_target = a[R] - p;
        long long high_target = a[L] + p;

        // Находим количество элементов в массиве, которые попадают в этот интервал
        int left_idx = lower_bound(a, n, low_target);
        int right_idx = upper_bound(a, n, high_target);
        
        // Количество элементов, которые нужно изменить
        int changes_needed = (R - L + 1) - (right_idx - left_idx);

        if (changes_needed <= k) {
            // Если условие выполнено, обновляем максимальную длину
            int current_len = R - L + 1;
            if (current_len > max_len) {
                max_len = current_len;
            }
        } else {
            // Если изменений слишком много, сдвигаем левый указатель
            L++;
        }
    }

    printf("%d\n", max_len);
    
    free(a);
    return 0;
}