P1564 Worship

There are many top students… of course… each student has someone they sincerely admire. At a certain school there are two top students, A and B. The newly enrolled $n$ students have already heard of their legends, so each student already sincerely worships one of them. Now the teacher needs to assign them to computer labs. For each lab, either everyone in that lab worships the same top student, or the absolute difference between the counts of the two worshippers does not exceed $m$. The $n$ students stand in a line, and the teacher will only assign a contiguous segment of students to the same lab. The teacher wants to know the minimum number of labs needed.

The first line contains two integers $n$ and $m$. Lines $2$ through $(n + 1)$ each contain an integer, either $1$ or $2$. The integer on line $(i + 1)$ indicates whom the $i$-th student worships: $1$ means A, $2$ means B.

Output a single integer, the minimum number of labs required.

Constraints - For $30\%$ of the testdata, it is guaranteed that $1 \le n \le 50$, $0 \le m \le 50$. - For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 2500$, $0 \le m \le 2500$. Translated by ChatGPT 5