Day 17 B. Cobb

Day 17 B. Cobb

Problem:
You are given n integers a1,a2,…,an and an integer k. Find the maximum value of i⋅j−k⋅(ai | aj) over all pairs (i,j) of integers with 1≤i<j≤n.

Input
The first line contains a single integer t (1≤t≤10000) — the number of test cases.

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

The second line of each test case contains n integers a1,a2,…,an (0≤ai≤n).

It is guaranteed that the sum of n over all test cases doesn’t exceed 3⋅10^5.

Output
For each test case, print a single integer — the maximum possible value of i⋅j−k⋅(ai | aj).

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

output
-1
-4
3
12

Note
Let f(i,j)=i⋅j−k⋅(ai | aj).

In the first test case,

f(1,2)=1⋅2−k⋅(a1 | a2)=2−3⋅(1|1)=−1.
f(1,3)=1⋅3−k⋅(a1 | a3)=3−3⋅(1|3)=−6.
f(2,3)=2⋅3−k⋅(a2 | a3)=6−3⋅(1|3)=−3.
So the maximum is f(1,2)=−1.

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

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<set>
#include<vector>
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
int t, n, k, a[100005];
int main()
{cin >> t;while (t--){cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];}ll ans = -1e9;for (int i = max(1, n - 105); i <= n; i++){for (int j = i + 1; j <= n; j++){ans = max(ans, ((ll)i) * j - (a[i] | a[j]) * k);}}cout << ans << endl;}return 0;
}