Submission #4220038

---

Source Code Expand

n, k = map(int, input().split())
a = list(map(int, input().split()))
dig=[0 for i in range(40)] # 10^12 < 2^40

for i in range(n) :
    temp = a[i] 
    for j in range(40) :
        if temp <= 0 :
            break
        if temp % 2 == 1 :
            dig[j] += 1
        temp = temp // 2

bin = 1 << 39 # 2^39
sum0 = 0
i = 39
# leading_zero of k
while(bin > k) :
    sum0 += bin * dig[i]
    bin //= 2
    i += -1

memo={}

def solve (k, bin, i) :
    if i < 0 :
        return 0, 0
    if (k,bin) in memo:
        return memo[(k,bin)]
    if k >= bin :  # this digit can be 1 or 0
        sum1, ans1 = solve(k-bin, bin//2, i-1)
        sum1 += bin * (n- dig[i]) 
        sum0, ans0 = solve(bin-1,bin//2, i-1)
        sum0 += bin * dig[i]
        if sum1 >= sum0 :
            sum = sum1
            ans = ans1 + bin
        else :
            sum = sum0
            ans = ans0
    else :         # this digit must be 0
        sum, ans = solve(k,bin//2, i-1)
        sum += bin * dig[i]
    memo[(k,bin)] = sum, ans
    return sum, ans

sum, ans = solve(k, bin, i)

print (sum+sum0)
#print(sum, sum0)
#print (ans)

Submission Info

Judge Result