Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a, b = [], []
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)


who = True
dishes = list(range(n))
takahashi = aoki = 0
while dishes:
    if who:
        dishes.sort(key=lambda dish: (b[dish], a[dish]))
        takahashi += a[dishes.pop()]
    else:
        dishes.sort(key=lambda dish: (a[dish], b[dish]))
        aoki += b[dishes.pop()]
    who = not who

print(takahashi - aoki)


Fixed submission:
n = int(input())
dishes = []
for _ in range(n):
    a, b = map(int, input().split())
    dishes.append((a, b, a + b))
dishes.sort(key=lambda dish: dish[2], reverse=True)

x = y = 0
for i in range(n):
    a, b, _ = dishes[i]
    if i % 2 == 0:
        x += a
    else:
        y += b

print(x - y)
Buggy python submission (verdict: Time Limit Exceeded):
import operator
import collections

n, k = map(int, input().split())
sushies = []
for _ in range(n):
    t, d = map(int, input().split())
    sushies.append((t, d))

sushies.sort(key=operator.itemgetter(1), reverse=True)

dishes = sushies[:k]
c = collections.Counter(t for t, d in dishes)
a = sum(d for t, d in dishes)
answer = a + len(c) ** 2

for t, d in sushies[k:]:
    if t in c:
        continue

    x = -1
    for i in reversed(range(k)):
        if c[dishes[i][0]] > 1:
            x = i
            break

    if x == -1:
        break

    a = a + d - dishes[x][1]
    c[t] += 1
    c[dishes[x][0]] -= 1
    del dishes[x]
    dishes.append((t, d))

    answer = max(answer, a + len(c) ** 2)

print(answer)


Fixed submission:
import operator
import collections

n, k = map(int, input().split())
sushies = []
for _ in range(n):
    t, d = map(int, input().split())
    sushies.append((t, d))

sushies.sort(key=operator.itemgetter(1), reverse=True)

dishes = sushies[:k]
c = collections.Counter(t for t, d in dishes)
a = sum(d for t, d in dishes)
answer = a + len(c) ** 2
x = k - 1
for t, d in sushies[k:]:
    if t in c:
        continue

    while x >= 0:
        if c[dishes[x][0]] > 1:
            break
        x -= 1

    if x == -1:
        break


    a = a + d - dishes[x][1]
    c[t] += 1
    c[dishes[x][0]] -= 1
    del dishes[x]
    dishes.append((t, d))

    answer = max(answer, a + len(c) ** 2)

print(answer)

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

n, k = map(int, input().split())
sushies = []
for _ in range(n):
    t, d = map(int, input().split())
    sushies.append((t, d))

sushies.sort(key=operator.itemgetter(1), reverse=True)

dishes = sushies[:k]
c = collections.Counter(t for t, d in dishes)
a = sum(d for t, d in dishes)
answer = a + len(c) ** 2

for t, d in sushies[k:]:
    if t in c:
        continue

    x = -1
    for i in reversed(range(k)):
        if c[dishes[i][0]] > 1:
            x = i
            break

    if x == -1:
        break

    a = a + d - dishes[x][1]
    c[t] += 1
    c[dishes[x][0]] -= 1
    del dishes[x]
    dishes.append((t, d))

    answer = max(answer, a + len(c) ** 2)

print(answer)


Fixed submission:
import operator
import collections

n, k = map(int, input().split())
sushies = []
for _ in range(n):
    t, d = map(int, input().split())
    sushies.append((t, d))

sushies.sort(key=operator.itemgetter(1), reverse=True)

dishes = sushies[:k]
c = collections.Counter(t for t, d in dishes)
a = sum(d for t, d in dishes)
answer = a + len(c) ** 2
x = k - 1
for t, d in sushies[k:]:
    if t in c:
        continue

    while x >= 0:
        if c[dishes[x][0]] > 1:
            break
        x -= 1

    if x == -1:
        break


    a = a + d - dishes[x][1]
    c[t] += 1
    c[dishes[x][0]] -= 1
    del dishes[x]
    dishes.append((t, d))

    answer = max(answer, a + len(c) ** 2)

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

costs = [float('inf') for _ in range(n)]
costs[0] = 0

for x in range(n):
    for y in range(x + 1, min(x + k + 1, n)):
        costs[y] = min(costs[y], costs[x] + abs(h[x] - h[y]))

print(costs[n - 1])

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

costs = [float('inf') for _ in range(n)]
costs[0] = 0

for x in range(n):
    for y in range(x + 1, min(x + k + 1, n)):
        costs[y] = min(costs[y], costs[x] + abs(h[x] - h[y]))

print(costs[n - 1])
Buggy python submission (verdict: Runtime Error):
import collections, sys

n, m = map(int, input().split())
nxts = collections.defaultdict(list)
for line in sys.stdin:
    x, y = map(int, line.split())
    nxts[x].append(y)

memo = {}

def solve(x):
    if not x in memo:
        ans = 0
        for nxt in nxts[x]:
            ans = max(ans, solve(nxt) + 1)
        memo[x] = ans
    return memo[x]

print(max(solve(x) for x in range(1, n + 1)))

Fixed submission:
import collections, sys

n, m = map(int, input().split())
pres = collections.defaultdict(list)
nxts = collections.defaultdict(list)
for line in sys.stdin:
    x, y = map(int, line.split())
    pres[y].append(x)
    nxts[x].append(y)

stack, count, nodes = [], [0], []
for node in range(1, n + 1):
    count.append(len(pres[node]))
    if count[node] == 0:
        stack.append(node)

while stack:
    node = stack.pop()
    nodes.append(node)
    for nxt in nxts[node]:
        count[nxt] -= 1
        if count[nxt] == 0:
            stack.append(nxt)

dp = [0] * (n + 1)
for node in nodes:
    for pre in pres[node]:
        dp[node] = max(dp[node], dp[pre] + 1)

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(float, input().split()))

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

for i in range(n):
    for j in range(n):
        if j + 1 <= n:
            dp[i + 1][j + 1] += dp[i][j] * p[i]
        dp[i + 1][j] += dp[i][j] * (1 - p[i])

print(sum(dp[n][n//2+1:]))

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

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

for i in range(n):
    for j in range(n):
        if j + 1 <= n:
            dp[i + 1][j + 1] += dp[i][j] * p[i]
        dp[i + 1][j] += dp[i][j] * (1 - p[i])

print(sum(dp[n][n//2+1:]))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

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

matrix = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    matrix[l][r] += 1

totals = [[0] * (n + 1) for _ in range(n + 1)]
for i, j in itertools.product(range(1, n + 1), repeat=2):
    totals[i][j] += totals[i][j - 1] + matrix[i][j]

for _ in range(q):
    p, q = map(int, input().split())
    print(sum(totals[i][q] - totals[i][p - 1] for i in range(p, q + 1)))



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

matrix = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    matrix[l][r] += 1

totals = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        totals[i][j] += totals[i][j - 1] + matrix[i][j]

answers = []
for _ in range(q):
    p, q = map(int, input().split())
    answer = sum(totals[i][q] - totals[i][p - 1] for i in range(p, q + 1))
    answers.append(answer)

for answer in answers:
    print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == '__main__':
    n, m = map(int, input().split())
    sweets = list(map(int, input().split()))

    cnt = 0
    total = 0
    totals = [0]
    for i in range(n):
        total += sweets[i]
        for old in totals:
            if (total - old) % m == 0:
                cnt += 1
        totals.append(total)
    
    print(cnt)

Fixed submission:
import collections

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

b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]

d = collections.Counter(x % m for x in b)
ans = sum(v * (v - 1) // 2 for v in d.values())
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
MOD = 10 ** 9 + 7

dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i + 1][j] += dp[i][j] * 3
        else:
            dp[i + 1][j] += dp[i][j]
    
    if S[i] == 'A' or S[i] == '?': dp[i + 1][1] += dp[i][0]
    if S[i] == 'B' or S[i] == '?': dp[i + 1][2] += dp[i][1]
    if S[i] == 'C' or S[i] == '?': dp[i + 1][3] += dp[i][2]

print(dp[len(S)][3] % MOD)

Fixed submission:
S = input()
MOD = 10 ** 9 + 7

dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * 3) % MOD
        else:
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
    
    if S[i] == 'A' or S[i] == '?': dp[i + 1][1] = (dp[i + 1][1] + dp[i][0]) % MOD
    if S[i] == 'B' or S[i] == '?': dp[i + 1][2] = (dp[i + 1][2] + dp[i][1]) % MOD
    if S[i] == 'C' or S[i] == '?': dp[i + 1][3] = (dp[i + 1][3] + dp[i][2]) % MOD

print(dp[len(S)][3] % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

ans = float('inf')
for x, y, z in itertools.permutations(range(C), 3):
    point = 0
    for i, j in itertools.product(range(N), repeat=2):
        if (i + j) % 3 == 0: point += D[c[i][j] - 1][x]
        if (i + j) % 3 == 1: point += D[c[i][j] - 1][y]
        if (i + j) % 3 == 2: point += D[c[i][j] - 1][z]
    ans = min(ans, point)

print(ans)


Fixed submission:
import itertools

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [[int(s) - 1 for s in input().split()] for _ in range(N)]

m0 = [0] * C
m1 = [0] * C
m2 = [0] * C
for i, j in itertools.product(range(N), repeat=2):
    if (i + j) % 3 == 0: m0[c[i][j]] += 1
    if (i + j) % 3 == 1: m1[c[i][j]] += 1
    if (i + j) % 3 == 2: m2[c[i][j]] += 1

ans = float('inf')
for x, y, z in itertools.permutations(range(C), 3):
    point = 0
    for i in range(C): point += D[i][x] * m0[i]
    for i in range(C): point += D[i][y] * m1[i]
    for i in range(C): point += D[i][z] * m2[i]
    ans = min(ans, point)

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [0, *map(int, input().split()), 0]

total = sum(abs(a[i] - a[i + 1]) for i in range(0, n + 1))
for i in range(1, n + 1):
    print(total - abs(a[i - 1] - a[i]) - abs(a[i] - a[i + 1]) + abs(a[i - 1] - a[i + 1]))


Fixed submission:
n = int(input())
a = [0] + list(map(int, input().split())) + [0]

total = sum(abs(a[i] - a[i + 1]) for i in range(0, n + 1))
for i in range(1, n + 1):
    print(total - abs(a[i - 1] - a[i]) - abs(a[i] - a[i + 1]) + abs(a[i - 1] - a[i + 1]))

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

def f(i1, i2, c):
    return itertools.islice(((x, y) for x, y in itertools.product(i1, i2) if x % 2 == y % 2), c)

a, b = map(int, input().split())
k = 100
grid = [['#' if x < k else '.' for _ in range(k * 2)] for x in range(k * 2)]

for x, y in f(range(0, k - 1), range(k * 2), a - 1):
    grid[x][y] = '.'

for x, y in f(range(k + 1, k * 2), range(k * 2), b - 1):
    grid[x][y] = '#'

for row in grid:
    print(''.join(row))

Fixed submission:
n = int(input())
a = [0] + list(map(int, input().split())) + [0]

total = sum(abs(a[i] - a[i + 1]) for i in range(0, n + 1))
for i in range(1, n + 1):
    print(total - abs(a[i - 1] - a[i]) - abs(a[i] - a[i + 1]) + abs(a[i - 1] - a[i + 1]))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import sys

sys.setrecursionlimit(10 ** 7)

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
l, r = [], []
for _ in range(q):
    x, y = map(int, input().split())
    l.append(x)
    r.append(y)


coordinates = {a[x][y] : (x, y) for x, y in itertools.product(range(h), range(w))}
cache = {}
def f(x, y):
    if x == y:
        return 0

    key = (x, y)
    if not key in cache:
        i1, j1 = coordinates[x]
        i2, j2 = coordinates[x + d]
        cache[key] = abs(i1 - i2) + abs(j1 - j2) + f(x + d, y)

    return cache[key]


for i in range(q):
    print(f(l[i], r[i]))

Fixed submission:
h, w, d = map(int, input().split())

coordinates = {}
for i in range(h):
    row = list(map(int, input().split()))
    for j in range(w):
        coordinates[row[j]] = (i, j)

costs = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    x1, y1 = coordinates[i]
    x2, y2 = coordinates[i - d]
    costs[i] = abs(x1 - x2) + abs(y1 - y2) + costs[i - d]

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(costs[r] - costs[l])

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
l, r = [], []
for _ in range(q):
    x, y = map(int, input().split())
    l.append(x)
    r.append(y)

coordinates = {a[x][y] : (x, y) for x, y in itertools.product(range(h), range(w))}
for i in range(q):
    score = 0
    while l[i] != r[i]:
        x1, y1 = coordinates[l[i]]
        x2, y2 = coordinates[l[i] + d]
        score += abs(x1 - x2) + abs(y1 - y2)
        l[i] = l[i] + d
    print(score)


Fixed submission:
h, w, d = map(int, input().split())

coordinates = {}
for i in range(h):
    row = list(map(int, input().split()))
    for j in range(w):
        coordinates[row[j]] = (i, j)

costs = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    x1, y1 = coordinates[i]
    x2, y2 = coordinates[i - d]
    costs[i] = abs(x1 - x2) + abs(y1 - y2) + costs[i - d]

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(costs[r] - costs[l])
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N, M, R = map(int, input().split())
r = [int(s) - 1 for s in input().split()]
a, b, c = [0] * M, [0] * M, [0] * M
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

wf = [[float('inf')] * N for _ in range(N)]
for i in range(M):
    wf[a[i]][b[i]] = c[i]
    wf[b[i]][a[i]] = c[i]

for k, i, j in itertools.product(range(N), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

x = float('inf')
for route in itertools.permutations(r):
    y = sum(wf[route[i]][route[i + 1]] for i in range(R - 1))
    x = min(x, y)

print(x)

Fixed submission:
import itertools

N, M, R = map(int, input().split())
r = [int(s) - 1 for s in input().split()]
a, b, c = [0] * M, [0] * M, [0] * M
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

wf = [[float('inf')] * N for _ in range(N)]
for i in range(M):
    wf[a[i]][b[i]] = c[i]
    wf[b[i]][a[i]] = c[i]

for k, i, j in itertools.product(range(N), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

x = float('inf')
for route in itertools.permutations(r):
    y = sum(wf[route[i]][route[i + 1]] for i in range(R - 1))
    x = min(x, y)

print(x)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

n = int(input())
distance = [[float('inf')] * n for _ in range(n)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    distance[a - 1][b - 1] = c
    distance[b - 1][a - 1] = c
q, k = map(int, input().split())
k -= 1
queries = []
for _ in range(q):
    x, y = map(int, input().split())
    queries.append((x - 1, y - 1))

d = [float('inf')] * (n + 1)
d[k] = 0
queue = [(0, k)]
while queue:
    cost, current = heapq.heappop(queue)
    for nxt in range(n):
        if cost + distance[current][nxt] < d[nxt]:
            d[nxt] = cost + distance[current][nxt]
            heapq.heappush(queue, (d[nxt], nxt))

for x, y in queries:
    print(d[x] + d[y])

Fixed submission:
import heapq, collections

n = int(input())
distance = collections.defaultdict(dict)
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    distance[a - 1][b - 1] = c
    distance[b - 1][a - 1] = c
q, k = map(int, input().split())
k -= 1
queries = []
for _ in range(q):
    x, y = map(int, input().split())
    queries.append((x - 1, y - 1))

d = [float('inf')] * (n + 1)
d[k] = 0
queue = [(0, k)]
while queue:
    cost, current = heapq.heappop(queue)
    for nxt in distance[current]:
        if cost + distance[current][nxt] < d[nxt]:
            d[nxt] = cost + distance[current][nxt]
            heapq.heappush(queue, (d[nxt], nxt))

for x, y in queries:
    print(d[x] + d[y])
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

def find(table, x):
    while table[x] != x:
        x = table[x]
    return x

def union(table, x1, x2):
    p1 = find(table, x1)
    p2 = find(table, x2)
    table[p2] = p1

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

edges = []
for j in (0, 1):
    cities1, cities2 = itertools.tee(sorted(range(n), key=lambda city: points[city][j]), 2)
    for city1, city2 in zip(cities1, itertools.islice(cities2, 1, None)):
        (x1, y1), (x2, y2) = points[city1], points[city2]
        cost = min(abs(x1 - x2), abs(y1 - y2))
        edges.append((cost, city1, city2))
edges.sort() # key=lambda cost, city1, city2: cost

table = list(range(n))
answer = 0
for cost, city1, city2 in edges:
    parent1, parent2 = find(table, city1), find(table, city2)
    if parent1 != parent2:
        answer += cost
        union(table, city1, city2)

print(answer)

Fixed submission:
import itertools

def find(table, x):
    stack = [x]
    while table[stack[-1]] != stack[-1]:
        stack.append(table[stack[-1]])
    
    for i in stack:
        table[i] = stack[-1]
    return table[x]


def union(table, x1, x2):
    p1 = find(table, x1)
    p2 = find(table, x2)
    table[p2] = p1

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

edges = []
cities = list(range(n))
for j in (0, 1):
    cities.sort(key=lambda city: points[city][j])
    for i in range(n - 1):
        city1, city2 = cities[i], cities[i + 1]
        (x1, y1), (x2, y2) = points[city1], points[city2]
        cost = min(abs(x1 - x2), abs(y1 - y2))
        edges.append((cost, city1, city2))
edges.sort() # key=lambda cost, city1, city2: cost

table = list(range(n))
answer = 0
for cost, city1, city2 in edges:
    parent1, parent2 = find(table, city1), find(table, city2)
    if parent1 != parent2:
        answer += cost
        union(table, city1, city2)

print(answer)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = [int(input()) for _ in range(n)]

dp = [set() for _ in range(n + 1)]
for i in range(n):
    dp[i + 1].update(dp[i])
    for x in dp[i]:
        dp[i + 1].add(x + s[i])
    dp[i + 1].add(s[i])


ans = max((x for x in dp[i + 1] if x % 10 != 0), default=0)
print(ans)


Fixed submission:
def find(scores):
    for score in scores:
        if score % 10 != 0: return score
    return -1

def solve(scores):
    x = find(scores)
    if x == -1: return 0

    total = sum(scores)
    return total if total % 10 != 0 else total - x

if __name__ == '__main__':
    n = int(input())
    scores = list(sorted(int(input()) for _ in range(n)))
    print(solve(scores))
Buggy python submission (verdict: Time Limit Exceeded):
import copy
import math
n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]

def is_ok(x):
    t = copy.deepcopy(h)
    y = x
    for i in range(n):
        t[i] -= b * x
        if t[i] > 0:
            y -= math.ceil(t[i] / (a - b))
    return y >= 0

ng = 0
ok = 10 ** 9
while abs(ok - ng) > 1:
    mi = (ok + ng) // 2
    if is_ok(mi):
        ok = mi
    else:
        ng = mi

print(ok)


Fixed submission:
import math

n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]

def is_ok(x):
    c = 0
    for i in range(n):
        t = h[i] - b * x
        if t <= 0:
            continue
        c += math.ceil(t / (a - b))
    return c <= x

ng = 0
ok = 10 ** 9
while abs(ok - ng) > 1:
    mi = (ok + ng) // 2
    if is_ok(mi):
        ok = mi
    else:
        ng = mi

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
import copy
import math
n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]

def is_ok(x):
    t = copy.deepcopy(h)
    y = x
    for i in range(n):
        t[i] -= b * x
        if t[i] > 0:
            y -= math.ceil(t[i] / (a - b))
    return y >= 0

ng = 0
ok = 10 ** 32
while abs(ok - ng) > 1:
    mi = (ok + ng) // 2
    if is_ok(mi):
        ok = mi
    else:
        ng = mi

print(ok)


Fixed submission:
import math

n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]

def is_ok(x):
    c = 0
    for i in range(n):
        t = h[i] - b * x
        if t <= 0:
            continue
        c += math.ceil(t / (a - b))
    return c <= x

ng = 0
ok = 10 ** 9
while abs(ok - ng) > 1:
    mi = (ok + ng) // 2
    if is_ok(mi):
        ok = mi
    else:
        ng = mi

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

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

sum1 = 0
sum2 = 0
left = []
used = set()
unused = []

for i in range(n):
    sum1 += a[i]
    heapq.heappush(left, (a[i], i))


for v, i in sorted((a[i], i) for i in range(n, n * 3)):
    if len(used) < n:
        sum2 += v
        used.add((v, i))
    else:
        heapq.heappush(unused, (v, i))

print(sum1, sum2)
ans = sum1 - sum2
for i in range(n, 2 * n):
    # v1: これから挿入しようとしている値
    # v2: 現状の最小値
    v1 = a[i]
    v2, j = left[0]
    if v2 < v1:
        sum1 = sum1 + v1 - v2
        heapq.heappop(left)
        heapq.heappush(left, (v1, i))

    # v1: これから削除する可能性がある値
    # v2: 候補のうちで最小の値
    while True:
        v2, j = unused[0]
        if i < j:
            break
        heapq.heappop(unused)
        
    if (v1, i) in used:
        sum2 = sum2 - v1 + v2
        used.remove((v1, i))
        used.add((v2, j))
        heapq.heappop(unused)

    ans = max(ans, sum1 - sum2)

print(ans)
    
    

Fixed submission:
import heapq

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

sum1 = 0
sum2 = 0
left = []
used = set()
unused = []

for i in range(n):
    sum1 += a[i]
    heapq.heappush(left, (a[i], i))


for v, i in sorted((a[i], i) for i in range(n, n * 3)):
    if len(used) < n:
        sum2 += v
        used.add((v, i))
    else:
        heapq.heappush(unused, (v, i))

ans = sum1 - sum2
for i in range(n, 2 * n):
    # v1: これから挿入しようとしている値
    # v2: 現状の最小値
    v1 = a[i]
    v2, j = left[0]
    if v2 < v1:
        sum1 = sum1 + v1 - v2
        heapq.heappop(left)
        heapq.heappush(left, (v1, i))

    # v1: これから削除する可能性がある値
    # v2: 候補のうちで最小の値
    while True:
        v2, j = unused[0]
        if i <= j:
            break
        heapq.heappop(unused)
        
    if (v1, i) in used:
        sum2 = sum2 - v1 + v2
        used.remove((v1, i))
        used.add((v2, j))
        heapq.heappop(unused)

    ans = max(ans, sum1 - sum2)

print(ans)