https://www.acmicpc.net/problem/14465

I solved this in $O(N^2)$ with one bigger for loop and partial second for loop.

But there is a solution with $O(N)$ time complexity, which uses partial sum.

I have thought that I donâ€™t have to use this since I was a high school student, but as well as the last SCPC preliminary problem, partial sum substantially reduces the time complexity.

If we assume that the number of malfunctioning traffic lights from $1$ to $i$ is `partialSums[i]`

, the number of broken lights from $i$ to $i+K-1$ is `partialSums[i+K-1] - partialSums[i]`

.

If we initializes `partialSums`

array properly, this is easy approach.

```
#include <iostream>
#include <vector>
using namespace std;
int N, K, B;
vector<int> partialSums;
int main() {
scanf("%d %d %d", &N, &K, &B);
partialSums.assign(N+1, 0);
for (int i=1; i<=B; ++i) {
int input;
scanf("%d", &input);
partialSums[input] = 1;
}
for (int i=0; i<N; ++i) {
partialSums[i+1] += partialSums[i];
}
int count = N;
for (int i=1; i<=N-K+1; ++i) {
if (partialSums[i+K-1] - partialSums[i] <= count) {
count = partialSums[i+K-1] - partialSums[i];
}
}
printf("%d\n", count);
return 0;
}
```

In addition, the process to get partial sums was interesting, which first makes the index of broken light $1$ and adds them sequentially.

I think I learned about it as I was in high school, but maybe I have forgotten it.