Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
H, W, M = map(int, input().split())
Bh = [0]*(H+1)
Bw = [0]*(W+1)
OD = []

for _ in range(M):
    h, w = map(int, input().split())
    Bh[h] += 1
    Bw[w] += 1
    OD.append((h, w))

M1 = max(Bh)
M2 = max(Bw)
l1 = [i for i, x in enumerate(Bh) if x == M1]
l2 = [j for j, x in enumerate(Bw) if x == M2]
for i, j in itertools.product(l1, l2):
    if (i, j) not in OD:
        break
else:
    print(M1+M2-1)
    exit()
print(M1+M2)


Fixed submission:
import itertools
H, W, M = map(int, input().split())
Bh = [0]*(H+1)
Bw = [0]*(W+1)
OD = set()

for _ in range(M):
    h, w = map(int, input().split())
    Bh[h] += 1
    Bw[w] += 1
    OD.add((h, w))

M1 = max(Bh)
M2 = max(Bw)
l1 = [i for i, x in enumerate(Bh) if x == M1]
l2 = [j for j, x in enumerate(Bw) if x == M2]
for i, j in itertools.product(l1, l2):
    if (i, j) not in OD:
        break
else:
    print(M1+M2-1)
    exit()
print(M1+M2)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
H, W, M = map(int, input().split())
Bh = [0]*(H+1)
Bw = [0]*(W+1)
OD = set()

for _ in range(M):
    h, w = map(int, input().split())
    Bh[h] += 1
    Bw[w] += 1
    OD.add((h, w))

l1 = [i for i, x in enumerate(Bh) if x == max(Bh)]
l2 = [j for j, x in enumerate(Bw) if x == max(Bw)]
for i, j in itertools.product(l1, l2):
    if (i, j) not in OD:
        break
else:
    print(max(Bh)+max(Bw)-1)
    exit()
print(max(Bh)+max(Bw))


Fixed submission:
import itertools
H, W, M = map(int, input().split())
Bh = [0]*(H+1)
Bw = [0]*(W+1)
OD = set()

for _ in range(M):
    h, w = map(int, input().split())
    Bh[h] += 1
    Bw[w] += 1
    OD.add((h, w))

M1 = max(Bh)
M2 = max(Bw)
l1 = [i for i, x in enumerate(Bh) if x == M1]
l2 = [j for j, x in enumerate(Bw) if x == M2]
for i, j in itertools.product(l1, l2):
    if (i, j) not in OD:
        break
else:
    print(M1+M2-1)
    exit()
print(M1+M2)

Buggy python submission (verdict: Time Limit Exceeded):
H, W, M = [int(i) for i in input().split()]
Bh = [0]*H
Bw = [0]*W
BB = [[0 for j in range(W)] for i in range(H)]


for _ in range(M):
    h, w = map(int, input().split())
    Bh[h-1] += 1
    Bw[w-1] += 1
    BB[h-1][w-1] = 1

ans = 0
Mh = max(Bh)
Mw = max(Bw)
for i in [i for i, x in enumerate(Bh) if x == Mh]:
    for j in [j for j, x in enumerate(Bw) if x == Mw]:
        ans = max(ans, Mh+Mw-BB[i][j])
print(ans)


Fixed submission:
import itertools
H, W, M = map(int, input().split())
Bh = [0]*(H+1)
Bw = [0]*(W+1)
OD = set()

for _ in range(M):
    h, w = map(int, input().split())
    Bh[h] += 1
    Bw[w] += 1
    OD.add((h, w))

M1 = max(Bh)
M2 = max(Bw)
l1 = [i for i, x in enumerate(Bh) if x == M1]
l2 = [j for j, x in enumerate(Bw) if x == M2]
for i, j in itertools.product(l1, l2):
    if (i, j) not in OD:
        break
else:
    print(M1+M2-1)
    exit()
print(M1+M2)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
C = [int(i) for i in input().split()]
for i in range(Q):
    l, r = map(int, input().split())
    print(len(set(C[l-1:r])))


Fixed submission:
N, Q = map(int, input().split())
C = [int(i) for i in input().split()]

pi = [-1]*(N+1)
ps = [[] for _ in range(N+1)]
for i in range(N):
    l = pi[C[i]]
    if l != -1:
        ps[l].append(i)
    pi[C[i]] = i

qs = [[] for _ in range(N+1)]
for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r, i))


bit = [0]*(N+1)


def bit_sum(idx):
    res_sum = 0
    while idx > 0:
        res_sum += bit[idx]
        idx -= idx & (-idx)
    return res_sum


def bit_add(idx, x):
    while idx <= N:
        bit[idx] += x
        idx += idx & (-idx)
    return True


ans = [0]*Q
for x in range(N-1, -1, -1):
    for y in ps[x]:
        bit_add(y, 1)
    for r, i in qs[x]:
        ans[i] = r-x+1-bit_sum(r)


for i in range(Q):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

c = 1
for i in range(K):
    c *= A[i]

for i in range(K, N):
    if c < c//A[i-K]*A[i]:
        print('Yes')
    else:
        print('No')
    c = c//A[i-K]*A[i]


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

for i in range(K, N):
    if A[i-K] < A[i]:
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import collections
N = int(input())
A = sorted([int(i) for i in input().split()])
C = collections.Counter(A)
tested = [True for i in range(10**7+1)]

ans = 0
for i in range(N):
    if C[A[i]] == 1 and tested[A[i]] is True:
        ans += 1

    for j in range(A[i], 10**6+1, A[i]):
        tested[j] = False
print(ans)


Fixed submission:
import collections
N = int(input())
A = sorted([int(i) for i in input().split()])
maxA = A[-1]

if N == 1:
    print(1)
    exit()

C = collections.Counter(A)
cand = set(A)

ans = 0
for i in range(N):
    if C[A[i]] >= 2:
        cand -= set([A[i]*j for j in range(1, maxA//A[i]+1)])
        continue

    if A[i] in cand:
        ans += 1
        cand -= set([A[i]*j for j in range(1, maxA//A[i]+1)])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split()]

ans = 1
for i in range(N):
    ans *= A[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)


Fixed submission:
N = int(input())
A = sorted([int(i) for i in input().split()])

if A[0] == 0:
    print(0)
    exit()
else:
    ans = 1
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            exit()
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split()]

ans = 1
for i in range(N):
    ans *= A[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)


Fixed submission:
N = int(input())
A = sorted([int(i) for i in input().split()])

if A[0] == 0:
    print(0)
    exit()
else:
    ans = 1
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            exit()
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])


Fixed submission:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])
Buggy python submission (verdict: Runtime Error):
import numpy as np

N, M, X = map(int, input().split())
C = []
A = np.ndarray((N, M), dtype=int)
for j in range(N):
    c, *a = [int(i) for i in input().split()]
    C.append(c)
    A[j] = a

ans = 10**20
for i in range(2 ** N):
    cost = 0
    sk = np.zeros(M, dtype=int)
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            cost += C[j]
            sk += A[j, :]
    if all(s >= X for s in sk):
        ans = min(ans, cost)

if ans == 10**20:
    print(-1)
else:
    print(ans)


Fixed submission:
import numpy as np

N, M, X = map(int, input().split())
C = []
A = np.ndarray((N, M), dtype=int)
for j in range(N):
    c, *a = [int(i) for i in input().split()]
    C.append(c)
    A[j] = a

ans = 10**20
for i in range(2 ** N):
    cost = 0
    sk = np.zeros(M, dtype=int)
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            cost += C[j]
            sk += A[j, :]
    if all(s >= X for s in sk):
        ans = min(ans, cost)

if ans == 10**20:
    print(-1)
else:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
S = int(input())

d = defaultdict(int)

for i in range(len(str(S))+1):
    t = S % (10**i)
    d[t % 2019] += 1

ans = 0
for v in d.values():
    ans += v*(v-1)//2
print(ans)


Fixed submission:
import collections
S = input()[::-1]

d = 1
M = []
for s in S:
    M.append(int(s)*d % 2019)
    d *= 10
    d %= 2019

S = [0]
for m in M:
    S.append((S[-1]+m) % 2019)

C = collections.Counter(S)

ans = 0
for v in C.values():
    ans += v*(v-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
S = input()

d = defaultdict(int)
d[0] = 1

for i in range(1, len(S)+1):
    t = int(S[-i:])
    d[t % 2019] += 1

ans = 0
for v in d.values():
    ans += v*(v-1)//2
print(ans)


Fixed submission:
import collections
S = input()[::-1]

d = 1
M = []
for s in S:
    M.append(int(s)*d % 2019)
    d *= 10
    d %= 2019

S = [0]
for m in M:
    S.append((S[-1]+m) % 2019)

C = collections.Counter(S)

ans = 0
for v in C.values():
    ans += v*(v-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
print(int(input()*2*math.pi))


Fixed submission:
import math
print(int(input())*2*math.pi)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = [int(i) for i in input().split()]


if sum(M) > N:
    print(-1)
else:
    print(N-sum(A))


Fixed submission:
N, M = map(int, input().split())
A = [int(i) for i in input().split()]


if sum(A) > N:
    print(-1)
else:
    print(N-sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if S[i] != S[j] and S[k] != S[i] and S[k] != S[j] and j-i != k-j:
                ans += 1
print(ans)


Fixed submission:
N = int(input())
S = input()

ans = S.count('R') * S.count('G') * S.count('B')

for i in range(N-1):
    for j in range(i+1, N):
        k = 2*j-i
        if k <= N-1 and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, W, K = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]


def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > K:
            return False
    return True


ans = 10**30
for i in range(2 ** (H-1)):
    g = 0
    id = [-1]*H
    for j in range(H):  # このループが一番のポイント
        id[j] = g
        if (i >> j & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            g += 1
    g += 1

    c = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += S[i][j]

    num = g-1
    now = [0]*g
    for j in range(W):
        if not add(j):
            num += 1
            now = [0]*g
            if not add(j):
                num = 10**30
                continue

    ans = min(ans, num)

print(ans)


Fixed submission:
H, W, K = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]


def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > K:
            return False
    return True


ans = 10**30
for i in range(2 ** (H-1)):
    g = 0
    id = [-1]*H
    for j in range(H):  # このループが一番のポイント
        id[j] = g
        if (i >> j & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            g += 1
    g += 1

    c = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += S[i][j]

    num = g-1
    now = [0]*g
    for j in range(W):
        if not add(j):
            num += 1
            now = [0]*g
            if not add(j):
                num = 10**30
                continue

    ans = min(ans, num)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
for _ in range(Q):
    Query = [i for i in input().split()]
    if Query[0] == '1':
        S = S[::-1]
    else:
        if Query[1] == '1':
            S = ''.join([Query[2], S])
        else:
            S = ''.join([S, Query[2]])
print(S)


Fixed submission:
S = input()
Q = int(input())
R = 1  # 1:False, -1:True
P = []
B = []
for _ in range(Q):
    Query = [i for i in input().split()]
    if Query[0] == '1':
        R *= -1
    else:
        if R == 1:
            if Query[1] == '1':
                P.append(Query[2])
            else:
                B.append(Query[2])
        else:
            if Query[1] == '1':
                B.append(Query[2][::-1])
            else:
                P.append(Query[2][::-1])

ans = ''.join(P[::-1])+S+''.join(B)
if R == -1:
    ans = ans[::-1]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
for _ in range(Q):
    Query = [i for i in input().split()]
    if Query[0] == '1':
        S = S[::-1]
    else:
        if Query[1] == '1':
            S = Query[2]+S
        else:
            S = S+Query[2]
print(S)


Fixed submission:
S = input()
Q = int(input())
R = 1  # 1:False, -1:True
P = []
B = []
for _ in range(Q):
    Query = [i for i in input().split()]
    if Query[0] == '1':
        R *= -1
    else:
        if R == 1:
            if Query[1] == '1':
                P.append(Query[2])
            else:
                B.append(Query[2])
        else:
            if Query[1] == '1':
                B.append(Query[2][::-1])
            else:
                P.append(Query[2][::-1])

ans = ''.join(P[::-1])+S+''.join(B)
if R == -1:
    ans = ans[::-1]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())
Q = int(input())

for _ in range(Q):
    qt, q1, q2 = input().split()
    if qt == '1':
        S[int(q1)-1] = q2
    else:
        print(len(set(S[int(q1)-1:int(q2)])))


Fixed submission:
N = int(input())
S = list(input())
Q = int(input())

'''
'init(a)': 配列aで初期化。O(N)
'update(k,x)': a[k]をxに変更 O(logN)
'query(p,q)': [p,q)について "segfunc" したものを返す O(logN)
'ide_ele' : 単位元。
'''

#####segfunc######


def segfunc(x, y):
    return x | y


def init(init_val):
    # set_val
    for i in range(N):
        seg[i+num-1] = init_val[i]
    # built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])


def update(k, x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1], seg[k*2+2])


def query(p, q):
    if q <= p:
        return ide_ele
    p += num-1
    q += num-2
    res = ide_ele
    while q-p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


#####単位元######
ide_ele = 0

# num:n以上の最小の2のべき乗
num = 2**(N-1).bit_length()
seg = [ide_ele]*2*num


init_val = []
for s in S:
    init_val.append(1 << (ord(s)-ord('a')))
init(init_val)

for _ in range(Q):
    t, s, u = input().split()
    if t == '1':
        update(int(s)-1, 1 << (ord(u)-ord('a')))
    else:
        print(bin(query(int(s)-1, int(u))).count('1'))
Buggy python submission (verdict: Runtime Error):
import fractions
import functools
N, M = map(int, input().split())
A = [int(i) for i in input().split()]


def multiple(a, b):
    return a*b // fractions.gcd(a, b)


def lcm(nums):
    return functools.reduce(multiple, nums)


lcm = lcm(A)
hlcm = lcm//2
# print(lcm, hlcm)
for a in A:
    if a % 2 == 1:
        print(0)
        exit()
    if lcm//a % 2 == 0:
        print(0)
        exit()

if hlcm > M:
    print(0)
else:
    print(M//hlcm//2+1)


Fixed submission:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()

mod = 10**9+7  # 出力の制限


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


maxn = 10**5+10
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, maxn + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


ans = 0
for i in range(N-K+1):
    x = cmb(N-i, K, mod)-cmb(N-i-1, K, mod)
    ans -= A[i]*x
    ans += A[N-1-i]*x
    ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

ans = 0
for k in range(K):
    dp = [[0] * 3 for i in range(N+1)]
    for i in range(N+1):
        # print(i)
        if k+i*K >= N:
            break

        if T[k+i*K] == 'r':
            dp[i+1][0] = max(dp[i][1], dp[i][2])
            dp[i+1][1] = max(dp[i][0], dp[i][2])
            dp[i+1][2] = max(dp[i][0]+P, dp[i][1]+P)

        elif T[k+i*K] == 's':
            dp[i+1][0] = max(dp[i][1]+R, dp[i][2]+R)
            dp[i+1][1] = max(dp[i][0], dp[i][2])
            dp[i+1][2] = max(dp[i][0], dp[i][1])

        else:
            dp[i+1][0] = max(dp[i][1], dp[i][2])
            dp[i+1][1] = max(dp[i][0]+S, dp[i][2]+S)
            dp[i+1][2] = max(dp[i][0], dp[i][1])
        # print(max(dp[i]))
    ans += max(dp[i])
print(ans)


Fixed submission:
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

dp = [[0] * 3 for i in range(N+1)]
for i in range(1, N+1):
    # print(i)

    if T[i-1] == 'r':
        if i < K:
            dp[i][0] = 0
            dp[i][1] = 0
            dp[i][2] = P
        else:
            dp[i][0] = max(dp[i-K][1], dp[i-K][2])
            dp[i][1] = max(dp[i-K][0], dp[i-K][2])
            dp[i][2] = max(dp[i-K][0]+P, dp[i-K][1]+P)

    elif T[i-1] == 's':
        if i < K:
            dp[i][0] = R
            dp[i][1] = 0
            dp[i][2] = 0
        else:
            dp[i][0] = max(dp[i-K][1]+R, dp[i-K][2]+R)
            dp[i][1] = max(dp[i-K][0], dp[i-K][2])
            dp[i][2] = max(dp[i-K][0], dp[i-K][1])

    else:
        if i < K:
            dp[i][0] = 0
            dp[i][1] = S
            dp[i][2] = 0
        else:
            dp[i][0] = max(dp[i-K][1], dp[i-K][2])
            dp[i][1] = max(dp[i-K][0]+S, dp[i-K][2]+S)
            dp[i][2] = max(dp[i-K][0], dp[i-K][1])
    # print(max(dp[i]))
ans = 0
for i in range(K):
    ans += max(dp[N-i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)

done = [[False] * N for i in range(N)]

hq = [(-A[0]*2, 0, 0)]
done[0][0] = True
heapq.heapify(hq)  # リストhqのheap化

ans = 0
c = 0
while c < M:
    v, i, j = heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力
    ans -= v
    c += 1

    if i+1 < N and done[i+1][j] is False:
        heapq.heappush(hq, (-A[i+1]-A[j], i+1, j))  # heap化されたリストhqに要素xを追加
        done[i+1][j] = True

    if j+1 < N and done[i][j+1] is False:
        heapq.heappush(hq, (-A[i]-A[j+1], i, j+1))  # heap化されたリストhqに要素xを追加
        done[i][j+1] = True

print(ans)


Fixed submission:
from itertools import accumulate
import bisect
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()

OK = 0
NG = max(A)*2+1
c = 0
# 幸福度がmid点以上上がる握手をM回できるか
while NG-OK > 1:
    mid = (OK+NG)//2
    cnt = 0

    for a in A:
        cnt += N-bisect.bisect_left(A, mid-a)

    if cnt >= M:
        OK = mid
    else:
        NG = mid

S = list(accumulate(A))

ans = 0
c = 0
for a in A:
    idx = bisect.bisect_right(A, OK-a)
    if idx >= 1:
        ans += a*(N-idx)+S[-1]-S[idx-1]
    else:
        ans += a*(N-idx)+S[-1]

    c += N-idx
ans += OK*(M-c)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)

done = [[False] * N for i in range(N)]

hq = [(-A[0]*2, 0, 0)]
done[0][0] = True
heapq.heapify(hq)  # リストhqのheap化

ans = 0
c = 0
while c < M:
    v, i, j = heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力
    ans -= v
    c += 1

    if i+1 < N and done[i+1][j] is False:
        heapq.heappush(hq, (-A[i+1]-A[j], i+1, j))  # heap化されたリストhqに要素xを追加
        done[i+1][j] = True

    if j+1 < N and done[i][j+1] is False:
        heapq.heappush(hq, (-A[i]-A[j+1], i, j+1))  # heap化されたリストhqに要素xを追加
        done[i][j+1] = True

print(ans)


Fixed submission:
from itertools import accumulate
import bisect
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()

OK = 0
NG = max(A)*2+1
c = 0
# 幸福度がmid点以上上がる握手をM回できるか
while NG-OK > 1:
    mid = (OK+NG)//2
    cnt = 0

    for a in A:
        cnt += N-bisect.bisect_left(A, mid-a)

    if cnt >= M:
        OK = mid
    else:
        NG = mid

S = list(accumulate(A))

ans = 0
c = 0
for a in A:
    idx = bisect.bisect_right(A, OK-a)
    if idx >= 1:
        ans += a*(N-idx)+S[-1]-S[idx-1]
    else:
        ans += a*(N-idx)+S[-1]

    c += N-idx
ans += OK*(M-c)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
mod = 10**9 + 7
A = sorted([int(i) for i in input().split()])
bits = [0]*61

ans = 0
for i, a in enumerate(A):
    for b in range(len(bin(a))-2):
        if (a >> b) & 1:
            ans += (2**b)*(i-bits[b])
            bits[b] += 1
        else:
            ans += (2**b)*bits[b]
    ans %= mod
print(ans)


Fixed submission:
import numpy as np

N = int(input())
mod = 10**9 + 7
A = np.array(input().split(), dtype=np.int64)
# print(A)

ans = 0
for i in range(60):
    b = np.count_nonzero(A >> i & 1)
    ans += 2**i*(b*(N-b))
    ans %= mod
    # c = np.count_nonzero(A >> i)
    # print(c)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9 + 7
bits = [0]*61

ans = 0
for i, a in enumerate(A):
    for b in range(60):
        if (a >> b) & 1:
            ans += (2**b)*(i-bits[b])
            bits[b] += 1
        else:
            ans += (2**b)*bits[b]
    ans %= mod
print(ans)


Fixed submission:
import numpy as np

N = int(input())
mod = 10**9 + 7
A = np.array(input().split(), dtype=np.int64)
# print(A)

ans = 0
for i in range(60):
    b = np.count_nonzero(A >> i & 1)
    ans += 2**i*(b*(N-b))
    ans %= mod
    # c = np.count_nonzero(A >> i)
    # print(c)
print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect
N = int(input())
A = [int(i) for i in input().split()]
g = sum(A)/2

S = []
s = 0
for a in A:
    s += a
    S.append(s)

i = bisect.bisect_left(S, g)

if int(g) in S:
    print(0)
else:
    print(min(S[i]-S[i-1], S[i+1]-S[i]))


Fixed submission:
import bisect
import math

N = int(input())
A = [int(i) for i in input().split()]
sa = sum(A)
g = sa/2

S = []
s = 0
for a in A:
    s += a
    S.append(s)


i = bisect.bisect_left(S, g)
print(min(math.ceil(sa-S[i-1]*2), math.ceil(S[i]*2-sa)))
Buggy python submission (verdict: Runtime Error):
import math
a, b, x = map(int, input().split())

if a**2*b == x:
    print(0)
if x > (a**2*b)/2:
    p = a/(2*(b-x/a**2))
    print(90-math.degrees(math.atan(p)))
else:
    p = 2*x/(a*b**2)
    print(90-math.degrees(math.atan(p)))


Fixed submission:
import math
a, b, x = map(int, input().split())

if a**2*b == x:
    print(0)
elif x > (a**2*b)/2:
    p = a/(2*(b-x/a**2))
    print(90-math.degrees(math.atan(p)))
else:
    p = 2*x/(a*b**2)
    print(90-math.degrees(math.atan(p)))