i think 2 pointer technique can work, move our right pointer till we utilised all k, and then move left pointer to the right until k become > 0 , then again move the right point till k gets exause,make continuous movements of both the pointers and each time keep track of max answer ? is this approach correct ?

It was a good implementation question. I stored all the segments of consecutive 0's in an vector and after doing this iteratively pick consecutive k segments of 0's and make them 1 and then check the answer . this is a greedy approach for this. Link to my submission https://atcoder.jp/contests/abc124/submissions/4954185 Hope it helps

Hi,

I solved this question with $$$2$$$-pointer sliding window technique.

I created two arrays $$$Z$$$ and $$$O$$$, where $$$Z[i]$$$ denotes the length of the $$$i$$$-th segment of $$$0$$$s and $$$O[i]$$$ denotes the length of the $$$i$$$-th segment of $$$1$$$s. Suppose I am flipping $$$Z[L], Z[L + 1], \dots , Z[R]$$$

What is the resulting length of the segment of $$$1$$$s ? If we are flipping $$$K$$$ $$$0$$$-segments, then we must add the $$$(K - 1)$$$ $$$1$$$-segments in between and the $$$2$$$ $$$1$$$-segments at each end. (Totally $$$(K + 1)$$$ $$$1$$$-segments.)

The number of $$$1$$$ s is either $$$(O[L - 1] + Z[L] + O[L] + \dots + O[R] + Z[R])$$$ or $$$(Z[L] + O[L] + \dots + O[R] + Z[R] + O[R + 1])$$$ depending on whether the first segment is a $$$1$$$-segment or a $$$0$$$-segment.

• I checked every set of $$$K$$$ consecutive $$$0$$$ segments and the one that maximises the number of $$$1$$$'s is the answer.

Here is my explanation and code. I have added a lot more details here.

See my solution in case you need help https://atcoder.jp/contests/abc124/submissions/15330027