Problem:
 Score : 400 points    Problem Statement You are given N non-negative integers A_1, A_2, ..., A_N and another non-negative integer K .  For a integer X between 0 and K (inclusive), let f(X) = (X XOR A_1)  +  (X XOR A_2)  +  ...  +  (X XOR A_N) .  Here, for non-negative integers a and b , a XOR b denotes the bitwise exclusive OR of a and b .  Find the maximum value of f .   What is XOR?  The bitwise exclusive OR of a and b , X , is defined as follows:   When X is written in base two, the digit in the 2^k 's place ( k \geq 0 ) is 1 if, when written in base two, exactly one of A and B has 1 in the 2^k 's place, and 0 otherwise.   For example, 3 XOR 5 = 6 . (When written in base two: 011 XOR 101 = 110 .)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n,k = map(int, input().split())
    a = list(map(int, input().split()))

    
    zero, one = [0]*40, [0]*40

    for i in range(n):
        for bit in range(40):
            if (a[i]>>bit) & 1:
                one[bit] += 1
            else:
                zero[bit] += 1
    
    res1 = 0
    
    res2 = 0
    flag = 0
    for i in range(39, -1, -1):
        if flag == 0:
            if (k>>i) & 1:
                res1 += 2**i * one[i]
                res2 += 2**i * zero[i]
                flag = 1
            else:
                res1 += 2**i * one[i]
                res2 += 2**i * one[i]
        else:
            if (k>>i) & 1:
                res1 = max(res1 + 2**i * max(one[i], zero[i]), res2 + 2**i * one[i])
                res2 += 2**i * zero[i]
            else:
                res1 += 2**i * max(one[i], zero[i])
                res2 += 2**i * one[i]
    print(max(res1, res2))

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n,k = map(int, input().split())
    a = list(map(int, input().split()))

    
    zero, one = [0]*40, [0]*40

    for i in range(n):
        for bit in range(40):
            if (a[i]>>bit) & 1:
                one[bit] += 1
            else:
                zero[bit] += 1
    
    res1 = 0
    
    res2 = 0
    flag = 0
    for i in range(39, -1, -1):
        if flag == 0:
            if (k>>i) & 1:
                res1 += 2**i * one[i]
                res2 += 2**i * zero[i]
                flag = 1
            else:
                res1 += 2**i * one[i]
                res2 += 2**i * one[i]
        else:
            if (k>>i) & 1:
                res1 = max(res1 + 2**i * max(one[i], zero[i]), res2 + 2**i * one[i])
                res2 += 2**i * zero[i]
            else:
                res1 += 2**i * max(one[i], zero[i])
                res2 += 2**i * one[i]
    print(max(res1, res2))

if __name__ == '__main__':
    main()

Solution (Python):


N, K = map(int,input().split())
A = list(map(int,input().split()))
dp = [[-1]*2 for _ in range(100)]
MAX_DIGIT = 50

dp[0][0] = 0
for i in range(MAX_DIGIT):
    bitmask = 1 << (MAX_DIGIT-i-1)
    bit1_num = 0
    for a in A:
        if bitmask & a:
            bit1_num += 1

    score0 = bitmask*bit1_num  
    score1 = bitmask*(N-bit1_num)

    if dp[i][1] != -1:
        dp[i+1][1] = max(dp[i+1][1],dp[i][1] + max(score0,score1))

    if dp[i][0] != -1:
        if K & bitmask:
            dp[i+1][1] = max(dp[i+1][1],dp[i][0] + score0)

    if dp[i][0] != -1:
        if K & bitmask:
            dp[i+1][0] = max(dp[i+1][0],dp[i][0] + score1)
        else:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + score0)


ans = max(dp[MAX_DIGIT][0], dp[MAX_DIGIT][1])
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0  
x = 0 


for i in range(40, -1, -1): 
    c = 0
    for ai in a:
        if (ai >> i) & 1: 
            c += 1  
            
    
    
    if (n - c) > c and x + (1 << i) <= k:
        x += 1 << i
        ans += (n - c) * (1 << i)
    else:
        
        ans += c * (1 << i)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))


ones = [0] * (len(bin(K)) - 2)
for a in A:
    for i in range(len(ones)):
        if (1 << i) & a:
            ones[i] += 1

best_bits = [1 if x * 2 < N else 0 for x in ones]
best_k = sum(2 ** i * b for i, b in enumerate(best_bits))
if K < best_k:
    better = 0
    for i in range(len(ones) - 1, -1, -1):
        if best_bits[i]:
            b = 1 << i
            if better + b <= K:
                better += b
    best_k = better

answer = 0
for a in A:
    answer += a ^ best_k
print(answer)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans,l=0,0
for i in range(40)[::-1]:
  b=1<<i
  c=sum(bool(x&b) for x in a)
  if l+b<=k and c<n-c:
    l+=b
    ans+=b*(n-c)
  else:
    ans+=b*c
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
x = 0
for i in range(40, -1, -1):
    c = 0
    for ai in a:
        if (ai >> i) & 1:
            c += 1
    if (n - c) > c and x + (1 << i) <= k:
        x += 1 << i
        ans += (n - c) * (1 << i)
    else:
        ans += c * (1 << i)
print(ans)

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
bi = ''
cur = 1
while cur <= k:
    t = k&cur
    if t != 0:
        bi = '1'+bi
    else:
        bi = '0'+bi
    cur *= 2
bit = [0]*len(bi)
for i in range(n):
    u = A[i]
    cur = 1
    s = ''
    times = 0
    for j in range(40):
        z = u&cur
        if z != 0:
            if times < len(bi):
                bit[len(bi)-times-1] += 1
        cur *= 2
        times += 1
ans = ''
flag = False 
l = len(A)
if l%2 != 0:
    for i in range(len(bi)):
        if l//2 < bit[i]:
            if flag:
                ans = ans+'0'
            else:
                if bi[i] == '1':
                    flag = True
                    ans = ans+'0'
                else:
                    ans = ans+'0'
        else:
            if flag:
                ans = ans+'1'
            else:
                if bi[i] == '1':
                    ans = ans+'1'
                else:
                    ans = ans+'0'
else:
    for i in range(len(bi)):
        if l//2 <= bit[i]:
            if flag:
                ans = ans+'0'
            else:
                if bi[i] == '1':
                    flag = True
                    ans = ans+'0'
                else:
                    ans = ans+'0'
        else:
            if flag:
                ans = ans+'1'
            else:
                if bi[i] == '1':
                    ans = ans+'1'
                else:
                    ans = ans+'0'
alt = 0
cur = 1
for i in range(len(ans)):
    if ans[len(ans)-i-1] == '1':
        alt += cur
    cur *= 2
S = 0
for i in range(n):
    S += A[i]^alt
print(S)

Solution (Python):
import bisect
import sys


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class v:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(N, M, b_k, D, i):
    res = 0
    for d in range(D - 1, i, -1):
        res += 2 ** d * (M[d] if b_k[d] == "0" else N - M[d])

    res += 2 ** i * M[i]

    for j in range(i):
        res += 2 ** j * (M[j] if M[j] * 2 > N else N - M[j])

    return res


def main():
    N, K = read_values()
    A = read_list()
    T = max(K + 1, max(A))
    D = len(bin(T)) - 2

    M = [0] * D
    for a in A:
        b = format(a, "0" + str(D) + "b")
        for i, s in enumerate(b):
            M[i] += int(s)

    M.reverse()
    b_k = format(K + 1, "0" + str(D) + "b")[::-1]
    res = v(max)
    for i in range(D):
        if b_k[i] == "0":
            continue
        res.ud(f(N, M, b_k, D, i))

    print(res)


if __name__ == "__main__":
    main()

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

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    
    l = max(M,max(a)).bit_length()
    a = np.array(a)
    
    base,ans = 0,0
    for i in reversed(range(l)):
        bit = (a>>i)&1
        c = np.count_nonzero(bit==0)
        if c > N//2:
            if base+2**i <= M:
                base += 2**i
                ans += (2**i)*c
            else:
                ans += (2**i)*(N-c)
        else:
            ans += (2**i)*(N-c)
    
    print(ans)

if __name__ == "__main__":
    main()

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

n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

bin_k = format(k, 'b').zfill(50)

b = [0] * 50 

for i in a:
    bin_i = format(i, 'b').zfill(50)
    for j in range(len(bin_i)):
        if bin_i[j] == "1":
            b[j] += 1

dp = [[0, 0] for _ in range(len(bin_k))]

if bin_k[0] == "0":
    dp[0][0] = b[0] * 2**(len(bin_k) - 1) 
else:
    dp[0][0] = (n - b[0]) * 2**(len(bin_k) - 1) 
    dp[0][1] = b[0] * 2**(len(bin_k) - 1) 

for i in range(1, len(bin_k)):
    if bin_k[i] == "0":
        dp[i][0] = dp[i - 1][0] + b[i] * 2**(len(bin_k) - (i + 1))
        if dp[i - 1][1] > 0:
            dp[i][1] = max(dp[i - 1][1] + b[i] * 2**(len(bin_k) - (i + 1)), dp[i - 1][1] + (n - b[i]) * 2**(len(bin_k) - (i + 1)))
    else:
        dp[i][0] = dp[i - 1][0] + (n - b[i]) * 2**(len(bin_i) - (i + 1))
        dp[i][1] = dp[i - 1][0] + b[i] * 2**(len(bin_k) - (i + 1))
        if dp[i - 1][1] > 0:
            dp[i][1] = max(dp[i][1], dp[i - 1][1] + (n - b[i]) * 2**(len(bin_i) - (i + 1)), dp[i - 1][1] + b[i] * 2**(len(bin_k) - (i + 1))) 

print(max(dp[-1][0], dp[-1][1]))

Solution (Python):
import numpy as np
import copy
import math
n, kk = map(int, input().split())
a = [int(x) for x in input().split()]
a2 = np.array(copy.deepcopy(a))

key = 1
p = int(math.log2(max([kk, 1])))+1
x = [1]*p
for i in range(p):
  k = np.sum(a2%2)
  if n >= 2*k:
    x[i] = 0
  a2 = a2//2

x_sum = 0
for i in range(p-1, -1, -1):
  if x[i]:
    continue
  if x_sum+pow(2, i) > kk:
    continue
  x_sum += pow(2, i)

ans = 0
for i in range(n):
  ans += (x_sum^a[i])
print(ans)

Solution (Python):

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_right, bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()    
A = LIST()

tmp = [0] * 40

for a in A:
    for i in range(40):
        if a & (1 << i):
            tmp[i] += 1


x = 0

for i in range(39, -1, -1):
    
    
    
    
    if x + (1 << i) <= K and tmp[i] < (N + 1) // 2:
        x += (1 << i)
        



ans = 0
for i in A:
    ans += i ^ x
print(ans)

Solution (Python):
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))

max_dig=50

dp=[[-1]*2 for _ in range(max_dig+1)]

dp[0][0]=0

for d in range(max_dig):
    mask=1<<(max_dig-d-1)

    cnt=sum([mask&a[i]>0 for i in range(n)])
    c0=cnt*mask
    c1=(n-cnt)*mask

    if dp[d][1]!=-1:
        dp[d+1][1]=max(dp[d+1][1],dp[d][1]+max(c0,c1))
    
    if dp[d][0]!=-1:
        if k&mask>0:
            dp[d+1][1]=max(dp[d+1][1],dp[d][0]+c0)
    
    if dp[d][0]!=-1:
        if k&mask>0:
            dp[d+1][0]=max(dp[d+1][0],dp[d][0]+c1)
        else:
            dp[d+1][0]=max(dp[d+1][0],dp[d][0]+c0)

print(max(dp[max_dig][0],dp[max_dig][1]))

Solution (Python):
N,K = map(int, input().split())
A = [int(i) for i in input().split()]




dp = [[-float("inf")] * 2 for _ in range(61)]


dp[0][0] = 0

for i in range(60):
    one = 0 
    for a in A:
        if (a >> (59 - i)) & 1:
            one += 1
    zero = N - one 

    for j in range(2):
        if dp[i][j] < 0:
            continue

        """ Xの(上から)i桁目を0にする -> 無条件"""
        dp[i+1][j | ((K >> (59 - i)) & 1)] = max(dp[i+1][j | ((K >> (59 - i)) & 1)], dp[i][j] + one * (1 << (59 - i)))

        """
        Xの(上から)i桁目を1にする場合の条件
        -> K以下未満が確定 or Kを超えない
        """
        if j or (K >> (59 - i)) & 1:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + zero * (1 << (59 - i)))

print(max(dp[60]))

Solution (Python):
N,K = map(int, input().split())
A = [int(i) for i in input().split()]




dp = [[-float("inf")] * 2 for _ in range(61)]


dp[0][0] = 0

for i in range(60):
    for j in range(2):
        if dp[i][j] < 0:
            continue

        one = 0
        for a in A:
            if (a >> (59 - i)) & 1:
                one += 1
        zero = N - one

        
        dp[i+1][j | ((K >> (59 - i)) & 1)] = max(dp[i+1][j | ((K >> (59 - i)) & 1)], dp[i][j] + one * (1 << (59 - i)))

        
        if j or (K >> (59 - i)) & 1:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + zero * (1 << (59 - i)))

print(max(dp[60]))

Solution (Python):
n,k=map(int,input().split())
l=list(map(int,input().split()))
keta=[0 for i in range(41)]
for i in l:
    for j in range(41):
        keta[j]+=i%2
        i//=2
ans=0
t=0
x=40
k2=[0 for i in range(41)]
for j in range(41):
    k2[j]=k%2
    k//=2
for i in k2[::-1]:
    if i==0 and t==0:
        ans+=keta[x]*(2**x)
    else:
        if keta[x]>n//2:
            if i==1:
                t=1
            ans+=keta[x]*(2**x)
        else:
            ans+=(n-keta[x])*(2**x)
    x-=1
print(ans)

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

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    
    bin_k=format(k,'b').zfill(50)
    l=50
    
    flag=False
    power=pow(2,l-1)
    ans=0
    for i in range(l):
        keta=l-i-1
        cnt=0
        for num in a:
            if (num>>keta)&1:
                cnt+=1

        if flag:
            ans+=max(cnt,n-cnt)*power
        
        else:
            if 2*cnt >= n and bin_k[i]=='1':
                flag=True
                ans+=cnt*power
          
            elif 2*cnt >= n:
                ans+=cnt*power
           
            elif bin_k[i]=='1':
                ans+=(n-cnt)*power
       
            else:
                ans+=cnt*power
        
        power//=2
    
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))

l = 50

dp = [[-1] * 2 for _ in range(l + 1)]
dp[0][0] = 0

for i in range(l):
    mask = 1 << (l - i - 1)
    ones = 0
    for e in a:
        if e & mask:
            ones += 1

    cost0 = mask * ones
    cost1 = mask * (n - ones)

    if dp[i][1] != -1:
        dp[i+1][1] = max(dp[i+1][1], dp[i][1] + max(cost0, cost1))

    if dp[i][0] != -1:
        if k & mask:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + cost0)

    if dp[i][0] != -1:
        if k & mask:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost1)
        else:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost0)

ans = max(dp[l][0], dp[l][1])
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
bit = list(bin(K)[2:])
d = len(bit)
count = [0] * d
for a in A:
    b = bin(a)[2:]
    for j in range(d):
        count[d-j-1] += a >> j & 1
less = False
X = 0
for i in range(d):
    X <<= 1
    if less or bit[i] == '1':
        if 2*count[i] < N:
            X += 1
        else:
            less = True
ans = 0
for a in A:
    ans += X ^ a
print(ans)

Solution (Python):



N,K=map(int,input().split())

A=list(map(int,input().split()))

cand=[2**i for i in range(40)][::-1]
bit=[0]*40

for a in A:
    for i in range(40):
        if a>=cand[i]:
            a-=cand[i]
            bit[i]+=1

digits=1
while K>=2**(digits):
    digits+=1

ans=0

if K==0:
    for i in range(40):
        ans+=cand[i]*bit[i]
    print(ans)
    exit()

for i in range(40-digits):
    ans+=cand[i]*bit[i]



dp=[[[0 for k in range(2)] for j in range(digits)] for i in range(2)]
cand=cand[40-digits:40]
bit=bit[40-digits:40]
dp[0][0][0]=bit[0]*cand[0]
dp[1][0][1]=(N-bit[0])*cand[0]
K-=cand[0]

for i in range(digits-1):
    cor=bit[i+1]*cand[i+1]
    rev=(N-bit[i+1])*cand[i+1]
    if K>=cand[i+1]:
        K-=cand[i+1]
        dp[0][i+1][0]=max(dp[0][i][0],dp[0][i][1],dp[1][i][1],dp[1][i][0])+cor
        dp[0][i+1][1]=max(dp[0][i][0],dp[0][i][1])+rev
        dp[1][i+1][1]=max(dp[1][i][1],dp[1][i][0])+rev
        
    else:
        dp[0][i+1][0]=max(dp[0][i][0],dp[0][i][1])+cor
        dp[0][i+1][1]=max(dp[0][i][0],dp[0][i][1])+rev
        dp[1][i+1][0]=max(dp[1][i][0],dp[1][i][1])+cor



temp=max(max(dp[0][-1]),max(dp[1][-1]))
print(ans+temp)

Solution (Python):

import math
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    a = int(math.log2(max(A))) + 1
    l = [0] * a
    for i in A:
        t = 0
        while i > 0:
            if i % 2 == 1:
                l[t] += 1
            i >>= 1
            t += 1
    la = [0 if i >= (N-i) else 1 for i in l]
    lla = sum(v * pow(2,i) for i, v in enumerate(la))
    lk = []
    K2 = K
    while K2 > 0:
        if K2 % 2 == 1:
            lk.append(1)
        else:
            lk.append(0)
        K2 >>= 1
    if len(lk) > len(la):
        la.extend([0] * (len(lk)-len(la)))
        l.extend([0] * (len(lk)-len(l)))
    else:
        lk.extend([0] * (len(la)-len(lk)))
    r = sum(pow(2, i) * l[i] for i in range(len(l)))
    for i in range(len(lk)):
        if lk[i] == 1:
            r = max(r, calc(lk, la, N, l, i))
    t = 0
    for i in range(len(lk)):
        if lk[i] == 1:
            t += pow(2, i) * max(l[i], N - l[i])
        else:
            t += pow(2, i) * l[i]
    r = max(r, t)
    return r

def calc(lk, la, N, l, j):
    r = 0
    for i in range(j):
        r += pow(2, i) * max(l[i], N - l[i])
    r += pow(2, j) * l[j]
    for i in range(j+1, len(lk)):
        if lk[i] == 1:
            r += pow(2, i) * max(l[i], N - l[i])
        else:
            r += pow(2, i) * l[i]
    return r
print(main())

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = bin(K)[2:]
    B = B[::-1]
    BB = len(bin(10 ** 12)) - 2
    T = [0] * BB
    for i in range(BB):
        T[i] = sum((a & (1 << i)) >> i for a in A)
    if K == 0:
        print(sum(A))
        return
    m = 0
    def h(i, f):
        if i < 0:
            return 0
        if i >= len(B):
            return (T[i] << i) + h(i - 1, False)
        if f:
            return (max(T[i], N - T[i]) << i) + h(i - 1, f)
        if B[i] == '0':
            return (T[i] << i) + h(i - 1, False)
        return max((T[i] << i) + h(i - 1, True), ((N - T[i]) << i) + h(i - 1, False))
    print(h(BB - 1, False))

main()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))

def f(x):
    ret = 0
    for i in range(N):
        ret += A[i] ^ x
    return ret


P = bin(K)
num = len(list(map(int,P[2:])))

best = 0

for i in range(num):
    count = 0
    for j in range(N):
        if A[j] > A[j]^(2**i):
            count += 1
    
    if count <= N - count:
        best += 2**i


can = [0]*40

for i in range(40):
    if K & 2**i == 0:
        continue
    for j in range(0,i):
        can[i] += best & 2**j
    for j in range(i+1,40):
        can[i] += K & 2**j

can.append(K)

print(max(list(map(f,can))))

Solution (Python):

import sys

def _solve(i, k, bits, N):
    if i == -1:
        return 0
    m = 1 << i
    if bits[i] <= N // 2 and k >= m:
        return _solve(i-1, k-m, bits, N) + m
    return _solve(i-1, k, bits, N)

def solve(N: int, K: int, A: "List[int]"):
    L = 64
    bits = tuple(sum(a & (1 << i) > 0 for a in A) for i in range(L))
    x = _solve(L-1, K, bits, N) 
    return sum(x ^ a for a in A)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    print(solve(N, K, A))

if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

L = len(bin(max(K, max(A)))) - 2
X = 0
ans = 0
table = [0]*L

for x in A:
    for i in range(L):
        if (x >> i) % 2 == 1:
            table[i] += 1

table = [(2**i * (N - table[i]), 2**i, table[i], table[i] > N - table[i])
         for i in range(L)]
table.sort(reverse=True)
ans = 0
tmp = 0

for x, y, z, flag in table:
    if flag or tmp + y > K:
        ans += (y*z)
        continue
    else:
        tmp += y
        ans += x
    
print(ans)

Solution (Python):
N, K, *A = map(int, open(0).read().split())
ls = [0]*K.bit_length()
for c in A:
  for i in range(K.bit_length()):
    if c%2==1:
      ls[i] += 1
    c >>= 1
if ls==[]:
  print(sum(A))
  import sys
  sys.exit()
ls = ls[::-1]
s = bin(K)[2:]
m = (2**(len(s)-1))*(N-2*ls[0])
dp1 = [0]*(len(s))
dp2 = [0]*(len(s))
dp1[0] = m
for i in range(1,len(s)):
  c = s[i]
  if c=='1':
    m = (2**(len(s)-i-1))*(N-2*ls[i])
    dp1[i] = dp1[i-1]+m
    if N>2*ls[i]:
      dp2[i] = dp2[i-1]+m
    else:
      dp2[i] = max(dp1[i-1],dp2[i-1])
  else:
    dp1[i] = dp1[i-1]
    if N>2*ls[i]:
      m = (2**(len(s)-i-1))*(N-2*ls[i])
      dp2[i] = dp2[i-1]+m
    else:
      dp2[i] = dp2[i-1]
print(sum(A)+max(dp1[-1],dp2[-1]))

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

def solve():  
  n,k = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  digit = [0]*62
  for i in range(n):
    an = a[i]
    j = 0
    while an>0:
      digit[j] += an%2
      an //= 2
      j+=1
  digit = digit[::-1]


  dp = [[0]*2  for _ in range(63)]
  for i in range(62):
    value = 2**(62-i-1)
    temp = digit[i]

    if (dp[i][1]):
        dp[i+1][1] = max(dp[i+1][1],dp[i][1]+value*max(n-temp,temp))  
      
    if (k>>(62-i-1)&1):
      dp[i+1][1] = max(dp[i][0] +value*temp,dp[i+1][1])
      dp[i+1][0] = max(dp[i+1][0],dp[i][0]+ value*(n-temp))
    else: 
      dp[i+1][0] = max(dp[i+1][0],dp[i][0]+ value*temp)
      

  
  print(max(dp[-1][0],dp[-1][1]))
    
solve()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,K=map(int, input().split())
A=tuple(map(int,input().split()))
l=[0]*40
for i in A:
    b=bin(i)
    for i in range(-1,1-len(b),-1):
        if b[i]=="1":
            l[i]+=1
x=[0]*40
xi=0
for i in range(40):
    if l[i]<=N//2 and xi+2**(39-i)<=K:
        x[i]=1
        xi+=2**(39-i)
a=0
for i in range(40):
    if x[i]:
        a+=(N-l[i])*2**(39-i)
    else:
        a+=l[i]*2**(39-i)
print(a)

Solution (Python):
N,K=map(int, input().split())
A=tuple(map(int,input().split()))
l=[0]*40
for i in A:
    b=bin(i)
    for i in range(-1,1-len(b),-1):
        if b[i]=="1":
            l[i]+=1
x=[0]*40
xi=0
for i in range(40):
    if l[i]<=N//2 and xi+2**(39-i)<=K:
        x[i]=1
        xi+=2**(39-i)
a=0
for i in range(40):
    if x[i]:
        a+=(N-l[i])*2**(39-i)
    else:
        a+=l[i]*2**(39-i)
print(a)

Solution (Python):
N,K=map(int, input().split())
A=tuple(map(int,input().split()))
l=[0]*40
for i in A:
    b=bin(i)
    for i in range(-1,1-len(b),-1):
        if b[i]=="1":
            l[i]+=1
x=[0]*40
xi=0
for i in range(40):
    if l[i]<=N//2 and xi+2**(39-i)<=K:
        x[i]=1
        xi+=2**(39-i)
a=0
for i in range(40):
    if x[i]:
        a+=(N-l[i])*2**(39-i)
    else:
        a+=l[i]*2**(39-i)
print(a)

Solution (Python):

N,K=map(int,input().split())
A=list(map(int,input().split()))

Pro=[0]*40
for i in range(40):
    res=0
    for j in range(N):
        if (A[j]>>i)&1:
            res+=1
    Pro[i]=res

K_bin=[]
tmp=K+1
for i in range(40):
    K_bin.append(tmp%2)
    tmp//=2
    
Ans=0    
    
for i in range(40):
    x=0
    if K_bin[i]==1:
        x+=sum([max(Pro[j],N-Pro[j])*(2**j) for j in range(0,i)])
        x+=Pro[i]*(2**i)
        x+=sum([(2**j)*(Pro[j]+(N-2*Pro[j])*K_bin[j]) for j in range(i+1,40)])
    Ans=max(Ans,x)
    
print(Ans)

Solution (Python):
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
bit_len = len(format(k, 'b'))
for i in range(n):
    bit_len = max(bit_len, len(format(a[i],'b')))
bit_count = [0 for i in range(bit_len)]
for i in range(n):
    bit = format(a[i], 'b').zfill(bit_len)
    for j in range(bit_len):
        if bit[j] == '1':
            bit_count[j] += 1
ans = 0
now_num = 0
for i in range(bit_len):
    if bit_count[i] < n - bit_count[i]:
        if now_num + 2 ** (bit_len - i - 1) <= k:
            now_num += 2 ** (bit_len - i - 1)
            ans += (n - bit_count[i]) * (2 ** (bit_len - i - 1))
            continue
    ans += bit_count[i] * (2 ** (bit_len - i - 1))
print(ans)

Solution (Python):
import numpy as np

N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)

digits = len(format(K, "b"))
bits_list = [((A >> shift) & 1).sum() for shift in range(digits)]
bits_list.reverse()

X = 0
half = (N + 1) // 2
digit = 1 << (digits - 1)

for bits in bits_list:
    if bits < half and (X | digit) <= K:
        A ^= digit
        X |= digit
    digit >>= 1

print(A.sum())

Solution (Python):
import numpy as np

N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)

digits = len(format(K, "b"))
bits_list = [((A >> shift) & 1).sum() for shift in range(digits)]
bits_list.reverse()

X = 0
half = (N + 1) // 2
digit = 1 << (len(format(K, "b")) - 1)

for bits in bits_list:
    if bits < half and (X | digit) <= K:
        A ^= digit
        X |= digit
    digit >>= 1

print(A.sum())

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
data=[0 for i in range(0,41)]
for i in range(0,N):
    for j in range(0,41):
        data[j]+=(A[i]>>j)&1
X=0
subdata=[K>>i &1 for i in range(0,41)]
subdataK=[i for i in range(0,41) if subdata[i]==1]
ans=sum(K^A[i] for i in range(0,N))
for i in range(0,len(subdataK)):
    k=subdataK[i]
    X=0
    for j in range(0,k):
        if N-data[j]>=data[j]:
            X+=2**j
    for j in range(k+1,41):
        X+=subdata[j]*2**j
    test=sum(X^A[i] for i in range(0,N))
    if test>ans:
        ans=test
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
data=[0 for i in range(0,41)]
for i in range(0,N):
    for j in range(0,41):
        data[j]+=(A[i]>>j)&1
X=0
flag=1
for i in range(0,41):
    if flag==0:
        if N-data[40-i]>=data[40-i]:
            X+=2**(40-i)
    else:
        test=K>>(40-i) &1
        if test==1:
            if N-data[40-i]>=data[40-i]:
                X+=2**(40-i)
            else:
                flag=0

print(sum(X^A[i] for i in range(0,N)))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
max_length = max(max(A), K).bit_length()
A_bin = [bin(a)[2:].zfill(max_length) for a in A]
K_bin = bin(K)[2:].zfill(max_length)

count = []
for digit in range(max_length):
  count_zero = 0
  for a_bin in A_bin:
    if a_bin[digit] == '0':
      count_zero += 1
  count.append(count_zero)


half = -(-N//2)
X = ''
tight = True
for i, c in enumerate(count):
  if c < half:
    X += '0'
    if K_bin[i] == '1':
      tight = False
  else:
    if K_bin[i] == '1' or not tight:
      X += '1'
    else:
      X += '0'


X = int(X, 2)
ans = 0
for a in A:
  ans += X^a


print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))



L = 50

bins = [0]*L
kb = [0]*L


for i in range(L):    
    for j in range(N):
        bins[i] += A[j]%2
        A[j] >>= 1
    kb[i] = K%2
    K >>= 1

bins.reverse()
kb.reverse()

start = L

for i,k in enumerate(kb):
    if k==1:
        start = i
        break




        
dp = [[0]*2 for _ in range(L+1)]



cur = 0
base = 2**(L-1)
for i in range(L):
    if i<start:
        dp[i+1][1] = dp[i][1] + bins[i]*base
        
    elif i==start:
        dp[i+1][0] = dp[i][1]+(bins[i])*base
        dp[i+1][1] = dp[i][1] + (N-bins[i])*base
        
    else:
        if kb[i]:
            dp[i+1][0] = max(dp[i][0] + max(bins[i],N-bins[i])*base,
                             dp[i][1] + (bins[i]) * base)
            
            dp[i+1][1] = dp[i][1] + (N-bins[i])*base      
        else:
            dp[i+1][0] = dp[i][0] + max(bins[i],N-bins[i])*base
            
            dp[i+1][1] = dp[i][1] + (bins[i])*base            
    base >>= 1
        
print(max(dp[L][0],dp[L][1]))

Solution (Python):
N, K = map(int, input().split())
*A, = map(int, input().split())

def get_k_bits():
    global K
    k_list = []
    while K:
        k_list.append(K%2)
        K//=2
    k_list.extend([0]*(50-len(k_list)))
    k_list.reverse()
    return k_list

def get_bits_count():
    b = [0]*50
    for i in A:
        p = 0
        while i:
            b[p] += i%2
            i //=2
            p += 1
    b.reverse()
    return b

b = get_bits_count()

def get_appropriate_bits():
    c = [0]*50
    for i in range(50):
        e, f = b[i], N-b[i]
        if e>=f:
            c[i] = 0
        else:            
            c[i] = 1
    return c

def output_candidates():
    candidates = []
    c = get_appropriate_bits()
    k_list = get_k_bits()

    for i in range(50):
        if k_list[i]:
            o = [k_list[j] for j in range(i)] + [0] + [c[j] for j in range(i+1, 50)]
            candidates.append(o)
    candidates.append(k_list)
    return candidates


ans = 0
for bits in output_candidates():
    v = 0
    for j in range(50):
        if bits[j]:
            v += (2**(50-j-1))*(N-b[j])
        else:
            v += (2**(50-j-1))*b[j]
    ans = max(ans, v)

print(ans)

Solution (Python):
N, K = map(int, input().split())
*A, = map(int, input().split())

target = []
while K:
    target.append(K%2)
    K//=2
target.extend([0]*(50-len(target)))

b = [0]*50
for i in A:
    p = 0
    while i:
        b[p] += i%2
        i //=2
        p += 1

target.reverse()
b.reverse()

c = [0]*50
for i in range(50):
    e, f = b[i], N-b[i]
    if e==f:
        c[i] = 0
    elif e>f:
        c[i] = 0
    else:            
        c[i] = 1

ans = 0
for i in range(50):
    if target[i]:
        o = []
        for j in range(i):
            o.append(target[j])
        o.append(0)
        for j in range(i+1, 50):
            o.append(c[j])
        v = 0
        for j in range(50):
            if o[j]:
                v += (2**(50-j-1))*(N-b[j])
            else:
                v += (2**(50-j-1))*b[j]
        ans = max(ans, v)

v = 0
for j in range(50):
    if target[j]:
        v += (2**(50-j-1))*(N-b[j])
    else:
        v += (2**(50-j-1))*b[j]
ans = max(ans, v)

print(ans)