[EC Final 2022] Dining Professors

Luogu

IDLGP9728

Time1000ms

Memory256MB

DifficultyP3

贪心2022O2优化ICPCEC Final

Prof. Pang invited $n$ professors to his banquet. The professors sit at a round table. For all $i$ from $1$ to $n$, professor $i$ sits adjacent to professor $(i \bmod n) + 1$ and $((i + n - 2)\bmod n) + 1$. Prof. Pang prepared $n$ dishes. There are $n$ positions on the table. Position $i$ is in front of professor $i$. Professor $i$ can access only the dishes placed at positions $i$, $(i \bmod n) + 1$, and $((i + n - 2)\bmod n) + 1$. Prof. Pang will place exactly one dish at each position. Among the dishes, $a$ of them are spicy and $n-a$ of them are not spicy. Some (possibly $0$) professors are unable to have spicy food. If a professor can have spicy food, his/her **satisfaction level** is the number of dishes (no matter spicy or not) he/she can access. If a professor cannot have spicy food, his/her satisfaction level is the number of not spicy dishes he/she can access. Prof. Pang knows whether each professor can have spicy food or not. Please help him to arrange the dishes on the table so that the sum of satisfaction levels over all the professors is maximized. Output the maximum sum. ## Input The first line contains two integers $n, a$ ($3\le n\le 10^5, 0\le a\le n$). The second line contains $n$ integers $b_1, \ldots, b_n$. $b_i$ is $0$ or $1$. $b_i=1$ means professor $i$ can have spicy food. $b_i=0$ means professor $i$ cannot have spicy food. ## Output Output one integer representing the answer in one line. [samples]

Samples

Input #1

5 2
1 0 1 0 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[EC Final 2022] Dining Professors",
    "description": {
      "content": "Prof. Pang invited $n$ professors to his banquet. The professors sit at a round table. For all $i$ from $1$ to $n$, professor $i$ sits adjacent to professor $(i \\bmod n) + 1$ and $((i + n - 2)\\bmod n)",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9728"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Prof. Pang invited $n$ professors to his banquet. The professors sit at a round table. For all $i$ from $1$ to $n$, professor $i$ sits adjacent to professor $(i \\bmod n) + 1$ and $((i + n - 2)\\bmod n)...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments