B. Cobb（CodeForces div.2）

B. Cobb（CodeForces div.2）

看的这位的思路：

Jacky_50

题意

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. Here, | is the bitwise OR operator.

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≤105) 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⋅105.

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

Example
inputCopy
4
3 3
1 1 3
2 2
1 2
4 3
0 1 2 3
6 6
3 2 0 0 5 6
outputCopy
-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.

AC代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 1e5+5;ll f[N];
int main()
{int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);for(ll i=1;i<=n;i++){scanf("%lld",&f[i]);}ll ans=2-k*(f[1]|f[2]);for(ll i=max(1,n-100);i<n;i++){for(ll j=i+1;j<=n;j++){if(ans<i*j-k*(f[i]|f[j])) ans=i*j-k*(f[i]|f[j]);}}printf("%lldn",ans);}return 0;
}