Problem:


Score : 500 points

Problem Statement

Let N be a positive integer.

There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}).
Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements.
Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').

Find the maximum possible score of a'.

Constraints

1 ≤ N ≤ 10^5

a_i is an integer.

1 ≤ a_i ≤ 10^9

Partial Score

In the test set worth 300 points, N ≤ 1000.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{3N}

Output

Print the maximum possible score of a'.

Sample Input 1

2
3 1 4 1 5 9

Sample Output 1

1

When a_2 and a_6 are removed, a' will be (3, 4, 1, 5), which has a score of (3 + 4) - (1 + 5) = 1.

Sample Input 2

1
1 2 3

Sample Output 2

-1

For example, when a_1 are removed, a' will be (2, 3), which has a score of 2 - 3 = -1.

Sample Input 3

3
8 2 2 7 4 6 5 3 8

Sample Output 3

5

For example, when a_2, a_3 and a_9 are removed, a' will be (8, 7, 4, 6, 5, 3), which has a score of (8 + 7 + 4) - (6 + 5 + 3) = 5.



Sample input:
2
3 1 4 1 5 9


Sample output:
1

Submission status: Accepted

Solution code:
from heapq import *

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

sumS1 = [0 for i in range(N + 1)]
S1 = a[0:N]
heapify(S1)
sumS1[0] = sum(S1)

for k in range(1, N + 1):
    if S1[0] < a[N + k - 1]:
        sumS1[k] = sumS1[k - 1] +a[N + k - 1] - S1[0]
        heapreplace(S1, a[N + k - 1])
    else:
        sumS1[k] = sumS1[k - 1]

sumS2 = [0 for i in range(N + 1)]
S2 =  [-1 * i for i in a[2 * N:3 * N]]
heapify(S2)
sumS2[N] = sum(S2)

for k in range(1, N + 1):
    if S2[0] < -1 * a[2 * N - k]:
        sumS2[N - k] = sumS2[N - k + 1] - a[2 * N - k] - S2[0]
        heapreplace(S2, -1 * a[2 * N - k])
    else:
        sumS2[N - k] = sumS2[N - k + 1]


res = [float("-inf")] * (N + 1)
for i in range(N + 1):
    res[i] = sumS1[i] + sumS2[i]

res.sort()
print(res[N])

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop

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

former = aa[:n]
latter = [-a for a in aa[2 * n:]]
fs = sum(former)
ls = sum(latter)
heapify(former)
heapify(latter)

results = [0] * (n + 1)
results[0] = fs
results[-1] = ls

for i in range(n, 2 * n):
    a = aa[i]
    k = heappushpop(former, a)
    fs += a - k
    results[i - n + 1] += fs

for i in range(2 * n - 1, n - 1, -1):
    a = -aa[i]
    k = heappushpop(latter, a)
    ls += a - k
    results[i - n] += ls

print(max(results))

Submission status: Accepted

Solution code:
import heapq

def solve():
  n = int(raw_input())
  ar = raw_input().split(' ')
  iar = [int(s) for s in ar]
  
  early = iar[:n]
  mid = iar[n:-n]
  late = iar[-n:]

  heapq.heapify(early)
  tmpsum = sum(early)
  esums = [tmpsum]
  for i in range(n):
    heapq.heappush(early, mid[i])
    emin = heapq.heappop(early)
    tmpsum += (mid[i] - emin)
    esums.append(tmpsum)
  #print esums
 
  lateinv = [-x for x in late]
  heapq.heapify(lateinv)
  tmpsum = sum(lateinv)
  lsums = [tmpsum]
  for i in range(1,n+1):
    heapq.heappush(lateinv, -mid[-i])
    lmax = heapq.heappop(lateinv)
    tmpsum += (-mid[-i] - lmax)
    lsums.append(tmpsum)
  #print lsums
  
  best = float("-inf")
  for i in range(n+1):
    score = esums[i] + lsums[n-i]
    #print 'i=',i,',n-i=',n-i,',esums[i]=',esums[i],',lsums[n-i]=',lsums[n-i],'score=',score
    if(best < score) : best = score
  return best

if __name__ == '__main__' :
  print solve()

Submission status: Accepted

Solution code:
n=int(input())
import heapq
a=list(map(int,input().split()))
q=a[:n]
heapq.heapify(q)
x=[sum(q)]
for k in range(n,2*n):
    v=heapq.heappushpop(q,a[k])
    x.append(x[-1]+a[k]-v)
a=a[::-1]
q=[-v for v in a[:n]]
heapq.heapify(q)
y=[-sum(q)]
for k in range(n,2*n):
    v=-heapq.heappushpop(q,-a[k])
    y.append(y[-1]+a[k]-v)
print(max(v-w for v,w in zip(x,y[::-1])))

Submission status: Accepted

Solution code:
def f(a):
	q=a[:n];s=sum(q);heapify(q);yield s
	for e in a[n:2*n]:s+=e-heappushpop(q,e);yield s
from heapq import*;r=reversed;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),r(list(f([-e for e in r(a)])))))))

Submission status: Accepted

Solution code:
def f(a):
	s=0;q=a[:n];s=sum(q);heapify(q);yield s
	for e in a[n:2*n]:s+=e-heappushpop(q,e);yield s
from heapq import*;r=reversed;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),r(list(f([-e for e in r(a)])))))))

Submission status: Accepted

Solution code:
def f(a):
	s=0;q=a[:n];s=sum(q);heapify(q);r=[s]
	for e in a[n:2*n]:s+=e-heappushpop(q,e);r+=[s]
	return r
from heapq import*;r=reversed;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),r(f([-e for e in r(a)]))))))

Submission status: Accepted

Solution code:
def f(a):
	s=0;q=a[:n];s=sum(q);heapify(q);r=[s]
	for e in a[n:2*n]:s+=e-heappushpop(q,e);r+=[s]
	return r
import sys;from heapq import*;r=reversed;n,*a=map(int,sys.stdin.read().split());print(max(map(sum,zip(f(a),r(f([-e for e in r(a)]))))))

Submission status: Accepted

Solution code:
def f(a):
	s=0;q=a[:n];s=sum(q);heapify(q);r=[s]
	for e in a[n:2*n]:s+=e-heappushpop(q,e);r+=[s]
	return r
import sys;from heapq import*;n,*a=map(int,sys.stdin.read().split());print(max(map(sum,zip(f(a),reversed(f([-e for e in reversed(a)]))))))

Submission status: Accepted

Solution code:
def f(a):
	s=0;q=a[:n];s=sum(q);heapify(q);r=[s]
	for e in a[n:2*n]:s+=e-heappushpop(q,e);r+=[s]
	return r
import sys;from heapq import*;n,*a=list(map(int,sys.stdin.read().split()));print(max(map(sum,zip(f(a),reversed(f([-e for e in reversed(a)]))))))

Submission status: Accepted

Solution code:
def f(a):
	s=0;q=a[:n];s=sum(q);heapify(q);r=[s]
	for i in range(n,2*n):s=s+a[i]-heappushpop(q,a[i]);r+=[s]
	return r
import sys;from heapq import*;n,*a=list(map(int,sys.stdin.read().split()));print(max(map(sum,zip(f(a),list(reversed(f(list(reversed([-e for e in a])))))))))

Submission status: Accepted

Solution code:
def f(a):
	s=0;q=[]
	for i in range(n):s+=a[i];heappush(q,a[i])
	r=[s]
	for i in range(n,2*n):s+=a[i];s-=heappushpop(q,a[i]);r+=[s]
	return r
import sys;from heapq import*;n,*a=list(map(int,sys.stdin.read().split()));print(max(map(sum,zip(f(a),list(reversed(f(list(reversed([-e for e in a])))))))))

Submission status: Accepted

Solution code:
import heapq
N = int(input())

a = list(map(int, input().split()))
left = []
for i in a[:N]:
    heapq.heappush(left, i)
right = []
for i in a[(2 * N):(3 * N)]:
    heapq.heappush(right, -i)

left_sum = [sum(left)]
right_sum = [-sum(right)]
for k in range(N, 2 * N):

    heapq.heappush(left, a[k])
    v = heapq.heappop(left)
    left_sum.append(left_sum[-1] + a[k] - v)

for k in range(2 * N - 1, N - 1, -1):
    heapq.heappush(right, -a[k])
    v = heapq.heappop(right)
    right_sum.append(right_sum[-1] + a[k] + v)

print(max([a - b for (a, b) in zip(left_sum, right_sum[::-1])]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import heapq

N = int(input())

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

B = A[:N]
B_sum = sum(B)
heapq.heapify(B)
dict_b = {}

for i in range(N, 2 * N):
    a = A[i]
    min_val = heapq.heappop(B)
    greater = max(a, min_val)
    heapq.heappush(B, greater)

    if greater != min_val:
        B_sum += (a - min_val)
    dict_b[i] = B_sum


C = A[-N:]
C = [-c for c in C]
C_sum = -1 * sum(C)
heapq.heapify(C)
dict_c = {}

for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    max_val = -1 * heapq.heappop(C)
    fewer = min(a, max_val)
    heapq.heappush(C, -fewer)

    if fewer != max_val:
        C_sum -= (max_val - a)
    dict_c[i] = C_sum

max_score = max(sum(A[:N]) - dict_c[N], dict_b[2*N-1] - sum(A[-N:]))
for i in range(N, 2 * N - 1):
    score = dict_b[i] - dict_c[i+1]
    if score > max_score:
        max_score = score

print(max_score)

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop

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

a_list_1 = []
a_list_2 = []
for i in a[0:N]:
    heappush(a_list_1, i)
for i in list(reversed(a))[0:N]:
    heappush(a_list_2, -i)

sum_1 = sum(a_list_1)
sum_2 = sum(a_list_2)
sum_arr_1 = [0] * (N + 1)
sum_arr_1[0] = sum_1
sum_arr_2 = [0] * (N + 1)
sum_arr_2[-1] = sum_2
for k in range(N, 2 * N):
    l = heappushpop(a_list_1, a[k])
    sum_1 += a[k] - l
    sum_arr_1[k - N + 1] = sum_1

for k in reversed(range(N, 2 * N)):
    l = heappushpop(a_list_2, -a[k])
    sum_2 += -a[k] - l
    sum_arr_2[k - N] = sum_2

max_score = float('-inf')
for s1, s2 in zip(sum_arr_1, sum_arr_2):
    score = s1 + s2
    if score > max_score:
        max_score = score

print(max_score)

Submission status: Accepted

Solution code:
def f(l,m,n,d):
	s=0;q=[]
	for i in range(l,m,d):s+=a[i];heappush(q,a[i]*d)
	r=[s]
	for i in range(m,n,d):s+=a[i];heappush(q,a[i]*d);s-=heappop(q)*d;r+=[s]
	return r
import sys;from heapq import*;n,*a=list(map(int,sys.stdin.read().split()));print(max(x-y for x,y in zip(f(0,n,2*n,1),reversed(f(3*n-1,2*n-1,n-1,-1)))))

Submission status: Accepted

Solution code:
import sys,heapq
n,*a=list(map(int,sys.stdin.read().split()))
def f(l,m,n,d):
	s=0
	q=[]
	for i in range(l,m,d):
		s+=a[i]
		heapq.heappush(q,a[i]*d)
	r=[s]
	for i in range(m,n,d):
		s+=a[i]
		heapq.heappush(q,a[i]*d)
		s-=heapq.heappop(q)*d
		r.append(s)
	return r
ra=f(0,n,2*n,1)
rb=reversed(f(3*n-1,2*n-1,n-1,-1))
print(max(x-y for x,y in zip(ra,rb)))

Submission status: Accepted

Solution code:
import sys,heapq
n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
sa=sb=0
la=[]
lb=[]
for i in range(n):
	sa+=a[i]
	heapq.heappush(la,a[i])
ra=[sa]
for i in range(n,2*n):
	sa+=a[i]
	heapq.heappush(la,a[i])
	sa-=heapq.heappop(la)
	ra.append(sa)
for i in range(3*n-1,2*n-1,-1):
	sb+=a[i]
	heapq.heappush(lb,-a[i])
rb=[sb]
for i in range(2*n-1,n-1,-1):
	sb+=a[i]
	heapq.heappush(lb,-a[i])
	sb+=heapq.heappop(lb)
	rb.append(sb)
print(max(x-y for x,y in zip(ra,reversed(rb))))

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
A_rev = [-x for x in A[::-1]] #逆順にして各要素を-1倍する
left, right = A[:N], A_rev[:N]
sum_left_list, sum_right_list = [0]*(N+1), [0]*(N+1)
sum_left, sum_right = sum(left), sum(right)
sum_left_list[0], sum_right_list[0]=sum_left, sum_right

#left: k=N, N+1,..., 2N-1まで動かして大きい方からN個の和を求める
for k in range(N, 2*N):
	val=A[k]
	heapq.heappush(left, val)
	min_val = heapq.heappop(left)
	sum_left += val
	sum_left -= min_val
	sum_left_list[k-N+1] = sum_left

#right: k=N, N+1,..., 2N-1まで動かして大きい方からN個の和を求める
for k in range(N, 2*N):
	val = A_rev[k]
	heapq.heappush(right, val)
	min_val = heapq.heappop(right)
	sum_right += val
	sum_right -= min_val
	sum_right_list[k-N+1] = sum_right
sum_right_list[::-1]

ans=-float("inf")
for i in range(N+1):
	ans=max(ans, sum_left_list[i]+sum_right_list[i])
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
tmp = list(map(int, input().split(' ')))
former_A = deque(tmp)
latter_A = deque(tmp.copy())
former_heap = list()
latter_heap = list()
for _ in range(N):
    former_heap.append(former_A.popleft())
    latter_heap.append(- latter_A.pop())
heapify(former_heap)
heapify(latter_heap)

former_sum = sum(former_heap)
former_sum_list = [former_sum]
for k in range(N):
    new_a = former_A.popleft()
    heappush(former_heap, new_a)
    min_a = heappop(former_heap)
    former_sum += new_a - min_a
    former_sum_list.append(former_sum)

latter_sum = sum(latter_heap)
latter_sum_list = [latter_sum]
for k in range(N):
    new_a = - latter_A.pop()
    heappush(latter_heap, new_a)
    min_a = heappop(latter_heap)
    latter_sum += new_a - min_a
    latter_sum_list.append(latter_sum)
latter_sum_list.reverse()

answer = max([former + latter for former, latter in zip(former_sum_list, latter_sum_list)])
print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque
from heapq import heapify, heappop, heappush
N = int(input())
A = deque(map(int, input().split(' ')))
former_heap = list()
latter_heap = list()
for _ in range(N):
    former_heap.append(A.popleft())
    latter_heap.append(- A.pop())
heapify(former_heap)
heapify(latter_heap)

former_sum = sum(former_heap)
former_sum_list = [former_sum]
former_A = A.copy()
for k in range(N):
    new_a = former_A.popleft()
    heappush(former_heap, new_a)
    min_a = heappop(former_heap)
    former_sum += new_a - min_a
    former_sum_list.append(former_sum)

latter_sum = sum(latter_heap)
latter_sum_list = [latter_sum]
latter_A = A.copy()
for k in range(N):
    new_a = - latter_A.pop()
    heappush(latter_heap, new_a)
    min_a = heappop(latter_heap)
    latter_sum += new_a - min_a
    latter_sum_list.append(latter_sum)
latter_sum_list.reverse()

answer = max([former + latter for former, latter in zip(former_sum_list, latter_sum_list)])
print(answer)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int, input().split()))

pre = [0]*(n+1)
pre_list = [e for e in A[:n]]
heapq.heapify(pre_list)
pre_sum = sum(pre_list)
pre[0] = pre_sum
for i in range(n, 2*n):
    small = heapq.heappushpop(pre_list, A[i])
    pre_sum += A[i] - small
    pre[i-n+1] = pre_sum

suf = [0]*(n+1)
suf_list = [-e for e in A[2*n:]]
heapq.heapify(suf_list)
suf_sum = -sum(suf_list)
suf[-1] = suf_sum
for i in range(2*n-1, n-1, -1):
    large = -heapq.heappushpop(suf_list, A[i])
    suf_sum += A[i] - large
    suf[i-n] = suf_sum

# print(pre)
# print(suf)

print(max([pre[i] - suf[i] for i in range(n+1)]))

Submission status: Runtime Error

Solution code:
import heapq
n=int(input())
l=list(map(int,input().split()))
q=[]
for i in range(n):
    heapq.heappush(q,l[i])
a1=[0]*(n+1)
a1[0]=sum(l[:n])
for i in range(n):
    p=heapq.heappop(q)
    a1[i+1]=a1[i]-p+max(p,l[i+n])
    heapq.heappush(q,max(p,l[i+n]))
q=[]
l.reverse()
for i in range(n):
    heapq.heappush(q,-l[i])
a1.reverse()
a1[0]-=sum(l[:n])
z=sum(l[:n])
for i in range(n):
    p=heapq.heappop(q)
    z=z-min(-p,l[i+n])
    a1[i+1]-=z
    heapq.heappush(q,max(p,-l[i+n])
print(max(a1))

Submission status: Runtime Error

Solution code:
from random import choice
N=int(input())
lista=[]
total=0
for criando in range (0,3*N):
    a = int(input())
    lista.append(a)
for loop in range (0,N):
    escolhido=choice(lista)
    if escolhido in lista:
        lista.remove(escolhido)
for conta in range (0,len(lista)):
    if conta<(len(lista))/2:
        total+=lista[conta]
    else:
        total-=lista[conta]
print (total)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0


ans = -inf
n = int(input())
A = list(map(int, input().split()))
AL, AR = A[:n], A[2*n:]
al,ar=AL.copy(),AR.copy()
AN = A[n:2*n]
LS, RS = sum(AL), sum(AR)
AR = list(map(lambda ddd: -ddd, AR))
heapq.heapify(AL)
heapq.heapify(AR)
tmp=LS
ANSR=[0]*n
ANSL=[0]*n

for i in range(n):
    if AN[i]-AL[0] >0:
        LS = LS-heapq.heappop(AL)+AN[i]
        heapq.heappush(AL,AN[i])
    ANSL[i] = LS

LS=tmp
for j in range(n-1,-1,-1):
    if 0 < -AR[0]-AN[j]:
        RS = RS+heapq.heappop(AR)+AN[j]
        heapq.heappush(AR,-AN[j])
    ANSR[j] = RS
ANSR=ANSR+[sum(ar)]
ANSL=[sum(al)]+ANSL
for i in range(n+1):
    ans=max(ans,ANSL[i]-ANSR[i])
print(ans)
# print(ANSL,ANSR)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readlin

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

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N = ii()
As = list(mi())
minusAs = [-a for a in As]
print(As, minusAs)

#下準備。左側0～N-1, 右側2N～3N-1のN要素のheapqを作っておく
#leftQは大きいのを残したい（最小値を取り除く）、rightQは小さいのを残したい（最大値を取り除く）ので、leftQはそのままの配列、rightQは符号反転したminusAsを使用する
leftQ = As[:N]
rightQ = minusAs[-N:]
heapq.heapify(leftQ)
heapq.heapify(rightQ)

#この配列のidxは、右端（左端）から何番目(0スタート)の区切りを採用するかを表す。あとで突き合わせる時に添字でバグらせないよう注意
leftsum = [0]*(N+1)
rightsum = [0]*(N+1) #どうせ最後に引くんだから、マイナスのまま入れちゃう
#つまり、最後に最小値を求める時は、逆に「最も大きい＝マイナス幅が小さいsum」を求めることになるので注意

#初期値はもう入れておく
leftsum[0] = sum(leftQ)
rightsum[0] = sum(rightQ)

for i in range(N, 2*N+1): #左端（右端）から最低N個～最大2N個
  #iがNのとき、左側は[:N], 右側は[-N:]
  #iが2Nのとき、左側は[0:2N], 右側は[-2N:]
  if leftQ[0] < As[i]: #大きいのを残したいので、最小値のが小さければ入れ替える
    #入れ替える
    leftsum[i-N+1] - heapq.heappop(leftQ)
    leftsum[i-N+1] = leftsum[i-N] + As[i]
    heapq.heappush(leftQ,As[i])
  else: leftsum[i-N+1] = leftsum[i-N] #そうでなければ入れ替えない
  if rightQ[0] < minusAs[-1-i]: #小さいのを残したいので、マイナス幅が大きければ入れ替える
    rightsum[i-N+1] - heapq.heappop(rightQ)
    rightsum[i-N+1] += rightsum[i-N] + minusAs[-1-i]
    heapq.heappush(rightQ,minusAs[-1-i])
  else: rightsum[i-N+1] = rightsum[i-N] #そうでなければ入れ替えない

ans = -100000000
for lsum, rsum in zip(leftsum, rightsum[::-1]):
  print(ans, lsum, rsum)
  ans = max(ans, lsum+rsum)

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
*A, = map(int,input().split())
q = []
for a in A[:N]:
    heapq.heappush(q,a)
S1 = [sum(q)]
for a in A[N:N*2]:
    if a>q[0]:
        S1.append(S1[-1] + a - q[0])
        heapq.heapreplace(q,a)
    else:
        S1.append(S1[-1])
q = []
for a in A[2*N:]:
    heapq.heappush(q,-a)
S2 = [sum(q)]
for a in A[N:N*2][::-1]:
    if a<-q[0]:
        S2.append(S2[-1] - a - q[0])
        heapq.heapreplace(q,-a)
    else:
        S2.append(S2[-1])
S2 = S2[::-1]
print(max(map(sum,zip(S1,S2))))

Submission status: Runtime Error

Solution code:
def d_3n_numbers(N, A):
    import heapq
    left = A[:N]
    heapq.heapify(left)
    # heappopはキューの最小値を取り出すが、rightからは最大値を取り出したいので-1を掛ける
    # 後にマイナスが付いているところは、それの帳尻を合わせている
    right = [-i for i in A[2 * N:]]
    heapq.heapify(right)

    # 最初、leftには数列の先頭N個が、rightには末尾N個が格納されている
    # 数列のN番目から2N番目まで順に、leftに格納して最小値を捨てることを繰り返す
    # 数列の2N番目からN番目まで順に、rightに格納して最大値を捨てることを繰り返す
    left_sum = [sum(left)]
    right_sum = [-sum(right)]
    for k in range(N, 2 * N):
        heapq.heappush(left, A[k])
        v = heapq.heappop(left)
        left_sum.append(left_sum[-1] + A[k] - v)
    for k in range(2 * N - 1, N - 1, -1):
        heapq.heappush(right, -A[k])
        v = heapq.heappop(right)
        right_sum.append(right_sum[-1] + A[k] - (-v))

    score = [a - b for a, b in zip(left_sum, right_sum[::-1])]
    return max(score)

N = int(input())
A = [int(i) for i in input().split()]
print(d_3N_Numbers(N, A))

Submission status: Runtime Error

Solution code:
ef d_3n_numbers(N, A):
    import heapq
 
    def _heappush_max(heap, item):
        heap.append(item)
        heapq._siftdown_max(heap, 0, len(heap) - 1)
    def _heappop_max(heap):
    """Maxheap version of a heappop."""
    　　lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    　　if heap:
        　　returnitem = heap[0]
        　　heap[0] = lastelt
        　　heapq._siftup_max(heap, 0)
        　　return returnitem
    　　return lastelt
    setattr(heapq, '_heappush_max', _heappush_max)
 
    left = A[:N]
    heapq.heapify(left)
    right = A[2 * N:]
    heapq._heapify_max(right)
    left_sum, right_sum = [sum(left)], [sum(right)]
 
    # 同じ要素をleftとrightで取り合っても、相殺されるので問題ない
    for k in range(N, 2 * N):
        heapq.heappush(left, A[k])
        v = heapq.heappop(left)
        left_sum.append(left_sum[-1] + A[k] - v)
    for k in range(2 * N - 1, N - 1, -1):
        heapq._heappush_max(right, A[k])
        v = heapq._heappop_max(right)
        right_sum.append(right_sum[-1] + A[k] - v)
    right_sum = right_sum[::-1]
 
    ans_candidate = [a - b for a, b in zip(left_sum, right_sum)]
    return max(ans_candidate)
 
N = int(input())
A = [int(i) for i in input().split()]
print(d_3n_numbers(N, A))

Submission status: Runtime Error

Solution code:
def d_3n_numbers(N, A):
    import heapq

    def _heappush_max(heap, item):
        heap.append(item)
        heapq._siftdown_max(heap, 0, len(heap) - 1)
    setattr(heapq, '_heappush_max', _heappush_max)

    left = A[:N]
    heapq.heapify(left)
    right = A[2 * N:]
    heapq._heapify_max(right)
    left_sum, right_sum = [sum(left)], [sum(right)]

    # 同じ要素をleftとrightで取り合っても、相殺されるので問題ない
    for k in range(N, 2 * N):
        heapq.heappush(left, A[k])
        v = heapq.heappop(left)
        left_sum.append(left_sum[-1] + A[k] - v)
    for k in range(2 * N - 1, N - 1, -1):
        heapq._heappush_max(right, A[k])
        v = heapq._heappop_max(right)
        right_sum.append(right_sum[-1] + A[k] - v)
    right_sum = right_sum[::-1]

    ans_candidate = [a - b for a, b in zip(left_sum, right_sum)]
    return max(ans_candidate)

N = int(input())
A = [int(i) for i in input().split()]
print(d_3n_numbers(N, A))

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
#import sys
from heapq import heapify, heappushpop
from heapq import _heapify_max as heapify_max, _siftup_max


def heappushpop_max(heap, item):
    if heap and heap[0] > item:
        item, heap[0] = heap[0], item
        _siftup_max(heap, 0)
    return item


fin = sys.stdin.readline
N, *a_list = map(int, open(0).read().split())

left_pq = a_list[:N]
right_pq = a_list[2 * N:]
heapify(left_pq)
heapify_max(right_pq)

left_sum = [sum(left_pq)]
right_sum = [sum(right_pq)]
for k in range(N, 2 * N):
    left_item = a_list[k]
    right_item = a_list[-k - 1]
    left_sum.append(left_sum[-1] - heappushpop(left_pq, left_item) + left_item)
    right_sum.append(right_sum[-1] - heappushpop_max(right_pq, right_item) + right_item)

max_sum = max(map(sum, zip(left_sum, [-item for item in right_sum[::-1]])))
print(max_sum)