Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

#X[l][r]はlからrをちょうど走る電車の数
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l, r in LR:
    X[l][r] += 1
cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        cum[i][j] = cum[i][j-1] + X[i][j]

outputs = []
for p, q in PQ:
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][p-1]
    outputs.append(ans)

print('\n'.join(map(str, outputs)))


Fixed submission:
N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

#X[l][r]はlからrをちょうど走る電車の数
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l, r in LR:
    X[l][r] += 1
cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        cum[i][j] = cum[i][j-1] + X[i][j]

for p, q in PQ:
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][p-1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

#X[l][r]はlからrをちょうど走る電車の数
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l, r in LR:
    X[l][r] += 1
cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        cum[i][j] = cum[i][j-1] + X[i][j]

for p, q in PQ:
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][p-1]
    print(ans)

Fixed submission:
N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

#X[l][r]はlからrをちょうど走る電車の数
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l, r in LR:
    X[l][r] += 1
cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        cum[i][j] = cum[i][j-1] + X[i][j]

for p, q in PQ:
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][p-1]
    print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
if n % 4 == 0: print('Yes')
elif n >= 7 && n % 4 == 3: print('Yes')
elif n >= 14 && n % 4 == 2: print('Yes')
elif n >= 21 && n % 4 == 1: print('Yes')
else: print('No')

Fixed submission:
n = int(input())
if n % 4 == 0: print('Yes')
elif n >= 7 and n % 4 == 3: print('Yes')
elif n >= 14 and n % 4 == 2: print('Yes')
elif n >= 21 and n % 4 == 1: print('Yes')
else: print('No')
Buggy python submission (verdict: Runtime Error):
A=map(int,input().split());print(max(A)-min(A))

Fixed submission:
A=list(map(int,input().split()));print(max(A)-min(A))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
six = [6**i for i in range(7)]
nine = [9**i for i in range(6)]
L = []
for s in six:
  L.append(s)
for s in nine[1:]:
  L.append(s)
L.sort(reverse=True)
ans = 0
for l in L:
  while N > 0:
    ans += N // l
    N %= l
print(ans)

Fixed submission:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def get_num_draw(n, x):
    res = 0
    while n > 0:
        res += n % x
        n = n // x
    return res


def main():
    N = NI()
    ans = 10**10
    for i in range(0, N+1, 6):
        ans = min(get_num_draw(N-i, 9) + get_num_draw(i//6, 6), ans)
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
N=int(input());print("Three" if len(set(map(input().split())))==3 else "Four")

Fixed submission:
N=int(input());print("Three" if len(set(input().split()))==3 else "Four")

Buggy python submission (verdict: Runtime Error):
N=int(input());print("Three" if len(set(map(int,input().split())))==3 else "Four")

Fixed submission:
N=int(input());print("Three" if len(set(input().split()))==3 else "Four")
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = sorted(list(map(int, input().split())), reversed=True)
if N == 1:
  print(A[0])
  exit()
print(sum(A[0::2]) - sum(A[1::2]))

Fixed submission:
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
if N == 1:
  print(A[0])
  exit()
print(sum(A[0::2]) - sum(A[1::2]))
Buggy python submission (verdict: Runtime Error):
import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
BoverA = [0] * N
CoverB = [0] * N
for i in range(N):
    BoverA[i] = N - bisect.bisect_right(B, A[i])
    CoverB[i] = N - bisect.bisect_right(C, B[i])
cumBC = [0] * N
cumBC[N-1] = CoverB[N-1]
for i in range(N-2, -1, -1):
    cumBC[i] = cumBC[i+1] + CoverB[i]
ans = 0
for i in range(N):
    ans += cumBC[N - BoverA[i]]
print(ans)

Fixed submission:
import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
BoverA = [0] * N
CoverB = [0] * N
for i in range(N):
    BoverA[i] = N - bisect.bisect_right(B, A[i])
    CoverB[i] = N - bisect.bisect_right(C, B[i])
cumBC = [0] * N
cumBC[N-1] = CoverB[N-1]
for i in range(N-2, -1, -1):
    cumBC[i] = cumBC[i+1] + CoverB[i]
ans = 0
for i in range(N):
    if N - BoverA[i] >= 0 and N - BoverA[i] < N:
        ans += cumBC[N - BoverA[i]]
print(ans)
Buggy python submission (verdict: Runtime Error):
R,G=map(int,input().split())
print(G*2-R)

Fixed submission:
R=int(input())
G=int(input())
print(G*2-R)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
for h in range(1, 3501):
  for n in range(1, 3501):
    a = N*h*n
    b = 4*h*n - N*n - N*h
    if b == 0:
      continue
    if a % b:
      continue
    if a//b < 0:
      continue
    print(h, n, a//b)
    exit()


Fixed submission:
N = int(input())
for h in range(1, 3501):
  for n in range(1, 3501):
    a = N*h*n
    b = 4*h*n - N*n - N*h
    if b == 0:
      continue
    if a % b:
      continue
    if a//b < 0:
      continue
    print(h, n, a//b)
    exit()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
for h in range(1, 3501):
  for n in range(1, 3501):
    a = N*h*n
    b = 4*h*n - N*n - N*h
    if b == 0:
      continue
    if a % b:
      continue
    print(h, n, a//b)


Fixed submission:
N = int(input())
for h in range(1, 3501):
  for n in range(1, 3501):
    a = N*h*n
    b = 4*h*n - N*n - N*h
    if b == 0:
      continue
    if a % b:
      continue
    if a//b < 0:
      continue
    print(h, n, a//b)
    exit()

Buggy python submission (verdict: Runtime Error):
N = int(input())
for h in range(1, 3501):
  for n in range(1, 3501):
    a = N*h*n
    b = 4*h*n - N*n - N*h
    if a % b:
      continue
    print(h, n, a//b)

Fixed submission:
N = int(input())
for h in range(1, 3501):
  for n in range(1, 3501):
    a = N*h*n
    b = 4*h*n - N*n - N*h
    if b == 0:
      continue
    if a % b:
      continue
    if a//b < 0:
      continue
    print(h, n, a//b)
    exit()
Buggy python submission (verdict: Runtime Error):
N,K,*A=map(int,open(0))
print(sum([min(a,K-a)*2 for a in A]))

Fixed submission:
N = int(input())
K = int(input())
*A, = map(int, input().split())
print(sum([min(a,K-a)*2 for a in A]))

Buggy python submission (verdict: Runtime Error):
N = int(input())
K = int(input())
*A = map(int, input().split())
print(sum([min(a,K-a)*2 for a in A]))

Fixed submission:
N = int(input())
K = int(input())
*A, = map(int, input().split())
print(sum([min(a,K-a)*2 for a in A]))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for i in range(N)]
A = sorted(A)
ans = 0
prev = A[0]
cnt = 0
for a in A:
    if prev == a:
        cnt += 1
        prev = a
    else:
        if cnt % 2 == 1:
            ans += 1
        cnt = 1
        prev = a
if cnt %= 1:
    ans += 1
print(ans)

Fixed submission:
N = int(input())
A = [int(input()) for i in range(N)]
A = sorted(A)
ans = 0
prev = A[0]
cnt = 0
for a in A:
    if prev == a:
        cnt += 1
        prev = a
    else:
        if cnt % 2 == 1:
            ans += 1
        cnt = 1
        prev = a
if cnt % 2 == 1:
    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque
from itertools import permutations

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M, R = NMI()
    targets = NLI()
    targets = [t-1 for t in targets]
    dist = [[10**9] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = NMI()
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    for i in range(N):
        dist[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = 10**9
    for case in permutations(targets, R):
        now = case[0]
        cost = 0
        for goto in case[1:]:
            cost += dist[now][goto]
            now = goto
        ans = min(ans, cost)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque
from itertools import permutations

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M, R = NMI()
    targets = NLI()
    targets = [t-1 for t in targets]
    dist = [[10**9] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = NMI()
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    for i in range(N):
        dist[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = 10**9
    for case in permutations(targets, R):
        now = case[0]
        cost = 0
        for goto in case[1:]:
            cost += dist[now][goto]
            now = goto
        ans = min(ans, cost)
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from math import gcd
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
gcm = 10**9+7
for i in range(N-1):
    gcm = min(gcm, gcd(A[i], A[i+1]))
if N == 1:
    print('IMPOSSIBLE')
    exit()

print('POSSIBLE' if K % gcm == 0 and K <= A[0] else 'IMPOSSIBLE')

Fixed submission:
from fractions import gcd
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
gcm = 10**9+7
for i in range(N-1):
    gcm = min(gcm, gcd(A[i], A[i+1]))
if N == 1:
    print('IMPOSSIBLE' if K != A[0] else 'POSSIBLE')
    exit()

print('POSSIBLE' if K % gcm == 0 and K <= A[0] else 'IMPOSSIBLE')
Buggy python submission (verdict: Time Limit Exceeded):
A, B, C = map(int, input().split())
x, y = abs(A-B), abs(B-C)
ans = 0
if x == 0 and y == 0 and A % 2 == 0:
  print(-1)
  exit()

while x % 2 == 0 and y % 2 == 0:
  x, y = x // 2, y // 2
  ans += 1
print(ans)

Fixed submission:
A, B, C = map(int, input().split())
x, y = abs(A-B), abs(B-C)
ans = 0
if x == 0 and y == 0 and A % 2 == 0:
  print(-1)
  exit()

if x == 0 and y == 0 and A % 2 == 1:
  print(0)
  exit()
  
while x % 2 == 0 and y % 2 == 0:
  x, y = x // 2, y // 2
  ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque
from itertools import combinations
import bisect

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, MA, MB = NMI()
    D = []
    for _ in range(N):
        a, b, c = NMI()
        t = a*MB - b*MA
        D.append((t, c))
    D.sort()

    D1 = D[:N//2]
    D2 = D[N//2:]
    ld1 = len(D1)
    ld2 = len(D2)

    S1 = defaultdict(lambda: 10**5)
    for case in range(2**ld1):
        if case == 0: continue
        s, c = 0, 0
        for i in range(ld1):
            if (case>>i)&1:
                s += D1[i][0]
                c += D1[i][1]
        S1[s] = min(S1[s], c)

    S2 = defaultdict(lambda: 10**5)
    for case in range(2 ** ld2):
        if case == 0: continue
        s, c = 0, 0
        for i in range(ld2):
            if (case >> i) & 1:
                s += D2[i][0]
                c += D2[i][1]
        S2[s] = min(S2[s], c)

    ans = 10**5
    for s, c in list(S1.items()):
        ans = min(ans, c + S2[-s])
    ans = min(ans, S1[0], S2[0])
    if ans >= 10**5:
        print(-1)
    else:
        print(ans)



if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque
from itertools import combinations
import bisect

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, MA, MB = NMI()
    D = []
    for _ in range(N):
        a, b, c = NMI()
        t = a*MB - b*MA
        D.append((t, c))
    D.sort()

    D1 = D[:N//2]
    D2 = D[N//2:]
    ld1 = len(D1)
    ld2 = len(D2)

    S1 = defaultdict(lambda: 10**5)
    for case in range(2**ld1):
        if case == 0: continue
        s, c = 0, 0
        for i in range(ld1):
            if (case>>i)&1:
                s += D1[i][0]
                c += D1[i][1]
        S1[s] = min(S1[s], c)

    S2 = defaultdict(lambda: 10**5)
    for case in range(2 ** ld2):
        if case == 0: continue
        s, c = 0, 0
        for i in range(ld2):
            if (case >> i) & 1:
                s += D2[i][0]
                c += D2[i][1]
        S2[s] = min(S2[s], c)

    ans = 10**5
    for s, c in list(S1.items()):
        ans = min(ans, c + S2[-s])
    ans = min(ans, S1[0], S2[0])
    if ans >= 10**5:
        print(-1)
    else:
        print(ans)



if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
H, W, A, B = map(int, input().split())
INF = 10**9 + 7

def powmod(a, n, mod):
    p = 1
    while n > 0:
        if n % 2 == 0:
            a = a**2 % mod
            n /= 2
        else:
            p *= a
            p %= mod
            n -= 1
    return p


def invmod(a, mod):
    return powmod(a, mod-2, mod)


def combmod(n, k, mod):
    if n < k : return 0
    else:
        if n < 2*k: k = n-k
        bunsi = fac[n]
        bunbo = inv[k] * inv[n-k]
        return bunsi * bunbo % mod

fac = [1] * (H+W+1)
inv = [1] * (H+W+1)
for i in range(H+W+1):
    if i == 0:
        fac[i] = 1
        inv[i] = 1
    else:
        fac[i] = fac[i-1] * i % INF
        inv[i] = inv[i-1] * invmod(i, INF) % INF

ans = 0
for i in range(min(W, H - A + B) - B):
    h = H - A - i
    w = B + 1 + i
    ans += combmod(h+w-2, h-1, INF) * combmod(H+W-h-w, H - h, INF) % INF

print(ans%INF)

Fixed submission:
H, W, A, B = map(int, input().split())
INF = 10**9 + 7

def powmod(a, n, mod):
    p = 1
    while n > 0:
        if n % 2 == 0:
            a = a**2 % mod
            n /= 2
        else:
            p *= a
            p %= mod
            n -= 1
    return p


def invmod(a, mod):
    return powmod(a, mod-2, mod)


def combmod(n, k, mod):
    if n < k : return 0
    else:
        if n < 2*k: k = n-k
        bunsi = fac[n]
        bunbo = inv[k] * inv[n-k]
        return bunsi * bunbo % mod

fac = [1] * (H+W+1)
inv = [1] * (H+W+1)
for i in range(H+W+1):
    if i == 0:
        fac[i] = 1
        inv[i] = 1
    else:
        fac[i] = fac[i-1] * i % INF
        inv[i] = inv[i-1] * invmod(i, INF) % INF

ans = 0
for i in range(min(W, H - A + B) - B):
    h = H - A - i
    w = B + 1 + i
    ans += combmod(h+w-2, h-1, INF) * combmod(H+W-h-w, H - h, INF) % INF

print(ans%INF)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.buffer.readline
r, c, k = map(int, input().split())


graph = [[0] * (c) for _ in range(r)]

for _ in range(k):
    d, e, f = map(int, input().split())
    graph[d - 1][e - 1] = f


# dijkstra
infi = 10 ** 10
money = [[[-infi] * (4) for _ in range(c)] for _ in range(r)]
money[0][0][0] = 0
for i in range(r):
    for j in range(c):
        for t in range(4):
            m = money[i][j][t]
            delta = graph[i][j]
            if i < r - 1:
                ni = i + 1
                nj = j
                nt = 0
                money[ni][nj][nt] = max(money[ni][nj][nt], m)
                if t < 3:
                    money[ni][nj][nt] = max(money[ni][nj][nt], m + delta)

            if j < c - 1:
                ni = i
                nj = j + 1
                nt = t
                money[ni][nj][nt] = max(money[ni][nj][nt], m)
                if t < 3:
                    nt = t + 1
                    money[ni][nj][nt] = max(money[ni][nj][nt], m + delta)


if graph[r - 1][c - 1] > 0:
    for t in range(3):
        money[r - 1][c - 1][t] += graph[r - 1][c - 1]
ans = max(money[r - 1][c - 1])

print(ans)


Fixed submission:
import sys

input = sys.stdin.buffer.readline
r, c, k = map(int, input().split())


graph = [[0] * (c) for _ in range(r)]

for _ in range(k):
    d, e, f = map(int, input().split())
    graph[d - 1][e - 1] = f


infi = 10 ** 10
money = [[[-infi] * (c) for _ in range(r)] for _ in range(4)]
money[0][0][0] = 0
for i in range(r):
    for j in range(c):
        for t in range(4):
            m = money[t][i][j]
            delta = graph[i][j]
            if i < r - 1:
                ni = i + 1
                nj = j
                nt = 0
                money[nt][ni][nj] = max(money[nt][ni][nj], m)
                if t < 3:
                    money[nt][ni][nj] = max(money[nt][ni][nj], m + delta)

            if j < c - 1:
                ni = i
                nj = j + 1
                nt = t
                money[nt][ni][nj] = max(money[nt][ni][nj], m)
                if t < 3:
                    nt = t + 1
                    money[nt][ni][nj] = max(money[nt][ni][nj], m + delta)

ans = 0
if graph[r - 1][c - 1] > 0:
    for t in range(3):
        money[t][r - 1][c - 1] += graph[r - 1][c - 1]
for i in range(4):
    ans = max(money[i][r - 1][c - 1], ans)

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

n = int(input())
jisho = defaultdict(int)
for _ in range(n):
    s = input()
    if int(float(s)) == float(s):
        num = int(float(s))
        cnt2 = 0
        cnt5 = 0
    else:
        a, b = s.split(".")
        keta = len(b)
        cnt2 = -keta
        cnt5 = -keta
        a = int(a)
        b = int(b)
        num = a * pow(10, keta) + b
    while True:
        if num % 5 == 0:
            num //= 5
            cnt5 += 1
        else:
            break
    while True:
        if num % 2 == 0:
            num //= 2
            cnt2 += 1
        else:
            break
    if cnt5 <= -11 or cnt2 <= -11:
        continue
    cnt2 = min(10, cnt2)
    cnt5 = min(10, cnt5)
    jisho[(cnt2, cnt5)] += 1
ans = 0
for i in range(21):
    i -= 10
    for j in range(21):
        j -= 10
        kouho1 = jisho[(i, j)]
        if kouho1 == 0:
            continue
        for k in range(21):
            k -= 10
            for l in range(21):
                l -= 10
                kouho2 = jisho[(k, l)]
                if kouho2 == 0:
                    continue

                if i + k >= 0 and j + l >= 0:
                    if (i, j) == (k, l):
                        ans += kouho1 * (kouho2 - 1)
                    else:
                        ans += kouho1 * kouho2

print(ans // 2)


Fixed submission:
from collections import defaultdict


n = int(input())
jisho = defaultdict(int)
for _ in range(n):
    s = input()
    if int(float(s)) == float(s):
        num = int(float(s))
        cnt2 = 0
        cnt5 = 0
    else:
        a, b = s.split(".")
        keta = len(b)
        cnt2 = -keta
        cnt5 = -keta
        a = int(a)
        b = int(b)
        num = a * pow(10, keta) + b
    while True:
        if num % 5 == 0:
            num //= 5
            cnt5 += 1
        else:
            break
    while True:
        if num % 2 == 0:
            num //= 2
            cnt2 += 1
        else:
            break
    if cnt5 <= -11 or cnt2 <= -11:
        continue
    cnt2 = min(10, cnt2)
    cnt5 = min(10, cnt5)
    jisho[(cnt2, cnt5)] += 1
ans = 0
for i in range(21):
    i -= 10
    for j in range(21):
        j -= 10
        kouho1 = jisho[(i, j)]
        if kouho1 == 0:
            continue
        for k in range(21):
            k -= 10
            for l in range(21):
                l -= 10
                kouho2 = jisho[(k, l)]
                if kouho2 == 0:
                    continue

                if i + k >= 0 and j + l >= 0:
                    if (i, j) == (k, l):
                        ans += kouho1 * (kouho2 - 1)
                    else:
                        ans += kouho1 * kouho2

print(ans // 2)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
# dp = [[[0] * (2) for _ in range(k+1)]for _ in range(n+1)]
# # dp[桁][数][負数の数=1,0]

A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    # 正の数に成る→大きいものがほしい
    # 負の数は偶数個、これの数を決め打つ
    # 計算すると大変だから大小を考える

    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    A_minus = A[:n_minus]

    # 負の数を使う数を決め打つ
    # 最終的に正にできるパターン
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max
    if n_plus < select:
        print(0)
        exit()
    # 負の数にしかできないパターン
    # 遊びがない時に奇数個の負の数を選ばざるを得ない
    # その時に0があるかどうかパターン
    plus_shortage = 0
    minus_shortage = 0
    for i in range(minus_num_max + 1):
        # 各々使う個数
        p = k - 2 * i
        m = 2 * i
        if p - 2 < 0:
            plus_shortage = 1
            break
        if p > n_plus:
            continue
        plus_kouho = A_plus[p - 1] * A_plus[p - 2]
        if m + 1 >= n_minus:
            minus_shortage = 1
            break
        minus_kouho = A_minus[2 * i] * A_minus[2 * i + 1]
        if minus_kouho > plus_kouho:
            ans *= minus_kouho
            ans %= mod
        else:
            break

    for j in range(k - 2 * i):
        ans *= A_plus[j]
        ans %= mod

print(ans)


Fixed submission:
n = int(input())
graph = [[] for _ in range(n)]

edge_sum = 0
for _ in range(n - 1):
    u, v = map(int, input().split())
    if u > v:
        u, v = v, u
    edge_sum += u * (n - v + 1)

dot_sum = n * (n + 1) * (n + 2) // 6
print(dot_sum - edge_sum)