Convention

import java.io.*;
import java.util.*;
 
public class convention {
	static int N;
	static int numBus;
	static int cap;
	static int[] cow;
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader("convention.in");
		N = in.nextInt();
		numBus = in.nextInt();
		cap = in.nextInt();
		cow = new int[N];
		for (int i = 0; i < N; i++) { cow[i] = in.nextInt(); }
 
		Arrays.sort(cow);
 
		// Cota inferior. Como el tiempo mínimo de espera tiene que estar por debajo
		// de la llegada máxima, la cota superior puede ser el valor más grande del arreglo
		int l = 0;
		int r = cow[cow.length - 1];
		while (l <= r) {
			int mid = (l + r) / 2;
			if (check(mid)) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		PrintWriter out =
		    new PrintWriter(new BufferedWriter(new FileWriter("convention.out")));
		System.out.println(l);
		out.println(l);
		out.close();
	}
	// Calcula el número de buses necesarios para garantizar el minWait. Si
	// es mayor que los buses disponibles, false.
	private static boolean check(int minWait) {
		int first = cow[0];
		int used = 1;
		int curCap = 0;
		for (int i = 0; i < N; i++) {
			if (cow[i] - first > minWait || curCap >= cap) {
				used++;
				curCap = 0;
				first = cow[i];
			}
			curCap++;
		}
		return used <= numBus;
	}
	private static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
 
		public InputReader() {
			try {
				reader = new BufferedReader(new InputStreamReader(System.in), 32768);
			} catch (Exception e) {
				throw new NullPointerException("Could not create input stream");
			}
		}
 
		public InputReader(String fileName) {
			try {
				reader = new BufferedReader(new FileReader(new File(fileName)), 32768);
			} catch (Exception ex) {
				throw new NullPointerException(
				    "Input file does not exist! Put it in the project folder.");
			}
			tokenizer = null;
		}
 
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) { throw new RuntimeException(e); }
			}
			return tokenizer.nextToken();
		}
 
		public boolean hasNextInt() throws IOException { return reader.ready(); }
 
		public int nextInt() { return Integer.parseInt(next()); }
 
		public double nextDouble() { return Double.parseDouble(next()); }
 
		public long nextLong() { return Long.parseLong(next()); }
 
		public char nextChar() { return next().charAt(0); }
 
		/**
		 * Al llamar next(), se salta esa línea entera.
		 * No se hace flush de buffers.
		 * No funciona cuando se quiere escanear el resto de la línea.
		 *
		 * @return la línea entera
		 */
 
		public String nextLine() {
			String str = "";
			try {
				str = reader.readLine();
				tokenizer = null;
			} catch (IOException e) { throw new RuntimeException(e); }
			return str;
		}
	}
}

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
 
using std::endl;
using std::vector;
 
int n, m, c;
vector<int> arrivals;
 
bool validate(int k) {
	int bus = 0;   // número de buses necesarios
	int cow = 0;   // vaca actual
	int lcow = 0;  // vaca más temprana en este bus
 
	while (cow < n) {
		if (cow == lcow) { bus++; }
 
		// no se puede satisfacer la restricción de tiempo al agregar esta vaca
		if (arrivals[cow] - arrivals[lcow] > k) {
			lcow = cow;
			// esta vaca no entra en el bus
		} else if (cow - lcow + 1 == c) {
			lcow = ++cow;
			// agregamos esta vaca al bus actual
		} else {
			cow++;
		}
	}
	return bus <= m;
}
 
int main() {
	freopen("convention.in", "r", stdin);
	freopen("convention.out", "w", stdout);
 
	std::cin >> n >> m >> c;
	arrivals.resize(n);
 
	for (int i = 0; i < n; i++) { std::cin >> arrivals[i]; }
 
	// ordenamos por tiempo de llegada para procesar las vacas en orden
	sort(arrivals.begin(), arrivals.end());
 
	int lo = 0;
	int hi = arrivals[n - 1] - arrivals[0];
 
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
 
		if (validate(mid)) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	std::cout << lo << endl;
}

def validate(k: int) -> bool:
	bus = 0  # número de buses necesarios
	cow = 0  # vaca actual
	lcow = 0  # vaca más temprana en este bus
 
	while cow < n:
		if cow == lcow:
			bus += 1
 
		# no se puede satisfacer la restricción de tiempo al agregar esta vaca
		if arrivals[cow] - arrivals[lcow] > k:
			lcow = cow
 
		# esta vaca no entra en el bus
		elif cow - lcow + 1 == c:
			cow += 1
			lcow = cow
 
		# agregamos esta vaca al bus actual
		else:
			cow += 1
 
	return bus <= m
 
 
with open("convention.in") as read:
	n, m, c = map(int, read.readline().strip().split())
	# ordenamos por tiempos de llegada
	arrivals = sorted(map(int, read.readline().strip().split()))
 
lo = 0
hi = arrivals[n - 1] - arrivals[0]
while lo < hi:
	mid = lo + (hi - lo) // 2
	if validate(mid):
		hi = mid
	else:
		lo = mid + 1
 
print(lo, file=open("convention.out", "w"))