Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

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

bits = [0] * 40

for i in range(N):
    for j in range(40):
        if A[i] >> j & 1:
            bits[j] += 1

pow2 = defaultdict(int)
for i in range(50):
    pow2[i] = pow(2, i)


ans = 0
for i in range(K+1):
    tmp = 0
    for j in range(40):
        bit_count = bits[j]
        if i >> j & 1:
            bit_count = N - bit_count
        tmp += pow2[j] * bit_count
    ans = max(ans, tmp)

print(ans)


Fixed submission:
MAX_DIGIT = 50
SMALL = 1
EQUAL = 0

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

dp = [[-1 for _ in range(2)] for _ in range(100)]
dp[0][0] = 0

for d in range(MAX_DIGIT):
    mask = 1 << (MAX_DIGIT - d - 1)
    # A で元々 d 桁目にビットが立っているものの個数
    num = 0
    for i in range(N):
        if A[i] & mask:
            num += 1

    # X の d 桁目を 0, 1 にしたときのコスト
    cost0 = mask * num  # 元々の 1 の個数
    cost1 = mask * (N - num)  # 元々の 0 の個数(反転するから)

    # "K 未満 -> K 未満" の遷移
    if dp[d][SMALL] != -1:
        # 0 でも 1 でも自在に大きい方
        dp[d+1][SMALL] = max(dp[d+1][SMALL], dp[d][SMALL] + max(cost0, cost1))

    # "K ぴったり -> K 未満" の遷移
    if dp[d][0] != -1:
        if K & mask:
            # K の d 桁目が 1 だったら、X の d 桁目は 0 にする
            dp[d+1][SMALL] = max(dp[d+1][SMALL], dp[d][EQUAL] + cost0)

    # "K ぴったり -> K ぴったり" の遷移
    if dp[d][EQUAL] != -1:
        if K & mask:
            dp[d+1][EQUAL] = max(dp[d+1][EQUAL], dp[d][EQUAL] + cost1)
        else:
            dp[d+1][EQUAL] = max(dp[d+1][EQUAL], dp[d][EQUAL] + cost0)


ans = max(dp[MAX_DIGIT][EQUAL], dp[MAX_DIGIT][SMALL])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))

bits = [0] * 40

for i in range(N):
    for j in range(40):
        if A[i] >> j & 1:
            bits[j] += 1

ans = 0
for i in range(K+1):
    tmp = 0
    for j in range(40):
        bit_count = bits[j]
        if i >> j & 1:
            bit_count = N - bit_count
        tmp += pow(2, j) * bit_count
    ans = max(ans, tmp)

print(ans)


Fixed submission:
MAX_DIGIT = 50
SMALL = 1
EQUAL = 0

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

dp = [[-1 for _ in range(2)] for _ in range(100)]
dp[0][0] = 0

for d in range(MAX_DIGIT):
    mask = 1 << (MAX_DIGIT - d - 1)
    # A で元々 d 桁目にビットが立っているものの個数
    num = 0
    for i in range(N):
        if A[i] & mask:
            num += 1

    # X の d 桁目を 0, 1 にしたときのコスト
    cost0 = mask * num  # 元々の 1 の個数
    cost1 = mask * (N - num)  # 元々の 0 の個数(反転するから)

    # "K 未満 -> K 未満" の遷移
    if dp[d][SMALL] != -1:
        # 0 でも 1 でも自在に大きい方
        dp[d+1][SMALL] = max(dp[d+1][SMALL], dp[d][SMALL] + max(cost0, cost1))

    # "K ぴったり -> K 未満" の遷移
    if dp[d][0] != -1:
        if K & mask:
            # K の d 桁目が 1 だったら、X の d 桁目は 0 にする
            dp[d+1][SMALL] = max(dp[d+1][SMALL], dp[d][EQUAL] + cost0)

    # "K ぴったり -> K ぴったり" の遷移
    if dp[d][EQUAL] != -1:
        if K & mask:
            dp[d+1][EQUAL] = max(dp[d+1][EQUAL], dp[d][EQUAL] + cost1)
        else:
            dp[d+1][EQUAL] = max(dp[d+1][EQUAL], dp[d][EQUAL] + cost0)


ans = max(dp[MAX_DIGIT][EQUAL], dp[MAX_DIGIT][SMALL])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

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

bits = [0] * 50

for i in range(N):
    for j in range(50):
        if A[i] >> j & 1:
            bits[j] += 1

ans = 0
for i in range(K+1):
    tmp = 0
    for j in range(50):
        bit_count = bits[j]
        if i >> j & 1:
            bit_count = N - bit_count
        tmp += 2 ** j * bit_count
    ans = max(ans, tmp)

print(ans)


Fixed submission:
MAX_DIGIT = 50
SMALL = 1
EQUAL = 0

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

dp = [[-1 for _ in range(2)] for _ in range(100)]
dp[0][0] = 0

for d in range(MAX_DIGIT):
    mask = 1 << (MAX_DIGIT - d - 1)
    # A で元々 d 桁目にビットが立っているものの個数
    num = 0
    for i in range(N):
        if A[i] & mask:
            num += 1

    # X の d 桁目を 0, 1 にしたときのコスト
    cost0 = mask * num  # 元々の 1 の個数
    cost1 = mask * (N - num)  # 元々の 0 の個数(反転するから)

    # "K 未満 -> K 未満" の遷移
    if dp[d][SMALL] != -1:
        # 0 でも 1 でも自在に大きい方
        dp[d+1][SMALL] = max(dp[d+1][SMALL], dp[d][SMALL] + max(cost0, cost1))

    # "K ぴったり -> K 未満" の遷移
    if dp[d][0] != -1:
        if K & mask:
            # K の d 桁目が 1 だったら、X の d 桁目は 0 にする
            dp[d+1][SMALL] = max(dp[d+1][SMALL], dp[d][EQUAL] + cost0)

    # "K ぴったり -> K ぴったり" の遷移
    if dp[d][EQUAL] != -1:
        if K & mask:
            dp[d+1][EQUAL] = max(dp[d+1][EQUAL], dp[d][EQUAL] + cost1)
        else:
            dp[d+1][EQUAL] = max(dp[d+1][EQUAL], dp[d][EQUAL] + cost0)


ans = max(dp[MAX_DIGIT][EQUAL], dp[MAX_DIGIT][SMALL])
print(ans)