Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
C = list(map(int, input().split()))

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1)
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += 2 ** (n-2)
    pattern %= mod
    ans %= mod

print(ans*(2**n) % mod)

Fixed submission:
n = int(input())
C = list(map(int, input().split()))

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1) % mod
d = 2 ** (n-2) % mod
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += d
    pattern %= mod
    ans %= mod

print(ans*(2**n) % mod)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
C = list(map(int, input().split()))

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1)
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += 2 ** (n-2)
    ans %= mod

print(ans*(2**n) % mod)

Fixed submission:
n = int(input())
C = list(map(int, input().split()))

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1) % mod
d = 2 ** (n-2) % mod
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += d
    pattern %= mod
    ans %= mod

print(ans*(2**n) % mod)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
C = list(map(int, input().split()))

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1)
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += 2 ** (n-2)
    ans %= mod

print(ans*(2**n) % mod)

Fixed submission:
n = int(input())
C = list(map(int, input().split()))

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1) % mod
d = 2 ** (n-2) % mod
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += d
    pattern %= mod
    ans %= mod

print(ans*(2**n) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq


n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

idx_dict = {}
for i in range(n):
    idx_dict[i] = i+1

ans = [A[i]+A[i] for i in range(n)]
candidates = [[-(A[i]+A[i+1]), i] for i in range(n-1)]
heapq.heapify(candidates)

for i in range(m//2):
    if not candidates:
        break
    num, idx = heapq.heappop(candidates)
    ans.append(-num)
    ans.append(-num)
    idx_dict[idx] += 1
    new_pair = idx_dict[idx]
    if new_pair >= n:
        continue
    candidate = A[idx] + A[new_pair]
    heapq.heappush(candidates, [-candidate, idx])

ans.sort(reverse=True)
print(sum(ans[:m]))

Fixed submission:
n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
cumsumA = []

total = 0
for a in A:
    total += a
    cumsumA.append(total)
cumsumA.append(0)

l = 0
r = 10 ** 6
while l + 1 < r:
    num = (l+r)//2
    pair_idx = n-1
    count = 0
    for a in A:
        while a + A[pair_idx] < num and pair_idx >= 0:
            pair_idx -= 1

        count += pair_idx+1

    if count < m:
        r = num
        continue
    elif count >= m:
        l = num


ans = 0
count = 0
num = l
pair_idx = n-1
for a in A:
    while a + A[pair_idx] < num and pair_idx >= 0:
        pair_idx -= 1

    count += pair_idx+1
    ans += cumsumA[pair_idx] + a*(pair_idx+1)

diff = count - m
ans -= num * diff
print(ans)

Buggy python submission (verdict: Runtime Error):
import heapq


n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

idx_dict = {}
for i in range(n):
    idx_dict[i] = i+1

ans = [A[i]+A[i] for i in range(n)]
candidates = [[-(A[i]+A[i+1]), i] for i in range(n-1)]
heapq.heapify(candidates)

for i in range(m//2):
    num, idx = heapq.heappop(candidates)
    ans.append(-num)
    ans.append(-num)
    idx_dict[idx] += 1
    new_pair = idx_dict[idx]
    if new_pair >= n:
        continue
    candidate = A[idx] + A[new_pair]
    heapq.heappush(candidates, [-candidate, idx])

ans.sort(reverse=True)
print(sum(ans[:m]))

Fixed submission:
n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
cumsumA = []

total = 0
for a in A:
    total += a
    cumsumA.append(total)
cumsumA.append(0)

l = 0
r = 10 ** 6
while l + 1 < r:
    num = (l+r)//2
    pair_idx = n-1
    count = 0
    for a in A:
        while a + A[pair_idx] < num and pair_idx >= 0:
            pair_idx -= 1

        count += pair_idx+1

    if count < m:
        r = num
        continue
    elif count >= m:
        l = num


ans = 0
count = 0
num = l
pair_idx = n-1
for a in A:
    while a + A[pair_idx] < num and pair_idx >= 0:
        pair_idx -= 1

    count += pair_idx+1
    ans += cumsumA[pair_idx] + a*(pair_idx+1)

diff = count - m
ans -= num * diff
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


def calc_counts(n, edges):
    counts = [0] * n
    seen = [False] * n
    dfs(0, edges, seen, counts)
    return counts


def dfs(node, edges, seen, counts):
    count = 1
    seen[node] = True
    for to in edges[node]:
        if seen[to]:
            continue
        count += dfs(to, edges, seen, counts)
    counts[node] = count
    return count


def calc_blank(node, counts: list, edges, all, mod=10**9+7):
    n = len(counts)
    paths = edges[node]
    if len(paths) <= 1:
        return 0
    base = counts[node]
    result = all - 1
    for v in paths:
        count = counts[v]
        if count > base:
            count = n - base
        result -= pow(2, count, mod) - 1
        result %= mod

    return result


def main():
    mod = 10**9 + 7
    n = int(input())
    edges = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    counts = calc_counts(n, edges)
    all = pow(2, n-1, mod)
    blanks = 0
    for node in range(n):
        blank = calc_blank(node, counts, edges, all)
        blanks += blank
        blanks %= mod

    inv_denominator = pow(pow(2, n, mod), mod-2, mod)
    ans = blanks * inv_denominator % mod
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
sys.setrecursionlimit(2*10**5)
input = sys.stdin.readline


def calc_counts(n, edges):
    counts = [0] * n
    seen = [False] * n
    dfs(0, edges, seen, counts)
    return counts


def dfs(node, edges, seen, counts):
    count = 1
    seen[node] = True
    for to in edges[node]:
        if seen[to]:
            continue
        count += dfs(to, edges, seen, counts)
    counts[node] = count
    return count


def calc_blank(node, counts: list, edges, all, mod=10**9+7):
    n = len(counts)
    paths = edges[node]
    if len(paths) <= 1:
        return 0
    base = counts[node]
    result = all - 1
    for v in paths:
        count = counts[v]
        if count > base:
            count = n - base
        result -= pow(2, count, mod) - 1
        result %= mod

    return result


def main():
    mod = 10**9 + 7
    n = int(input())
    edges = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    counts = calc_counts(n, edges)
    all = pow(2, n-1, mod)
    blanks = 0
    for node in range(n):
        blank = calc_blank(node, counts, edges, all)
        blanks += blank
        blanks %= mod

    inv_denominator = pow(pow(2, n, mod), mod-2, mod)
    ans = blanks * inv_denominator % mod
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
inf = float('INF')
A = []
B = []

for i in range(h):
    line = list(map(int, input().split()))
    A.append(line)

for i in range(h):
    line = list(map(int, input().split()))
    B.append(line)

D = [[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        D[i][j] = abs(A[i][j] - B[i][j])


def slide_down(y, x, possible: set):
    new = set()
    delta = D[y+1][x]
    for num in possible:
        if num + delta <=6400:
            new.add(num+delta)
        if abs(num-delta) <= 6400:
            new.add(abs(num-delta))
    return new


def slide_right(y, x, possible: set):
    new = set()
    delta = D[y][x+1]
    for num in possible:
        if num + delta <=6400:
            new.add(num+delta)
        if abs(num-delta) <=6400:
            new.add(abs(num-delta))
    return new


DP = [[set() for j in range(w)] for i in range(h)]
DP[0][0] = {D[0][0]}
for row in range(h):
    for col in range(w):
        possible = DP[row][col]
        if col < w-1:
            new = slide_right(row, col, possible)
            DP[row][col+1] |= new
        if row < h-1:
            new = slide_down(row, col, possible)
            DP[row+1][col] |= new

ans = min(DP[h-1][w-1])
print(ans)


Fixed submission:
A = list(map(int, input().split()))
if sum(A) >= 22:
    print('bust')
else:
    print('win')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

bit_count = [0] * 60
ans = 0
for a in A:
    for bit in range(60):
        if (a >> bit) & 1:
            count = bit_count[bit]
            ans += (2 ** bit) * (n-1-count*2)
            bit_count[bit] += 1
            ans %= mod
        else:
            continue

print(ans)

Fixed submission:
n = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

bit_count = [0] * 60
ans = 0
for a in A:
    for bit in range(60):
        if (a >> bit) & 1:
            count = bit_count[bit]
            ans += (2 ** bit) * (n-1-count*2)
            bit_count[bit] += 1
            ans %= mod
        else:
            continue

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
mod = 10**9 + 7

def main():
    n = int(input())
    A = list(map(int, input().split()))
    candidates = [0] * n
    candidates[0] = 3
    ans = 1

    for a in A:
        ans *= candidates[a]
        ans %= mod
        candidates[a] -= 1
        candidates[a+1] += 1

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
n = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

ans = 3
hats = [1, 0, 0]

if n == 1:
    if A[0] == 0:
        print(3)
    else:
        print(0)
    exit()


if A[0] != 0:
    print(0)
    exit()
for a in A[1:]:
    count = hats.count(a)
    if count == 0:
        print(0)
        exit()

    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod

print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

ans = 3
hats = [1, 0, 0]

for a in A[1:]:
    count = hats.count(a)
    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod

print(ans)

Fixed submission:
n = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

ans = 3
hats = [1, 0, 0]

if n == 1:
    if A[0] == 0:
        print(3)
    else:
        print(0)
    exit()


if A[0] != 0:
    print(0)
    exit()
for a in A[1:]:
    count = hats.count(a)
    if count == 0:
        print(0)
        exit()

    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.read


n, *ab = map(int, read().split())
ans = [0]*(n-1)
edges = [[]for _ in range(n)]
used = [0]*n

for i, a, b in zip(range(n-1), *[iter(ab)] * 2):
    edges[a].append([b, i])

for node in range(n):
    unable = used[node]
    color = 1

    for to, id in edges[node]:
        if color == unable:
            color += 1
        ans[id] = str(color)
        used[to] = color
        color += 1

print(max(used))
print('\n'.join(ans))

Fixed submission:
import sys
input = sys.stdin.readline


n = int(input())
routes = []
dic = [{}] * n
edges = [[]for _ in range(n)]
used = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    routes.append([a-1, b-1])
    edges[a-1].append(b-1)

for node in range(n):
    unanle = used[node]
    count = 1
    if count == unanle:
        count += 1
    for to in edges[node]:
        dic[node][to] = count
        used[to] = count
        count += 1
        if count == unanle:
            count += 1

print(max(used))
for _from, to in routes:
    print(dic[_from][to])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


n = int(input())
routes = []
ans = [[0]*n for i in range(n)]
edges = [[]for _ in range(n)]
used = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    routes.append([a-1, b-1])
    edges[a-1].append(b-1)

sort_routes = sorted(routes)

for node in range(n):
    unanle = used[node]
    count = 1
    if count == unanle:
        count += 1
    for to in edges[node]:
        ans[node][to] = count
        used[to] = count
        count += 1
        if count == unanle:
            count += 1

print(max(used))
for _from, to in routes:
    print(ans[_from][to])

Fixed submission:
import sys
input = sys.stdin.readline


n = int(input())
routes = []
dic = [{}] * n
edges = [[]for _ in range(n)]
used = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    routes.append([a-1, b-1])
    edges[a-1].append(b-1)

for node in range(n):
    unanle = used[node]
    count = 1
    if count == unanle:
        count += 1
    for to in edges[node]:
        dic[node][to] = count
        used[to] = count
        count += 1
        if count == unanle:
            count += 1

print(max(used))
for _from, to in routes:
    print(dic[_from][to])
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
S = input()

ans = []
x = len(S) - 1
while x:
    for step in range(m, 0, -1):
        to = S[x-step]
        if x - step < 0:
            continue
        if to == '1':
            continue
        else:
            x -= step
            ans.append(str(step))
            break
    else:
        print(-1)
        exit()

print(' '.join(ans[::-1]))


Fixed submission:
n, m = map(int, input().split())
S = input()

ans = []
x = len(S) - 1
while x:
    for step in range(m, 0, -1):
        if x - step < 0:
            continue
            
        to = S[x-step]
        if to == '1':
            continue
        else:
            x -= step
            ans.append(str(step))
            break
    else:
        print(-1)
        exit()

print(' '.join(ans[::-1]))
Buggy python submission (verdict: Time Limit Exceeded):
n, t = map(int, input().split())
dishes = []

for _ in range(n):
    time, point = map(int, input().split())
    dishes.append([time, point])

dishes.sort()

DP = [0] * t

candidates = []
for time, point in dishes:
    candidates.append(max(DP) + point)

    for i in range(t-1, time-1, -1):
        DP[i] = max(DP[i], DP[i-time]+point)

print(max(candidates))

Fixed submission:
from collections import defaultdict


n, t = map(int, input().split())

dish = []

for _ in range(n):
    time, point = map(int, input().split())
    dish.append([time, point])

dish.sort()
DP = [[0]*t for i in range(n+1)]
ans = defaultdict(int)

for i in range(1, n+1):
    time, point = dish[i-1]

    for j in range(t):
        DP[i][j] = max(DP[i-1][j], DP[i][j])
        if j + time >= t:
            ans[i] = max(DP[i-1][j]+point, ans[i])
            continue
        DP[i][j+time] = max((DP[i-1][j] + point), DP[i-1][j+time])

res = max(ans.values())
print(res)

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


n, t = map(int, input().split())

dish = []

for _ in range(n):
    time, point = map(int, input().split())
    dish.append([time, point])

dish.sort()
DP = [[0]*t for i in range(n+1)]
ans = defaultdict(int)

for i in range(1, n+1):
    time, point = dish[i-1]

    for j in range(t):
        DP[i][j] = max(DP[i-1][j], DP[i][j])
        if j + time >= t:
            ans[i] = max(DP[i-1][j]+point, ans[i])
            continue
        DP[i][j+time] = max((DP[i-1][j] + point), DP[i-1][j+time])

res = max(ans.values())
print(res)

Fixed submission:
from collections import defaultdict


n, t = map(int, input().split())

dish = []

for _ in range(n):
    time, point = map(int, input().split())
    dish.append([time, point])

dish.sort()
DP = [[0]*t for i in range(n+1)]
ans = defaultdict(int)

for i in range(1, n+1):
    time, point = dish[i-1]

    for j in range(t):
        DP[i][j] = max(DP[i-1][j], DP[i][j])
        if j + time >= t:
            ans[i] = max(DP[i-1][j]+point, ans[i])
            continue
        DP[i][j+time] = max((DP[i-1][j] + point), DP[i-1][j+time])

res = max(ans.values())
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for _ in range(m):
    _from, to, dist = map(int, input().split())
    edges[_from-1][to-1] = dist

for i in range(1, n):
    edges[i][i-1] = 0

G = csgraph_from_dense(edges, null_value=float('INF'))
D = dijkstra(G, directed=True, indices=0)
ans = D[-1]
if ans == float('INF'):
    ans = -1
print(int(ans))

Fixed submission:
import heapq
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

edges = [[] for _ in range(n)]
for i in range(1, n):
    _from, to, dist = i, i-1, 0
    edges[_from].append([to, dist])

for _ in range(m):
    _from, to, dist = map(int, input().split())
    edges[_from-1].append([to-1, dist])


D = [float('INF')]*n
D[0] = 0
todo = []
for to, dist in edges[0]:
    heapq.heappush(todo, [dist, to])
    D[to] = dist

while todo:
    total_dist, node = heapq.heappop(todo)

    for to, dist in edges[node]:
        if total_dist + dist < D[to]:
            heapq.heappush(todo, [total_dist+dist, to])
            D[to] = total_dist + dist
        else:
            continue

ans = D[n-1]
if ans == float('INF'):
    ans = -1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


n, m = map(int, input().split())
edges = []
for _ in range(m):
    l, r, c = map(int, input().split())
    edges.append([l-1, r-1, c])

edges.sort()

DP = [float('INF')] * n
DP[0] = 0

for l, r, c in edges:
    for i in range(l+1, r+1):
        DP[i] = min(DP[i], DP[l]+c)

ans = DP[n-1]
if ans == float('INF'):
    ans = -1
print(ans)


Fixed submission:
import heapq
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

edges = [[] for _ in range(n)]
for i in range(1, n):
    _from, to, dist = i, i-1, 0
    edges[_from].append([to, dist])

for _ in range(m):
    _from, to, dist = map(int, input().split())
    edges[_from-1].append([to-1, dist])


D = [float('INF')]*n
D[0] = 0
todo = []
for to, dist in edges[0]:
    heapq.heappush(todo, [dist, to])
    D[to] = dist

while todo:
    total_dist, node = heapq.heappop(todo)

    for to, dist in edges[node]:
        if total_dist + dist < D[to]:
            heapq.heappush(todo, [total_dist+dist, to])
            D[to] = total_dist + dist
        else:
            continue

ans = D[n-1]
if ans == float('INF'):
    ans = -1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math

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

def search(x, k, A, F):
    for a, f in zip(A, F):
        time = a * f
        if time <= x:
            continue
        else:
            dif = time - x
            training = int(math.ceil(dif/f))
            k -= training

        if k < 0:
            return False
    return True


A.sort()
F.sort(reverse=True)
r= max([a*f for a, f in zip(A, F)])
l = 0
while l < r:
    candidate = (r+l)//2
    if search(candidate, k, A, F):
        r = candidate
    else:
        l = candidate + 1

print(r)

Fixed submission:
import math

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

def search(x, k, A, F):
    for a, f in zip(A, F):
        time = a * f
        if time <= x:
            continue
        else:
            dif = time - x
            training = int(math.ceil(dif/f))
            k -= training

        if k < 0:
            return False
    return True


A.sort()
F.sort(reverse=True)
r= max([a*f for a, f in zip(A, F)])
l = 0
while l < r:
    candidate = (r+l)//2
    if search(candidate, k, A, F):
        r = candidate
    else:
        l = candidate + 1

print(r)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
edges_from = [[] for _ in range(n)]

for _ in range(m):
    _from, to = map(lambda x: int(x)-1, input().split())
    edges_from[_from].append(to)

E_dist_to_goal = [0] * n
for node in range(n-2, -1, -1):
    routes = edges_from[node]
    num_of_routes = len(routes)
    for next_node in routes:
        dist = E_dist_to_goal[next_node] + 1
        E_dist_to_goal[node] += dist/num_of_routes


def recalculate_dist(node, E_dist_to_goal):
    recal_E_dist = [0]*(node+1)
    routes = edges_from[node]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        return False

    heaviest_route = max(E_dist_to_goal[next_node]+1 for next_node in routes)
    new_dist = E_dist_to_goal[node] - heaviest_route/num_of_routes
    new_dist *= num_of_routes / (num_of_routes - 1)
    recal_E_dist[node] = new_dist

    for v in range(node-1, -1, -1):
        routes = edges_from[v]
        num_of_routes = len(routes)
        for nv in routes:
            if nv > node:
                dist = E_dist_to_goal[nv] + 1
            else:
                dist = recal_E_dist[nv] + 1
            recal_E_dist[v] += dist
        recal_E_dist[v] /= num_of_routes
    return recal_E_dist[0]


ans = [E_dist_to_goal[0]]
for i in range(n-2):
    candidate = recalculate_dist(i, E_dist_to_goal)
    if candidate:
        ans.append(candidate)

print(min(ans))


Fixed submission:
n, m = map(int, input().split())
edges_from = [[] for _ in range(n)]

for _ in range(m):
    _from, to = map(lambda x: int(x)-1, input().split())
    edges_from[_from].append(to)

E_dist_to_goal = [0] * n
for node in range(n-2, -1, -1):
    routes = edges_from[node]
    num_of_routes = len(routes)
    for next_node in routes:
        dist = E_dist_to_goal[next_node] + 1
        E_dist_to_goal[node] += dist/num_of_routes


def recalculate_dist(node, E_dist_to_goal):
    recal_E_dist = [0]*(node+1)
    routes = edges_from[node]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        return False

    heaviest_route = max(E_dist_to_goal[next_node]+1 for next_node in routes)
    new_dist = E_dist_to_goal[node] - heaviest_route/num_of_routes
    new_dist *= num_of_routes / (num_of_routes - 1)
    recal_E_dist[node] = new_dist

    for v in range(node-1, -1, -1):
        routes = edges_from[v]
        num_of_routes = len(routes)
        for nv in routes:
            if nv > node:
                dist = E_dist_to_goal[nv] + 1
            else:
                dist = recal_E_dist[nv] + 1
            recal_E_dist[v] += dist
        recal_E_dist[v] /= num_of_routes
    return recal_E_dist[0]


ans = [E_dist_to_goal[0]]
for i in range(n-2):
    candidate = recalculate_dist(i, E_dist_to_goal)
    if candidate:
        ans.append(candidate)

print(min(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
print(sum(range(1, n)))


Fixed submission:
n = int(input())

ans = n*(n-1)//2
print(ans)