B - Sum AND Subarrays Editorial /

Time Limit: 2.525 sec / Memory Limit: 1024 MB

配点 : 400 点

問題

ある日、ドワンゴ社員のニワンゴくんは、長さ N の整数列 (a_1, ..., a_N) を見つけました。ニワンゴくんは、数列 a の性質に興味を持っています。

数列 a の空でない連続する部分列 a_l, ..., a_r (1 \leq l \leq r \leq N) の 美しさ は、 a_l + ... + a_r と定義されます。ニワンゴくんは、ありうる N(N+1)/2 個の空でない連続する部分列のうち、 K 個を選んで取ってきて、それらの美しさのビット毎の論理積 (AND) を計算したとき、その最大値がどうなるかを知りたがっています (取ってくる部分列の間で重複する要素があっても構いません)。

彼の代わりに最大値を求めてください。

制約

  • 2 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9
  • 1 \leq K \leq N(N+1)/2
  • 入力として与えられる数値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N K
a_1 a_2 ... a_N

出力

答えを出力せよ。

入力例 1

4 2
2 5 2 5

出力例 1

12

異なる空でない連続する部分列は 10 個存在します。全列挙すると、

  • 1 番目から始まるもの: \{2\}, \{2, 5\}, \{2, 5, 2\}, \{2, 5, 2, 5\}
  • 2 番目から始まるもの: \{5\}, \{5, 2\}, \{5, 2, 5\}
  • 3 番目から始まるもの: \{2\}, \{2, 5\}
  • 4 番目から始まるもの: \{5\}

です (数列の要素が同じでも、異なる添字から始まる列は異なるものとみなすことに注意してください)。

このうち異なる 2 個の部分列の美しさのビット毎の論理積 (AND) として得られる値の最大値は 12 です。 これは \{5, 2, 5\} (美しさ 12) と \{2, 5, 2, 5\} (美しさ 14) を選んだ時に達成できます。

入力例 2

8 4
9 1 8 2 7 5 6 4

出力例 2

32

Score : 400 points

Problem Statement

One day, Niwango-kun, an employee of Dwango Co., Ltd., found an integer sequence (a_1, ..., a_N) of length N. He is interested in properties of the sequence a.

For a nonempty contiguous subsequence a_l, ..., a_r (1 \leq l \leq r \leq N) of the sequence a, its beauty is defined as a_l + ... + a_r. Niwango-kun wants to know the maximum possible value of the bitwise AND of the beauties of K nonempty contiguous subsequences among all N(N+1)/2 nonempty contiguous subsequences. (Subsequences may share elements.)

Find the maximum possible value for him.

Constraints

  • 2 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9
  • 1 \leq K \leq N(N+1)/2
  • All numbers given in input are integers

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N

Output

Print the answer.

Sample Input 1

4 2
2 5 2 5

Sample Output 1

12

There are 10 nonempty contiguous subsequences of a. Let us enumerate them:

  • contiguous subsequences starting from the first element: \{2\}, \{2, 5\}, \{2, 5, 2\}, \{2, 5, 2, 5\}
  • contiguous subsequences starting from the second element: \{5\}, \{5, 2\}, \{5, 2, 5\}
  • contiguous subsequences starting from the third element: \{2\}, \{2, 5\}
  • contiguous subsequences starting from the fourth element: \{5\}

(Note that even if the elements of subsequences are equal, subsequences that have different starting indices are considered to be different.)

The maximum possible bitwise AND of the beauties of two different contiguous subsequences is 12. This can be achieved by choosing \{5, 2, 5\} (with beauty 12) and \{2, 5, 2, 5\} (with beauty 14).

Sample Input 2

8 4
9 1 8 2 7 5 6 4

Sample Output 2

32