Official Analysis (C++)

Explanation

We can represent this problem as an array $a$ of $N$ signals, such that the $i$-th signal is $0$ if it is working and $1$ if it is not working. Now we need to find a subarray of length $K$ with the least number of $1$s (i.e., the least sum).

We can use prefix sums to find the number of $1$s (broken signals) across all subarrays of length $K$ and then take the minimum.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
with open("maxcross.in") as read:
	n, k, b = [int(i) for i in read.readline().split()]

	signals = [0 for _ in range(n)]
	for _ in range(b):
		signals[int(read.readline()) - 1] += 1

# prefix sums precomputation
pref_sum = [0]
for i in range(n):