Freight Train

#include <iostream>
#include <vector>

void solve() {
	int n, w, l;
	std::cin >> n >> w >> l;
	std::vector<int> move;
	int prev = 0;
	for (int i = 0; i < w; ++i) {
		int ind;
		std::cin >> ind;
		if (ind - prev - 1 > 0) {
			move.push_back(-(ind - prev - 1));
		}
		move.push_back(ind);
		prev = ind;
	}
	if (prev != n) {
		move.push_back(prev - n);
	}
	// binary search answer
	int low = 1;
	int high = n;
	while(low != high) {
		int mid = (low + high) / 2;
		std::vector<int> clone;
		for (int i = move.size() - 1; i >= 0; --i) {
			clone.push_back(move[i]);
		}
		int used = 0;
		while(! clone.empty()) {
			++used;
			if (clone.back() < -mid) {
				clone.pop_back();
			} else {
				int left = mid;
				while((! clone.empty()) && (left > 0)) {
					int next = clone.back();
					if (next < 0) {
						left += next;
						if (left >= 0) {
							clone.pop_back();
						} else {
							clone.back() = left;
							break;
						}
					} else {
						--left;
						clone.pop_back();
					}
				}
			}
		}
		if (used <= l) {
			high = mid;
		} else {
			low = mid + 1;
		}
	}
	std::cout << low << '\n';
}

int main() {
	int T;
	std::cin >> T;
	for (int i = 0; i < T; ++i) {
		solve();
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED