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 .

Solution (Python):
from heapq import heappush, heappop
n=int(input())
a=list(map(int,input().split()))
l=[]
for v in a[:n]:
  heappush(l,v)
suml=[sum(a[:n])]
for i in range(n):
  suml.append(suml[i]+a[n+i])
  heappush(l,a[n+i])
  suml[i+1]-=heappop(l)
r=[]
for v in a[2*n:]:
  heappush(r,(10**10-v,v))
sumr=[sum(a[2*n:])]
for i in range(n):
  sumr.append(sumr[i]+a[2*n-i-1])
  heappush(r,(10**10-a[2*n-i-1],a[2*n-i-1]))
  _,t=heappop(r)
  sumr[i+1]-=t
ans=-10**20
for i in range(n+1):
  ans=max(ans,suml[i]-sumr[n-i])
print(ans)

Solution (Python):
import bisect
N = int(input())
A = list(map(int, input().split()))
L = sorted(A[:2*N])
sumL = sum(L[N:])
R = sorted(A[N:])
sumR = sum(R[:N])
AL = [sumL]
p = N
BL = [False] * (2*N)
for a in reversed(A[N:2*N]):  
    ind = bisect.bisect_left(L, a)
    if BL[ind] != False:
        BL[ind] += 1
        ind += BL[ind] - 1
    if ind >= p:
        sumL -= L[ind]
        p -= 1
        while BL[p] != False:
            p -= 1
        sumL += L[p]
    AL.append(sumL)
    BL[ind] = 1
AR = [sumR]
p = N-1
BR = [False] * (2*N)
for a in A[N:2*N]:  
    ind = bisect.bisect_left(R, a)
    if BR[ind] != False:
        BR[ind] += 1
        ind += BR[ind] - 1
    if ind <= p:
        sumR -= R[ind]
        p += 1
        while BR[p] != False:
            p += 1
        sumR += R[p]
    AR.append(sumR)
    BR[ind] = 1
AL.reverse()
C = [AL[i] - AR[i] for i in range(N+1)]
print(max(C))

Solution (Python):
import heapq
n = int(input())
a,b = [int(i) for i in input().split()],[]
for i in a: b.append(-i)
x,y = a[:n],b[2*n:]
heapq.heapify(x)
heapq.heapify(y)
num,num2 = sum(a[:n]),sum(a[2*n:])
a2,b2 = [num],[num2]
for i in range(n+1,2*n+1):
	j = 3*n+1-i
	num += a[i-1]-heapq.heappushpop(x,a[i-1])
	num2 += a[j-1]+heapq.heappushpop(y,b[j-1])
	a2.append(num)
	b2.append(num2)
b2,ans = b2[::-1],-float("inf")
for i in range(n+1): ans = max(ans,a2[i]-b2[i])
print(ans)

Solution (Python):
import heapq

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


left, right = A[:N], A[-N:]

right = list(map(lambda x: -x, right))
left_sum, right_sum = [sum(left)], [-sum(right)]
heapq.heapify(left)
heapq.heapify(right)


for i in range(N, 2*N):
    heapq.heappush(left, A[i])
    low = heapq.heappop(left)
    left_sum.append(left_sum[-1] + A[i] - low)


for i in range(2*N-1, N-1, -1):
    heapq.heappush(right, -A[i])
    high = -heapq.heappop(right)
    right_sum.append(right_sum[-1] + A[i] - high)


right_sum = right_sum[::-1]

ans = max([l-r for l, r in zip(left_sum, right_sum)])
print(ans)

Solution (Python):
import heapq

N=int(input())
A=[int(x) for x in input().split()]

a=A[:N]
b=A[-N:]
c=A[N:-N]
res=[sum(a)]


heapq.heapify(a)
for i in range(N):
  heapq.heappush(a,c[i])
  k=heapq.heappop(a)
  res.append(res[-1]+c[i]-k)

cnt=sum(b)
for i in range(N):
  b[i]*=-1

max_ans=res[N]-cnt

heapq.heapify(b)
for i in range(N-1,-1,-1):
  heapq.heappush(b,-c[i])
  k=heapq.heappop(b)
  res[i]-=(cnt+c[i]+k)
  cnt=cnt+c[i]+k
  max_ans=max(max_ans,res[i])

print(max_ans)

Solution (Python):
def d_3N_Numbers(N, A):
    import heapq
    left = A[:N]
    heapq.heapify(left)
    
    
    right = [-i for i in A[2 * N:]]
    heapq.heapify(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))
    right_sum = right_sum[::-1]
    ans = []
    for a, b in zip(left_sum, right_sum):
        ans.append(a - b)
    return max(ans)

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

Solution (Python):
n=int(input())
import heapq
a=map(int, raw_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])))

Solution (Python):
import itertools
import datetime
from heapq import heapify,heappush,heappop



N=input()
a=[]
a=map(int, raw_input().split())
a1=a[:N]



heapify(a1)

l1=[]
sum_a1=sum(a1)
l1.append(sum_a1)




for i in range(N,2*N):
	if a[i]>a1[0]:
		sum_a1=sum_a1+a[i]-a1[0]
		heappop(a1)
		heappush(a1, a[i])

	l1.append(sum_a1)

 

l2=[]
a2=[ -x for x in a[2*N:]]
heapify(a2)
sum_a2=-1*sum(a2)
l2.append(sum_a2)


for i in reversed(range(N,2*N)):
	if a[i]<-1*a2[0]:
		sum_a2=sum_a2+a[i]-(-1*a2[0])
		heappop(a2)
		heappush(a2,-1*a[i])
	l2.append(sum_a2)


ans=[]
for i in range(N+1):
	heappush(ans, -1*(l1[i]-l2[N-i]))

print ans[0]*-1

Solution (Python):
import itertools
from heapq import heapify,heappush,heappop

N=input()
a=[]
a=map(int, raw_input().split())
a1=a[0:N]


heapify(a1)

l1=[]
sum_a1=sum(a1)
l1.append(sum_a1)


for i in range(N,2*N):
	if a[i]>a1[0]:
		sum_a1=sum_a1+a[i]-a1[0]
		heappop(a1)
		heappush(a1, a[i])

	l1.append(sum_a1)


l2=[]
a2=[ -x for x in a[2*N:3*N]]
heapify(a2)
sum_a2=-1*sum(a2)
l2.append(sum_a2)


for i in reversed(range(N,2*N)):
	if a[i]<-1*a2[0]:
		sum_a2=sum_a2+a[i]-(-1*a2[0])
		heappop(a2)
		heappush(a2,-1*a[i])
	l2.append(sum_a2)


ans=[]
for i in range(N+1):
	ans.append(l1[i]-l2[N-i])

print max(ans)

Solution (Python):

"""
http://abc062.contest.atcoder.jp/tasks/arc074_b

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


def solve(A, N):
    red_pq = []
    blue_pq = []

    for a in A[:N]:
        heappush(red_pq, a)
    red_total = sum(A[:N])

    blue_total = 0
    for a in A[2*N:]:
        heappush(blue_pq, -a)
        blue_total += a

    blue_lut = [0] * (3*N)
    blue_lut[2*N] = blue_total
    for k in range(2*N - 1, N - 1, -1):
        t1 = A[k]
        heappush(blue_pq, -t1)
        t2 = heappop(blue_pq)
        blue_total += (t1 + t2)
        blue_lut[k] = blue_total

    best_ans = red_total - blue_total

    for k in range(N, 2*N):
        t1 = A[k]
        heappush(red_pq, t1)
        t2 = heappop(red_pq)
        red_total += (t1 - t2)

        ans = red_total - blue_lut[k+1]
        best_ans = max(best_ans, ans)

    return best_ans


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    result = solve(A, N)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
import heapq

N = int(input())
a = [int(n) for n in input().split()]
former = a[:N]

heapq.heapify(former)

former_sum = [sum(former)]


for k in range(N):
  heapq.heappush(former, a[N+k])
  former_sum.append(former_sum[k]+a[N+k]-heapq.heappop(former))

a = [n * (-1) for n in a]
latter = a[2*N:]
heapq.heapify(latter)
latter_sum = [sum(latter)]

for k in range(N):
  heapq.heappush(latter, a[2*N-k-1])
  latter_sum.append(latter_sum[k] + a[2*N-k-1] - heapq.heappop(latter))

res = [former_sum[k] + latter_sum[N-k] for k in range(N+1)]

print(max(res))

Solution (Python):
import heapq

N = int(input())
a = [int(n) for n in input().split()]
former = a[:N]

heapq.heapify(former)

former_sum = [sum(former)]


for k in range(N):
  heapq.heappush(former, a[N+k])
  former_sum.append(former_sum[k]+a[N+k]-heapq.heappop(former))

a = [n * (-1) for n in a]
latter = a[2*N:]
heapq.heapify(latter)
latter_sum = [sum(latter)]

for k in range(N):
  heapq.heappush(latter, a[2*N-k-1])
  latter_sum.append(latter_sum[k] + a[2*N-k-1] - heapq.heappop(latter))

res = [former_sum[k] + latter_sum[N-k] for k in range(N+1)]

print(max(res))

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

a1h = a[:N]
a2h = [-ai for ai in a[2 * N:]]

import heapq
heapq.heapify(a1h)
heapq.heapify(a2h)

sum1 = [sum(a1h)]
sum2 = [sum(a2h)]
for k in range(N, 2 * N):
    sum1.append(sum1[-1] + a[k] - heapq.heappushpop(a1h, a[k]))
    sum2.append(sum2[-1] + -a[-k - 1] - heapq.heappushpop(a2h, -a[-k - 1]))

print(max(map(sum, zip(sum1, sum2[::-1]))))

Solution (Python):
import heapq

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

q = a[:N]
heapq.heapify(q)
x = [sum(q)]

for k in range(N, 2*N):
    
    out = heapq.heappushpop(q, a[k])
    x.append(x[-1]+a[k]-out)
    
a = a[::-1]    
q = [-v for v in a[:N]]
heapq.heapify(q)
y = [-sum(q)]
for k in range(N, 2*N):
    out = -heapq.heappushpop(q, -a[k])
    y.append(y[-1]+a[k]-out)
    
print(max(v-w for v,w in zip(x, y[::-1])))

Solution (Python):
import heapq

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

red, blue = a[:n], [-1*i for i in a[2*n:]]
sr, sb = sum(red), sum(blue)

results = [0] * (n + 1)
results[0] = sr
results[-1] = sb

heapq.heapify(red)
heapq.heapify(blue)

for k in range(n, 2*n):
    v = a[k]
    p = heapq.heappushpop(red, v)
    sr += v - p
    results[k-n+1] += sr

for k in range(2*n-1, n-1, -1):
    v = -1 * a[k]
    p = heapq.heappushpop(blue, v)
    sb += v - p
    results[k-n] += sb

print(max(results))

Solution (Python):
import heapq

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

red = a[:n]
sr = sum(red)
sum_red = {n: sr}
heapq.heapify(red)


blue = [-1 * i for i in a[2*n:]]
sb = sum(blue)
sum_blue = {2 * n: sb}
heapq.heapify(blue)


for k in range(n, 2 * n):
    popped_red = heapq.heappushpop(red, a[k])
    sr += a[k] - popped_red
    sum_red[k + 1] = sr
    

for k in range(2 * n - 1, n - 1, -1):
    popped_blue = heapq.heappushpop(blue, -1  * a[k])
    sb += -1 * a[k] - popped_blue
    sum_blue[k] = sb
    

ans = -1 * float('inf')
for k in range(n, 2 * n + 1):
    ans = max(ans, sum_red[k] + sum_blue[k])
    

print(ans)

Solution (Python):
import heapq
N=int(input())
a=list(map(int,input().split()))
earl=[]
late=[]
for i in range(N):
  heapq.heappush(earl,a[i])
  heapq.heappush(late,-a[2*N+i])
E=0
L=0
for i in range(N):
  E+=a[i]
  L-=a[2*N+i]
e=[E]*(N+1)
l=[L]*(N+1)
for i in range(N):
  e[i+1]=e[i]+a[N+i]-heapq.heappushpop(earl,a[N+i])
  l[N-1-i]=l[N-i]-a[2*N-1-i]-heapq.heappushpop(late,-a[2*N-1-i])

ans=e[N]+l[N]
for i in range(N):
  ans=max(ans,e[i]+l[i])
print(ans)

Solution (Python):
N = int(input())
array = [int(n) for n in input().split()]
import copy
import heapq
lst = [None for i in range(N + 1)]
left_lst = copy.deepcopy(lst)
right_lst = copy.deepcopy(lst)
left_array = array[:N]
right_array= [-n for n in array[-N:]]
l_sum = sum(left_array)
r_sum = sum(right_array)
heapq.heapify(left_array)
heapq.heapify(right_array)
left_lst[0] = l_sum
right_lst[0] = r_sum

for k in range(N, 2 * N):
    new_a, new_b = array[k], array[-k - 1]*-1
    heapq.heappush(left_array,new_a)
    heapq.heappush(right_array,new_b)
    old_a = heapq.heappop(left_array)
    l_sum += (new_a - old_a)
    left_lst[k - N + 1] = l_sum
    old_b = heapq.heappop(right_array)
    r_sum += (new_b - old_b)
    right_lst[k - N + 1] = r_sum
lst = [ a + b for a, b in zip(left_lst, list(reversed(right_lst)))]
print(max(lst))

Solution (Python):
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])

Solution (Python):
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))

Solution (Python):
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)
  
 
  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)
  
  
  best = float("-inf")
  for i in range(n+1):
    score = esums[i] + lsums[n-i]
    
    if(best < score) : best = score
  return best

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

Solution (Python):
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])))

Solution (Python):
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)])))))))

Solution (Python):
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)])))))))

Solution (Python):
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)]))))))

Solution (Python):
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)]))))))

Solution (Python):
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)]))))))

Solution (Python):
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)]))))))

Solution (Python):
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])))))))))

Solution (Python):
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])))))))))

Solution (Python):
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])]))

Solution (Python):


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)

Solution (Python):
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)

Solution (Python):
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)))))

Solution (Python):
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)))

Solution (Python):
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))))