Background

I am a ghost.
Through the city of sorrow, I fled in panic.
Through eternal misery, I flew far away.

Along the bank of the Arno River, I ran wildly, panting... I turned left onto Via dei Castellani and kept heading north, staying hidden under the shadow of the Uffizi Gallery.

But they still would not let me go.

Their footsteps grew louder and louder. These pursuers were cold and ruthless, and they would not stop until they achieved their goal.

For so many years, they have been following me. They never gave up, so I could only live underground... forced to stay in Purgatory... like a demon of the underworld, suffering the torment of hell at every moment.

I am a ghost.

Now in this floating world, I look north, but I cannot see any shortcut to salvation—the towering Apennines block the first ray of dawn.

Problem Description

After Robert Langdon washed the acrylic plaster off Dante’s death mask, he found a line of words on the back:

O you who have steady wisdom,
Please pay attention to the meaning here,
Hidden beneath the veil of an obscure sequence.

Below it, there is a sequence of length $n$ consisting of $1$ and $-1$. The mask has been worn away by time, and some numbers in the sequence have become blurred. Fortunately, there are two clues given under the mask:

You may fill the blank positions with $k$ number of $1$, and fill the rest with $-1$. You need to maximize the maximum subarray sum of this sequence.

The maximum subarray sum of a sequence is defined as the maximum sum over any continuous interval. Formally, for a sequence $a$, its maximum subarray sum is $\max\limits_{l=1}^n\max\limits_{r=l}^n\left(\sum\limits_{i=l}^r a_i\right)$.

Robert Langdon hopes to find the relevant clue before the plague spreads. So he came to you.

Formal Statement

Given a sequence containing only $-1,0,1$, fill $k$ of the positions with value $0$ with $1$, and fill the rest with $-1$. Find the maximum possible value of the maximum subarray sum after filling.

Input Format

The first line contains two positive integers $n,k$.

The next line contains $n$ integers $a_i\in\{-1,0,1\}$, where $0$ means the number is blurred.

Output Format

Output one positive integer in one line, indicating the maximum possible maximum subarray sum.

5 2
1 0 -1 0 0

2

Hint

Sample Explanation

One feasible plan is to fill as $\{1,1,-1\}$, and the maximum subarray sum is $2$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le n,k\le10^7$, $a_i\in \{-1,0,1\}$. It is guaranteed that $k\le$ the number of $0$ in the sequence.

The official solution uses optimized input/output. With O2 optimization, the largest test takes about $350$ ms, which is enough to pass. If you believe your algorithm complexity is correct but you exceed the time limit, please use faster input/output methods or optimize constant factors.

Translated by ChatGPT 5