B. Cobb
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.
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\).
For each test case, print a single integer — the maximum possible value of \(i \cdot j - k \cdot (a_i | a_j)\).
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\).