Chef and Bitwise OR Operation
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef studies very well in his University. There is only one professor who doesn't want to give him the highest grade, A. Chef has had a long argument with him, and eventually they agreed, that if Chef solves an algorithmic problem, he gets the highest grade. After looking at the problem, he realized he can't solve it. Once again, he approached Codechef admins for help, and once again we decided to put it off and pass on the task to you. Please, help him (and us)!
You are given an array A of integers and an integer K. Your goal is to divide the array into K consecutive disjoint non-empty groups, so that any array element belongs to exactly one group.
Each group can be specified by two integers L and R (L ≤ R) with the meaning that the group contains all the elements from the Lth to the Rth one (both inclusive) in the given array. The cost of such a group equals to the value of bitwise OR of all elements in the group.
The cost of array for some particular group division equals to the sum of costs for all the groups. You have to find the maximal achievable cost of the given array.
You can read more about bitwise OR operation here
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N and K denoting the number of elements in the array and number of groups, respectively.
The second line contains N space-separated integers A1, A2, ..., AN denoting the given array.
For each test case, output a single line, containing the maximal achievable cost of the array.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 5000
- 1 ≤ K ≤ N
- 0 ≤ Ai ≤ 230
- Subtask 1(15 points): 1 ≤ N ≤ 100
- Subtask 2(35 points): 1 ≤ N ≤ 1000
- Subtask 3(50 points): 1 ≤ N ≤ 5000
- The time limit for the first and the second subtask is 1 second. The time limit for the third subtask is 10 seconds.
Input: 4 3 2 1 2 2 4 3 1 2 3 4 2 2 1 2 11 4 66 152 7 89 42 28 222 69 10 54 99 Output: 5 10 3 704
Example case 1. The optimal group division is the following one: put the first two numbers to the first group, and the next one into the second. This way, you will obtain the cost of the array equal to (1 OR 2) + 2 = 3 + 2 = 5.
Example case 2. The first two integers should be in the first group, the third one should be in the second group, the fourth one should be in the third group. This way, we will obtain a cost of an array equal to (1 OR 2) + 3 + 4 = 3 + 3 + 4 = 10.
Example case 3. Each number will be in its' own group. So, we obtain a cost of 1 + 2 = 3.
Example case 4. Try to figure out yourself.
|Tags||dynamic-programming, easy-medium, furko, ltime25|
|Time Limit:||1 - 10 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.