409979: GYM103886 F Cereal Schemes

The CerealCodes gift shop contains a row of $$$n$$$ boxes of cereal. The $$$i$$$-th box contains $$$c_i$$$ pieces of cereal.

Unfortunately, one group of competitors has thought up a scheme to buy all of the cereal!

The group consists of $$$k$$$ members. They will divide the row of cereal into $$$k$$$ non-empty contiguous subsegments, and the $$$i$$$-th member will buy all the cereal boxes in the $$$i$$$-th subsegment.

Say that the $$$i$$$-th subsegment consists of all cereal boxes from $$$l_i$$$ to $$$r_i$$$. Then the smugness of the $$$i$$$-th competitor is $$$s_i = c_{l_i} | c_{l_i + 1} | \ldots | c_{r_i - 1} | c_{r_i}$$$.

The overall sadistic satisfaction the members feel (at the humiliation of CerealCodes) is equal to $$$s_1 \& s_2 \& \ldots \& s_{k-1} \& s_k$$$.

What is the maximum possible satisfaction that the group could feel as a result of this scheme?

Here, $$$|$$$ and $$$\&$$$ denote the bitwise OR and bitwise AND operations respectively.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

The next line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).

Output the maximum satisfaction the group can feel.

6 2
10 4 3 1 8 7

15

Here is one plan that maximizes the humiliation:

• Member $$$1$$$ buys the subsegment $$$[1, 3]$$$, and has smugness $$$10 | 4 | 3 = 15$$$.
• Member $$$2$$$ buys the subsegment $$$[4, 6]$$$, and has smugness $$$1 | 8 | 7 = 15$$$.

The total satisfaction is equal to $$$15 \& 15 = 15$$$.

Problem Credits: Agastya Goel