Cobb
Contest: Codeforces Round 735 (Div. 2)
Difficulty rating: 1700
Tags: bitmasks, brute force, greedy, math

You are given $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$k$$$. Find the maximum value of $$$i \cdot j - k \cdot (a_i | a_j)$$$ over all pairs $$$(i, j)$$$ of integers with $$$1 \le i < j \le n$$$. Here, $$$|$$$ is the bitwise OR operator.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$)  — the number of test cases.

The first line of each test case contains two integers $$$n$$$ ($$$2 \le n \le 10^5$$$) and $$$k$$$ ($$$1 \le k \le \min(n, 100)$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print a single integer  — the maximum possible value of $$$i \cdot j - k \cdot (a_i | a_j)$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Let $$$f(i, j) = i \cdot j - k \cdot (a_i | a_j)$$$.

In the first test case,

- $$$f(1, 2) = 1 \cdot 2 - k \cdot (a_1 | a_2) = 2 - 3 \cdot (1 | 1) = -1$$$.
- $$$f(1, 3) = 1 \cdot 3 - k \cdot (a_1 | a_3) = 3 - 3 \cdot (1 | 3) = -6$$$.
- $$$f(2, 3) = 2 \cdot 3 - k \cdot (a_2 | a_3) = 6 - 3 \cdot (1 | 3) = -3$$$.

So the maximum is $$$f(1, 2) = -1$$$.

In the fourth test case, the maximum is $$$f(3, 4) = 12$$$.

Example input:
4
3 3
1 1 3
2 2
1 2
4 3
0 1 2 3
6 6
3 2 0 0 5 6

Example output:
-1
-4
3
12

Editorial:
Let $$$f(i, j) = i \cdot j - k \cdot (a_i | a_j)$$$ for $$$i < j$$$.
Do we really need to check all pairs?
The value of $$$k$$$ is small, which is suspicious. There must be something revolving around it. What can that be?
In the equation, $$$i \cdot j$$$ can be $$$\mathcal{O}(n^2)$$$, but $$$k \cdot (a_i | a_j)$$$ is $$$\mathcal{O}(n \cdot 100)$$$. That means the value of $$$f(i, j)$$$ must be larger for bigger $$$i, j$$$. Can you deduce something from this?
What is the smallest $$$i$$$ which can contribute to the result($$$f(i, j): i < j$$$ is the maximum)? Pause and think. Hint: try to maximize $$$f(i, j)$$$ and minimize the heaviest pair, that is, $$$f(n - 1, n)$$$, and compare them.
Let's find it. What is the maximum possible value of a pair containing $$$i$$$?. It's when $$$i$$$ pairs with $$$n$$$ and $$$a_i = a_n = 0$$$. So, $$$f(i, n) = i \cdot n - k \cdot 0 = i \cdot n$$$.
What is the minimum possible value of the heaviest pair $$$f(n - 1, n)$$$? It's when $$$a_{n - 1} | a_n$$$ is maximum. And, since $$$0 \le a_i \le n$$$, the maximum possible of value any $$$a_i | a_j$$$ is $$$\le 2n$$$. So $$$f(n - 1, n) = (n - 1) \cdot n - k \cdot 2n = n^2 - 2kn - n$$$.
For $$$i$$$ to contribute to the result, $$$f(i, n)$$$ must be $$$\gt f(n - 1, n)$$$. And, when $$$f(i, n) \gt f(n - 1, n)$$$, then $$$i \cdot n \gt n^2 - 2kn - n$$$, or $$$i \gt n - 2k -1$$$. So any of $$$f(i, j)$$$ such that $$$i < n - 2k$$$ won't generate a value greater than $$$f(n - 1, n)$$$!. This indicates us that we just have to check the pairs $$$f(i, j)$$$ such that $$$i, j \ge n - 2k$$$. And, there are only $$$\mathcal{O}(k^2)$$$ such pairs, so we can brute-force.
We have also allowed $$$\mathcal{O}(n \cdot k)$$$ solutions to pass i.e. brute-forcing over all pairs such that $$$1 \le i \le n $$$ and $$$n - 2k \le j \le n$$$.
Time Complexity: $$$\mathcal{O}(k^2)$$$