Sum AND Subarrays

AtCoder

IDdwacon5th_prelims_b

Time2525ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

4 2
2 5 2 5

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$).

Input #2

8 4
9 1 8 2 7 5 6 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Sum AND Subarrays",
    "description": {
      "content": "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 subseque",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2525,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "dwacon5th_prelims_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$.\nFor a nonempty contiguous subseque...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments