Tích trừ OR

Đề bài

Mô tả

Cho n số nguyên a1,a2,…,an và số nguyên k. Hãy tìm giá trị lớn nhất của

i·j−k·(ai∣aj)

trên tất cả các cặp chỉ số (i,j) thỏa mãn 1≤i<j≤n, trong đó ∣ là phép toán OR theo bit.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t, là số bộ dữ liệu.

Mỗi bộ dữ liệu gồm:

  • Dòng thứ nhất chứa hai số nguyên n và k.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là giá trị lớn nhất của i·j−k·(ai∣aj).

Ràng buộc

  • 1≤t≤10000
  • 2≤n≤105
  • 1≤k≤min(n,100)
  • 0≤ai≤n
  • Tổng n trên tất cả các bộ dữ liệu không vượt quá 3·105

Ví dụ

Input Output Giải thích
4
3 3
1 1 3
2 2
1 2
4 3
0 1 2 3
6 6
3 2 0 0 5 6
-1
-4
3
12
Kí hiệu f(i,j)=i·j−k·(ai∣aj). Bộ thứ nhất: f(1,2)=2−3·(1∣1)=−1, f(1,3)=3−3·3=−6, f(2,3)=6−3·3=−3, nên đáp án là −1. Bộ thứ tư: đáp án đạt tại (3,4) với 12−6·0=12.
1
2 1
2 2
0 Chỉ có một cặp (1,2): 2−1·(2∣2)=0.
1
8 5
0 1 5 0 8 8 8 6
4 Đáp án đạt tại (1,4): 4−5·(0∣0)=4. Các cặp có chỉ số lớn hơn bị phạt nặng vì a5,…,a8 lớn.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0