Description

Behaviors and Definitions of People

A person is either in the grinding state or in the slacking state. If they are not grinding, then they are slacking; if they are not slacking, then they are grinding.

In this problem, we consider there are four types of people:

1. Eternal grinder. An eternal grinder is always in the grinding state at any time.

2. Eternal slacker. An eternal slacker is always in the slacking state at any time.

3. Temporary grinder. If at some second a temporary grinder is in the grinding state and both neighbors are in the slacking state, then in the next second their state updates to slacking. If at some second a temporary grinder is in the slacking state and at least one neighbor is in the grinding state, then in the next second their state updates to grinding. In short: if there is grinding nearby, then grind.

4. Temporary slacker. If at some second a temporary slacker is in the slacking state and both neighbors are in the grinding state, then in the next second their state updates to grinding. If at some second a temporary slacker is in the grinding state and at least one neighbor is in the slacking state, then in the next second their state updates to slacking. In short: if there is slacking nearby, then slack.

We call a temporary grinder in the grinding state a grinding temporary grinder, and a temporary grinder in the slacking state a slacking temporary grinder. Similarly, we call a temporary slacker in the grinding state a grinding temporary slacker, and a temporary slacker in the slacking state a slacking temporary slacker.

We call eternal grinders and eternal slackers eternal people, and temporary grinders and temporary slackers temporary people.

Problem Description After Definitions

There are $n$ people sitting in a row. The leftmost is person $1$, and the rightmost is person $n$.

Initially, person $i$ is given as type $a_i$. It is guaranteed that $a_i\in \{1,2,3,4\}$ and $a_1,a_n\in\{1,2\}$ (these four indices are as described above), i.e., person $1$ and person $n$ are both eternal people. It is guaranteed that between any two eternal people of the same type, there exists at least one other eternal person. That is, if you only look at the eternal people, eternal grinders and eternal slackers appear alternately.

Each person in this row has a state, forming a state configuration. A state configuration is stable if and only if in the next second no one updates their state. The grind count of a state configuration is the number of people in the grinding state (eternal grinders, grinding temporary slackers, and grinding temporary grinders are in the grinding state).

The best state configuration of this row is a stable state configuration whose grind count is the maximum among all stable state configurations (that is, you may choose the initial states arbitrarily). The excellence level of this row is defined as the grind count of the best state configuration.

The teacher thinks they are too weak not excellent enough. Since eternal grinders do not need to be swapped, and eternal slackers are beyond saving, the teacher asks you to swap at most $k$ pairs of temporary people. Find the maximum possible excellence level after swapping.

Input Format

The first line contains two integers $n$ and $k$.

The second line contains $n$ integers, where the $i$-th integer indicates that person $i$ is of type $a_i$.

Output Format

Output one integer in one line, the maximum possible excellence level after swapping at most $k$ pairs of temporary people.

8 3
1 3 3 2 4 3 4 1

7

Hint

Sample $1$ Explanation

Swap person $5$ and person $6$. Then the excellence level is $7$ (persons $1,2,3,5,6,7,8$ are in the grinding state).

Data Scale and Constraints

This problem uses bundled testdata.

• Subtask 1 (30 points): $1\leq k\leq2$, $n=9$.
• Subtask 2 (20 points): Only person $1$ and person $n$ are eternal people, $k>0$.
• Subtask 3 (10 points): $k = 0$.
• Subtask 4 (40 points): No special restrictions.

For $100\%$ of the testdata, $a_i\in \{1,2,3,4\}$, $a_1,a_n\in\{1,2\}$, $4 \le n \leq 2\times10^6$, $0\le k \le 2\times 10^6$.

Hint

The testdata of Subtask 4 has been strengthened multiple times, and there are $62$ test points in total.

Translated by ChatGPT 5