Cobb (Codeforces 1554B)
Tags: Math, bitmasks

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

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

Sample Inputs:
4
3 3
1 1 3
2 2
1 2
4 3
0 1 2 3
6 6
3 2 0 0 5 6

Sample Outputs:
-1
-4
3
12

Solution (Python):
import sys

def II():
    return int(sys.stdin.buffer.readline())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def solve():
    (n, k) = LI()
    a = LI()
    if n <= 101:
        m = -10 ** 12
        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                m = max(m, i * j - k * (a[i - 1] | a[j - 1]))
        return m
    else:
        m = -10 ** 12
        for i in range(n - 101, n + 1):
            for j in range(i + 1, n + 1):
                m = max(m, i * j - k * (a[i - 1] | a[j - 1]))
        return m

def main():
    for _ in range(II()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def II():
    return int(sys.stdin.buffer.readline())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def solve():
    (n, k) = LI()
    a = LI()
    if n <= 101:
        m = -10 ** 12
        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                m = max(m, i * j - k * (a[i - 1] | a[j - 1]))
        return m
    else:
        m = -10 ** 12
        for i in range(n - 101, n + 1):
            for j in range(i + 1, n + 1):
                m = max(m, i * j - k * (a[i - 1] | a[j - 1]))
        return m

def main():
    for _ in range(II()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def solve_tc():
    (n, k) = list(map(int, input().split()))
    a = list(map(int, input().split()))
    ans = float('-inf')
    for i in range(max(0, n - 110), n):
        for j in range(i + 1, n):
            ans = max(ans, (i + 1) * (j + 1) - k * (a[i] | a[j]))
    return ans
t = int(input())
for _ in range(t):
    sys.stdout.write(str(solve_tc()) + '\n')