P11068 "QMSOI R1" Spinning Stairs

The problem statement itself is the best background ().

Students do exercises every day, and they will pass through the spinning stairs. The spinning stairs has $n+1$ steps. For step $i \ (1\le i\le n+1)$, it has a spinning value $a_i$, where $a_i\in\{0,1\}$. In particular, $a_{n+1}=0$. For a step $i$, if the spinning value of the next step is the same as it (that is, $a_{i+1}=a_i$), then we can walk down directly, costing $1$ second. Otherwise, we need to spend $1$ second to spin once to change the spinning value of the current step to $1-a_i$, and then spend another $1$ second to walk down. We need to do exercises for $k$ days. Every day, we walk from step $1$ to step $n+1$. Please compute the total time for these $k$ days that students spend on the spinning stairs.

The input has $2$ lines. The first line contains two numbers $n$ and $k$. The second line contains $n$ integers. The $i \ (1\leq i\leq n)$-th number represents $a_i$.

Output one integer in one line, representing the total time spent on the spinning stairs over these $k$ days.

### Sample Explanation On the first day, the sequence is $a=\{0,1,0\}$. We walk $3$ steps and spin $2$ times, so the time is $5$. On the second day, the sequence is $a=\{1,0,0\}$. We walk $3$ steps and spin $1$ time, so the time is $4$. ### Constraints **This problem uses subtasks for bundled judging**. The score for each subtask is as follows: | Subtask | Range | Score | | :----------: | :----------: | :----------: | | $0$ | $1\le n,k\le 2\times 10^3$ | $30$ | | $1$ | $1\le n,k\le 2\times 10^6$ | $70$ | For all data, $1\le n,k\le2\times10^6$ and $a_i\in\{0,1\}$. Translated by ChatGPT 5