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):
import heapq
n=int(input())
a=[int(i) for i in input().split()]
 
heap_left=[]
left=0
for i in range(n):
    left+=a[i]
    heapq.heappush(heap_left,a[i])
 
lst_left=[left]
for i in range(n,2*n):
    tmp=heapq.heappushpop(heap_left,a[i])
    left=left-tmp+a[i]
    lst_left+=[left]
 
heap_right=[]
right=0
for i in range(2*n,3*n):
    right+=a[i]
    heapq.heappush(heap_right,-a[i])
 
lst_right=[right]
for i in range(2*n-1,n-1,-1):
    tmp=heapq.heappushpop(heap_right,-a[i])
    right=right-(-tmp)+a[i]
    lst_right+=[right]
 

ans=-10**100
for i in range(n+1):
    ans=max(ans,lst_left[i]-lst_right[-(i+1)])
 
print (ans)

Solution (Python):
import heapq

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

push = heapq.heappush
pop = heapq.heappop
lq = []
l = [0] * (N + 1)
for i in range(N):
  push(lq, a[i])
  l[0] += a[i]
for i in range(N):
  l[i + 1] = l[i]
  x = pop(lq)
  if a[N + i] > x:
    l[i + 1] += a[N + i] - x
    push(lq, a[N + i])
  else:
    push(lq, x)

rq = []
r = [0] * (N + 1)
for i in range(N):
  push(rq, -a[-1 -i])
  r[-1] += a[-1 -i]
for i in range(N):
  r[-2 -i] = r[-1 -i]
  x = pop(rq)
  if a[-N-1 -i] < -x:
    r[-2 -i] -= -x -a[-N-1 -i]
    push(rq, -a[-N-1 -i])
  else:
    push(rq, x)

ans = l[0] - r[0]
for i in range(1, N + 1):
  ans = max(ans, l[i] - r[i])

print(ans)

Solution (Python):
import heapq
N = int(input())
A = list(map(int,input().split()))

f = A[:N]
heapq.heapify(f)
S = sum(f)
fs = [S]
for i in range(N):
    a = A[N+i]
    S += a
    heapq.heappush(f,a)
    a = heapq.heappop(f)
    S -= a
    fs.append(S)

l = [-a for a in A[2*N:]]
heapq.heapify(l)
S = sum(l)
ls = [S]
for i in range(N):
    a = -A[2*N-i-1]
    S += a
    heapq.heappush(l,a)
    a = heapq.heappop(l)
    S -= a
    ls.append(S)

ans = -10**15
for i in range(N+1):
    ans = max(ans,fs[i]+ls[N-i])
print(ans)

Solution (Python):
from heapq import heappush,heappop
n=int(input()); a=[int(_) for _ in input().split()]
fh=[]; lh=[]
for i in range(n):
    heappush(fh, a[i])
    heappush(lh, -1*a[-i-1])
f=[sum(fh)]; l=[-1*sum(lh)]
for i in range(n,2*n):
    heappush(fh, a[i]); f.append(f[-1]+a[i]-heappop(fh))
    heappush(lh, -1*a[-i-1]); l.append(l[-1]+a[-i-1]+heappop(lh))
ans=-10**15
for i,j in zip(f,l[::-1]):ans=max(ans, i-j)
print(ans)

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

heap_left = []
left = 0
for i in range(N):
    left += a[i]
    heapq.heappush(heap_left, a[i])

lst_left = [left]
for i in range(N, 2 * N):
    tmp = heapq.heappushpop(heap_left, a[i])
    left = left - tmp + a[i]
    lst_left += [left]

heap_right = []
right = 0
for i in range(2 * N, 3 * N):
    right += a[i]
    heapq.heappush(heap_right, -1 * a[i])

lst_right = [right]
for i in range(2 * N -1, N-1, -1):
    tmp = heapq.heappushpop(heap_right, -1 * a[i])
    right = right - (-1 * tmp) + a[i]
    lst_right += [right]



ans = -1 * 10 ** 20
for i in range(N+1):
    
    ans = max(ans, lst_left[i]-lst_right[-(i+1)])

print (ans)

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

heap_left = []
left = 0
for i in range(N):
    left += a[i]
    heapq.heappush(heap_left, a[i])

lst_left = [left]
for i in range(N, 2 * N):
    tmp = heapq.heappushpop(heap_left, a[i])
    left = left - tmp + a[i]
    lst_left += [left]

heap_right = []
right = 0
for i in range(2 * N, 3 * N):
    right += a[i]
    heapq.heappush(heap_right, -1 * a[i])

lst_right = [right]
for i in range(2 * N -1, N-1, -1):
    tmp = heapq.heappushpop(heap_right, -1 * a[i])
    right = right - (-1 * tmp) + a[i]
    lst_right += [right]



ans = -1 * 10 ** 20
for i in range(N+1):
    
    ans = max(ans, lst_left[i]-lst_right[-(i+1)])

print (ans)

Solution (Python):

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)

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())


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



leftQ = As[:N]
rightQ = minusAs[-N:]
heapq.heapify(leftQ)
heapq.heapify(rightQ)


leftsum = [0]*(N+1)
rightsum = [0]*(N+1) 



leftsum[0] = sum(leftQ)
rightsum[0] = sum(rightQ)

for i in range(N, 2*N): 
  
  
  if leftQ[0] < As[i]: 
    
    nowmin = heapq.heappop(leftQ)
    leftsum[i-N+1] = leftsum[i-N] - nowmin + As[i]
    heapq.heappush(leftQ,As[i])
  else: leftsum[i-N+1] = leftsum[i-N] 
  if rightQ[0] < minusAs[-1-i]: 
    nowmax = heapq.heappop(rightQ)
    rightsum[i-N+1] = rightsum[i-N] - nowmax + minusAs[-1-i]
    heapq.heappush(rightQ,minusAs[-1-i])
  else: rightsum[i-N+1] = rightsum[i-N] 

ans = -INF
for lsum, rsum in zip(leftsum, rightsum[::-1]):

  ans = max(ans, lsum+rsum)

print(ans)

Solution (Python):
import heapq

n = int(input())
A = [int(x) for x in input().split()]
A_rev = [-x for x in A[::-1]]

def get_sum_list(A):
  h = []
  result = []
  current_sum = 0
  for i,a in enumerate(A[:2*n]):
    heapq.heappush(h,a)
    current_sum += a
    if i >= n:
      m = heapq.heappop(h)
      current_sum -= m
    if i >= n-1:
      result.append(current_sum)
  return result

from_left = get_sum_list(A)
from_right = get_sum_list(A_rev)

ans = -10**18
for i in range(n+1):
  score = from_left[i] + from_right[n-i]
  if ans < score:
    ans = score
    
print(ans)

Solution (Python):
import heapq
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

A = np.array(A, dtype=int)




lefts = list(A[:N])
heapq.heapify(lefts)

L_sum = sum(lefts)
L_hist = [L_sum]
for div in range(N, 2 * N):
    if A[div] > lefts[0]:
        L_sum += A[div] - lefts[0]
        heapq.heapreplace(lefts, A[div])
    L_hist.append(L_sum)

rights = list(-A[N * 2:])
heapq.heapify(rights)
r_sum = -sum(rights)
r_hist = [r_sum]
for div in reversed(range(N, 2 * N)):
    if A[div] < -rights[0]:
        r_sum += A[div] - (-rights[0])
        heapq.heapreplace(rights, -A[div])
    r_hist.append(r_sum)
r_hist.reverse()

ans = -INF
for l, r in zip(L_hist, r_hist):
    ans = max(ans, l - r)
print(ans)

Solution (Python):
import heapq

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

B=A[:N]
S=sum(B)
heapq.heapify(B)

BS=[0]*(3*N)
BS[N]=S
for i in range(N,2*N):
    if B[0]<A[i]:
        x=heapq.heappop(B)
        S+=A[i]-x
        heapq.heappush(B,A[i])

    BS[i+1]=S
        
    
C=[-c for c in A[2*N:]]
S=-sum(C)
heapq.heapify(C)

CS=[0]*(3*N)
CS[2*N]=S

for i in range(2*N-1,N-1,-1):
    if -C[0]>A[i]:
        x=-heapq.heappop(C)
        S+=A[i]-x
        heapq.heappush(C,-A[i])

    CS[i]=S

ANS=-float("inf")
for i in range(N,2*N+1):
    ANS=max(ANS,BS[i]-CS[i])

print(ANS)

Solution (Python):




from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)



def main():
    n,*a=map(int,open(0).read().split())
    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
    print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1]))))
if __name__ == '__main__':
    main()

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop,heapify
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    def rev(n):
        return -n
    N = I()
    A = LI()
    left_sum = [sum(A[:N])]  
    left = A[:N]
    heapify(left)
    right_sum = [sum(A[2 * N:])]
    right=list(map(rev,A[2*N:]))
    heapify(right)
    for k in range(1, N + 1):
        heappush(left, A[N - 1 + k])
        poped = heappop(left)
        left_sum.append(left_sum[-1] + A[N - 1 + k] - poped)

        heappush(right, -A[-N - k])
        poped = -heappop(right)
        right_sum.append(right_sum[-1] + A[-N - k] - poped)
    ans = -inf
    for k in range(N + 1):
        ans = max(ans, left_sum[k] - right_sum[-k - 1])
    print(ans)
if __name__ == '__main__':
    main()

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

b=a[::-1]
A=a[:N]

AR=[A[0]]
for i in range(1,len(A)*2):
    AR.append(a[i]+AR[i-1])

AL=[]

heapq.heapify(A)
for i in range(N,N*2):
    heapq.heappush(A,a[i])
    AL.append(A[0])
    heapq.heappop(A)

ALR=[AL[0]]
for i in range(1,len(AL)):
    ALR.append(ALR[i-1]+AL[i])

ANSA=[AR[N-1]]
for i in range(len(ALR)):
    ANSA.append(AR[N+i]-ALR[i])


B=b[:N]
for i in range(len(B)):
    B[i]*=-1

BR=[B[0]]
for i in range(1,len(B)*2):
    BR.append(-b[i]+BR[i-1])

BL=[]

heapq.heapify(B)
for i in range(N,N*2):
    heapq.heappush(B,-b[i])
    BL.append(-B[0])
    heapq.heappop(B)

BLR=[BL[0]]
for i in range(1,len(BL)):
    BLR.append(BLR[i-1]+BL[i])

BNSA=[BR[N-1]]
for i in range(len(BLR)):
    BNSA.append(BR[N+i]+BLR[i])

BNSA=BNSA[::-1]

ANS=-10**20
for i in range(len(BNSA)):
    if (ANSA[i]+BNSA[i])>ANS:
        ANS=(ANSA[i]+BNSA[i])
print(ANS)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
l = a[:n]
m = a[n:2*n]
r = list(map(lambda x: -x, a[2*n:]))


import heapq
heapq.heapify(l)
heapq.heapify(r)
lremovesum = [0]
rremovesum = [0]


ruisekil = [sum(l)]
ruisekir = [sum(r)]
for i in range(n):
    ruisekil.append(ruisekil[-1] + m[i])
    ruisekir.append(ruisekir[-1] - m[-i - 1])
    
ruisekir.reverse()

for i in range(n):
    heapq.heappush(l, m[i])
    lremovesum.append(lremovesum[-1] + heapq.heappop(l))
    heapq.heappush(r, -m[-i-1])
    rremovesum.append(rremovesum[-1] + heapq.heappop(r))
rremovesum.reverse()









ans = -10**20
for i in range(n + 1):
    
    
    ans = max(ans, ruisekil[i]-lremovesum[i]+ruisekir[i]-rremovesum[i])

print(ans)

Solution (Python):
import heapq
n=int(input())
A=[int(i) for i in input().split()]
AL=A[:n]
AR=[0]*n
for i in range(2*n,3*n):
  AR[i-2*n]-=A[i]
ALS,ARS=[0]*(n+1),[0]*(n+1)
ALS[0],ARS[0]=sum(AL),sum(AR)
heapq.heapify(AL)
heapq.heapify(AR)
for i in range(n):
  l,r=A[n+i],-A[2*n-i-1]
  heapq.heappush(AL,l)
  ALS[i+1]=ALS[i]+l-heapq.heappop(AL)
  heapq.heappush(AR,r)
  ARS[i+1]=ARS[i]+r-heapq.heappop(AR)
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]+ARS[n-i])
print(ans)

Solution (Python):
import heapq

N = int(input())
A = list(map(int, input().split()))
 
L = A[:N]
heapq.heapify(L) 

sum_L = [0] * (N+1)
sum_L[0] = sum(L)

for i in range(N):
    min_L = heapq.heappushpop(L, A[N+i])
    sum_L[i+1] = sum_L[i] + A[N+i] - min_L
    

R = A[N*2:]
rev_R = list(map(lambda x: -x, R))
heapq.heapify(rev_R) 

sum_R = [0] * (N+1)
sum_R[N] = sum(R)

for i in range(N-1, -1, -1):
    max_R = -heapq.heappushpop(rev_R, -A[N+i])
    sum_R[i] = sum_R[i+1] + A[N+i] - max_R
    

ans = -10**14

for i in range(N+1):
    ans = max(ans, sum_L[i] - sum_R[i])

print(ans)

Solution (Python):
import heapq

N = int(input())
A = list(map(int, input().split()))
 
L = A[:N]
heapq.heapify(L) 

sum_L = [0] * (N+1)
sum_L[0] = sum(L)

for i in range(N):
    min_L = heapq.heappushpop(L, A[N+i])
    sum_L[i+1] = sum_L[i] + A[N+i] - min_L
    

R = A[N*2:]
rev_R = list(map(lambda x: x*(-1), R))
heapq.heapify(rev_R) 

sum_R = [0] * (N+1)
sum_R[N] = sum(R)

for i in range(N-1, -1, -1):
    max_R = heapq.heappushpop( rev_R, A[N+i]*(-1) ) * (-1)
    sum_R[i] = sum_R[i+1] + A[N+i] - max_R
    

ans = -10**14

for i in range(N+1):
    ans = max(ans, sum_L[i] - sum_R[i])

print(ans)

Solution (Python):
import heapq
N = int(input())
li = [ int(it) for it in input().split() ]

X = li[:N]
sX = [0]*(N+1)
sX[0] = sum(X)
heapq.heapify(X) 
for i in range(N):
  pu = li[N+i]
  heapq.heappush(X,pu)
  po = heapq.heappop(X)
  sX[1+i] = sX[i] + pu - po

li = [ -li[3*N-1-i] for i in range(3*N)] 
Y = li[:N]
sY = [0]*(N+1)
sY[0] = sum(Y)
heapq.heapify(Y) 
for i in range(N):
  pu = li[N+i]
  heapq.heappush(Y,pu)
  po = heapq.heappop(Y)
  sY[1+i] = sY[i] + pu - po

  
s = -100000000000000000000000
for i in range(N+1):
  s = max( sX[i] + sY[N-i] ,s )
print  (s)

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

Solution (Python):
def f(a):
	q=a[:n];s=sum(q);heapify(q)
	for e in a[n:n-~n]:yield s;s+=e-heappushpop(q,e)
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-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*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1]))))

Solution (Python):
def f(x):
    y=x[:n];heapify(y);z=sum(y);yield z
    for i in x[n:n*2]:z+=i-heappushpop(y,i);yield z
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f([-i for i in a[n:][::-1]]),list(f(a))[::-1]))))

Solution (Python):
def f(x):
    y=x[:n];heapify(y);z=sum(y);s=[z]
    for i in x[n:n*2]:z+=i-heappushpop(y,i);s+=[z]
    return s
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f([-i for i in a[n:][::-1]]),f(a)[::-1]))))

Solution (Python):
def f(x):
    y=x[:n];heapify(y);z=sum(y);s=[z]
    for i in x[n:n*2]:z+=i-heappushpop(y,i);s+=[z]
    return s
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f([-i for i in a[n:][::-1]]),f(a)[::-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*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1]))))

Solution (Python):
import heapq
N = int(input())
a = [int(i) for i in input().split()]

before = []
after = []
before_sum = 0
after_sum = 0
for i in range(N):
    heapq.heappush(before, a[i])
    before_sum += a[i]

for i in range(2*N, 3*N):
    heapq.heappush(after, -a[i])
    after_sum -= a[i]

c = [0] * (N+1)
c[0] = before_sum
c[N] = after_sum
for i in range(N):
    before_sum = before_sum - heapq.heappushpop(before, a[N+i]) + a[N+i]
    c[i+1] += before_sum
    after_sum = after_sum - heapq.heappushpop(after, -a[(2*N)-i-1]) - a[(2*N)-i-1]
    c[N-i-1] += after_sum

print(max(c))

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))

    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))

Solution (Python):
import sys
from heapq import heapify, heappush, heappushpop

def main():
    input = sys.stdin.readline
    N = int(input())

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

    F = [0 for _ in range(N+1)]
    B = [0 for _ in range(N+1)]
    F[0] = sum(A[:N])
    B[N] = sum(A[2*N:])

    Ffactors = []
    Bfactors = []
    for i in range(N):
        heappush(Ffactors, A[i])
        heappush(Bfactors, -A[3*N-1-i])

    for i in range(1, N+1):
        F[i] = F[i-1] + A[N-1+i] - heappushpop(Ffactors, A[N-1+i])
        B[N-i] = B[N+1-i] + A[2*N-i] + heappushpop(Bfactors, -A[2*N-i])

    ans = -float('inf')
    for i in range(N+1):
        ans = max(ans, F[i] - B[i])

    return ans


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

Solution (Python):
from heapq import heappush,heappop
dataX=[]
dataY=[]
mae=dict()
ushiro=dict()
N=int(input())
A=list(map(int,input().split()))
X=A[0:N]
Y=A[N:2*N]
Z=A[2*N:3*N]
for i in range(N):
    heappush(dataX,X[i])
    heappush(dataY,-1*Z[i])
mae[0]=sum(X)
ushiro[0]=-1*sum(Z)
for i in range(1,N+1):
    mae[i]=mae[i-1]+Y[i-1]
    heappush(dataX,Y[i-1])
    mae[i]-=heappop(dataX)
    ushiro[i]=ushiro[i-1]-Y[N-i]
    heappush(dataY,-1*Y[N-i])
    ushiro[i]-=heappop(dataY)
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)

Solution (Python):
import sys,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()    
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

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

res = [0]*(n+1)
head = a[:n:]
heapq.heapify(head)
p = sum(head)
for i in range(n+1):
    res[i] = p
    p += a[n+i]
    heapq.heappush(head,a[n+i])
    p -= heapq.heappop(head)
end = a[2*n::]
heapq._heapify_max(end)
q = sum(end)
for i in range(n+1):
    res[n-i] -= q
    q += a[2*n-1-i]
    _heappush_max(end,a[2*n-1-i])
    q -= _heappop_max(end)
print(max(res))

Solution (Python):
import heapq


class PriorityQueue:
    def __init__(self):
        self.__heap = []
        self.__count = 0

    def empty(self) -> bool:
        return self.__count == 0

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        self.__count -= 1
        return heapq.heappop(self.__heap)

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__heap, v)

    def __len__(self):
        return self.__count


def _3N_numbers(N: int, A: list)->int:
    
    q = PriorityQueue()
    first_half = [0] * (N+1)
    for i in range(N):
        q.enqueue(A[i])
        first_half[0] += A[i]

    for k in range(N):
        q.enqueue(A[N+k])
        decrement = q.dequeue()
        first_half[k+1] = first_half[k] - decrement + A[N+k]

    
    q = PriorityQueue()
    second_half = [0] * (N+1)
    for i in range(N):
        q.enqueue(-A[3*N-1-i])
        second_half[N] += A[3*N-1-i]

    for k in range(N):
        q.enqueue(-A[2*N-1-k])
        decrement = -q.dequeue()
        second_half[N-(k+1)] = second_half[N-k] - decrement + A[2*N-1-k]

    return max(f - s for f, s in zip(first_half, second_half))


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _3N_numbers(N, A)
    print(ans)

Solution (Python):
import heapq

n = int(input())

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

func = lambda p: p * (-1)

b = list(map(func,a[:]))




l = [0] * (3*n)

first = a[0:n]
second = b[2*n:3*n]

x = [0] * (3*n)
y = [0] * (3*n)

x[n-1] = sum(first)
y[2*n-1] = sum(second)

heapq.heapify(first)
heapq.heapify(second)

for i in range(n,2*n):
    heapq.heappush(first, a[i])
    s = first[0]
    heapq.heappop(first)
    x[i] = x[i-1] + a[i] - s

for i in range(n,2*n):
    heapq.heappush(second, b[-i-1])
    t = second[0]
    heapq.heappop(second)
    y[-i-2] = y[-i-1] + b[-i-1] - t
    
for i in range(n-1,2*n):
    l[i] = x[i] + y[i]
    




print(max(l[n-1:2*n]))

Solution (Python):
import heapq

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

ante, post = alist[:n], alist[-n:]
antesums = [0 for _ in range(n+1)]
postsums = [0 for _ in range(n+1)]
antesums[0] = sum(ante)
postsums[0] = sum(post)
post = list(map(lambda x: -x, post))
heapq.heapify(ante)
heapq.heapify(post)

for k in range(n):
  minante = heapq.heappushpop(ante, alist[n+k])
  antesums[k+1] = antesums[k] + alist[n+k] - minante
  maxpost = heapq.heappushpop(post, -alist[2*n-k-1])
  postsums[k+1] = postsums[k] + alist[2*n-k-1] + maxpost

ans = -sum(alist)
for k in range(n+1):
  if ans < antesums[k] - postsums[-k-1]:
    ans = antesums[k] - postsums[-k-1]
print(ans)

Solution (Python):
import heapq
import copy
N = int(input())
a = list(map(int,input().split()))
leftHeap = copy.copy(a[0:N])
rightHeap = [-a[i] for i in range(2*N,3*N)]
heapq.heapify(leftHeap)
heapq.heapify(rightHeap)
leftSideTakenSum = [0] 
rightSideTakenSum = [0] 
for i in range(1,N+1):
  left = heapq.heappushpop(leftHeap,a[N+i-1])
  right = -heapq.heappushpop(rightHeap,-a[2*N-i])
  leftSideTakenSum.append(leftSideTakenSum[i-1]+left)
  rightSideTakenSum.append(rightSideTakenSum[i-1]+right)

leftSideSum = 0
for i in range(N):
  leftSideSum += a[i]
totalSum = sum(a)
rightSideSum = totalSum - leftSideSum
answer = -totalSum
for i in range(N+1):
  candidate = leftSideSum - leftSideTakenSum[i] - (rightSideSum - rightSideTakenSum[N-i])
  
  answer = max(answer,candidate)
  leftSideSum += a[N+i]
  rightSideSum -= a[N+i]
print(answer)

Solution (Python):
import heapq
N = int(input())
a = list(map(int, input().split()))
a1 = a[:N]
a2 = [-x for x in a[2 * N:]]
sum1, sum2 = sum(a1), -sum(a2)
heapq.heapify(a1)
heapq.heapify(a2)
s1, s2 = [sum1], [sum2]
for i in range(N):
    heapq.heappush(a1, a[N + i])
    m = heapq.heappop(a1)
    if a[N + i] > m:
        sum1 += a[N + i] - m
    s1.append(sum1)
    heapq.heappush(a2, -a[2 * N - 1 - i])
    m = -heapq.heappop(a2)
    if a[2 * N - 1 - i] < m:
        sum2 += a[2 * N - 1 - i] - m
    s2.append(sum2)
ans = -float("inf")
for i in range(N + 1):
    if ans < s1[i] - s2[N - i]:
        ans = s1[i] - s2[N - i]
print(ans)

Solution (Python):
import heapq


def main():
    N = int(input())
    A = list(map(int, input().split()))
    X = [0] * (N+1)
    X[0] = sum(A[:N])
    Y = [0] * (N+1)
    Y[0] = sum(A[2*N:])
    h = A[:N]
    heapq.heapify(h)
    for i in range(N):
        heapq.heappush(h, A[N + i])
        minimum = heapq.heappop(h)
        X[i+1] = X[i] + A[N + i] - minimum
    h = [-x for x in A[2*N:]]
    heapq.heapify(h)
    for i in range(N):
        heapq.heappush(h, -A[2*N-1 - i])
        maximum = -heapq.heappop(h)
        Y[i+1] = Y[i] + A[2*N-1 - i] - maximum
    ans = - float("inf")
    for i in range(N+1):
        ans = max(ans, X[i] - Y[N-i])
    print(ans)


if __name__ == "__main__":
    main()

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):
import heapq

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

p = [0] * (n + 1)
q = [] + p

L = []
R = []
C = [] + a[n:n * 2]

for i in range(n):
    heapq.heappush(L, a[i])
    heapq.heappush(R, - a[n * 2 + i])

p[0] = sum(L)
q[n] = sum(R)
for i in range(n):
    if C[i] > L[0]:
        p[i + 1] = p[i] + C[i] - L[0]
        heapq.heappop(L)
        heapq.heappush(L, C[i])
    else:
        p[i + 1] = p[i]

    temp = C[n - 1 - i] * -1
    if temp > R[0]:
        q[n - 1 - i] = q[n - i] + temp - R[0]
        heapq.heappop(R)
        heapq.heappush(R, temp)
    else:
        q[n - 1 - i] = q[n - i]

ans = p[n] + q[n]
for i in range(n):
    ans = max(ans, p[i] + q[i])

print(ans)

Solution (Python):
import heapq
n = int(input())
a = list(map(int,input().split()))


left_seq = sorted(a[0:n])
right_seq =  sorted(a[2*n:3*n],reverse=True)
for i in range(n):
  right_seq[i]=-right_seq[i]






left_sum = [0]*(n+1)
right_sum = [0]*(n+1)
left_sum[0] =  sum(left_seq) 
right_sum[n] =  sum(right_seq) 


for i in range(n):
  if left_seq[0]<a[n+i]:
    left_sum[i+1] = left_sum[i] + a[n+i] - left_seq[0]
    heapq.heappop(left_seq)
    heapq.heappush(left_seq, a[n+i])
  else:
    left_sum[i+1] = left_sum[i]
  
  

for i in range(n)[::-1]:
  if right_seq[0]<-a[n+i]:
    right_sum[i] = right_sum[i+1] + (-a[n+i]) - right_seq[0]
    
    heapq.heappop(right_seq)
    heapq.heappush(right_seq, -a[n+i])
    
  else:
    right_sum[i] = right_sum[i+1]
  

ans = -float("inf")
for i in range(n+1):
  
  ans = max(ans,left_sum[i]+right_sum[i])
print(ans)

Solution (Python):
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 = a[i]
    v2, j = left[0]
    if v2 < v1:
        sum1 = sum1 + v1 - v2
        heapq.heappop(left)
        heapq.heappush(left, (v1, i))

    
    
    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)

Solution (Python):



















from heapq import heappush,heappop

N=int(input())
*a,=map(int,input().split())
a=[0]+a

A,B=0,0
As,Bs=[None]*(3*N+1),[None]*(3*N+1)
l,r=[],[]

for p in range(1,N+1):
    heappush(l,a[p])
A=sum(l)
As[N]=A
for p in range(N+1,2*N+1):
    heappush(l,a[p])
    b=heappop(l)
    A=A+a[p]-b
    As[p]=A

for p in range(2*N+1,3*N+1)[::-1]:
    heappush(r,-a[p])
B=-sum(r)
Bs[2*N+1]=B
for p in range(N+1,2*N+1)[::-1]:
    heappush(r,-a[p])
    b=heappop(r)
    B=B+a[p]+b
    Bs[p]=B
    
ans=max(As[p]-Bs[p+1] for p in range(N,2*N+1))
print(ans)

Solution (Python):
from heapq import heappop, heappush

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

r=[None]*(3*N)
s=[None]*(3*N)
p=[]
q=[]
ans=-float("inf")

for i in range(N):
    heappush(p,a[i])
v=sum(p)
r[N-1]=v
for i in range(N,2*N):
    heappush(p,a[i])
    b=heappop(p)
    v=v+a[i]-b
    r[i]=v

for i in range(2*N,3*N)[::-1]:
    heappush(q,-a[i])
v=sum(q)
s[2*N]=-v
for i in range(N,2*N)[::-1]:
    heappush(q,-a[i])
    b=heappop(q)
    v=v-a[i]-b
    s[i]=-v

for i in range(N-1,2*N):
    ans=max(ans,r[i]-s[i+1])

print(ans)

Solution (Python):
import heapq

N = int(input())
a = [int(i) for i in input().split()]

hq = a[0: N]
left_max = [sum(hq)]
heapq.heapify(hq)
for i in range(N):
    left_max.append(left_max[i] + a[N + i] - heapq.heappushpop(hq, a[N + i]))

hq = [-i for i in a[2 * N: 3 * N]]
right_min = [-sum(hq)]
heapq.heapify(hq)
for i in range(N):
    right_min.append(right_min[i] + a[2 * N - i - 1] + heapq.heappushpop(hq, -a[2 * N - i - 1]))

ans = -100000000000000
for i in range(N + 1):
    ans = max(ans, left_max[i] - right_min[N - i])

print(ans)

Solution (Python):
import heapq

N = int(input())
a = [int(i) for i in input().split()]

hq = a[0: N]
left_max = [sum(hq)]
heapq.heapify(hq)
for i in range(N):
    left_max.append(left_max[i] + a[N + i] - heapq.heappushpop(hq, a[N + i]))

hq = [-i for i in a[2 * N: 3 * N]]
right_min = [-sum(hq)]
heapq.heapify(hq)
for i in range(N):
    right_min.append(right_min[i] + a[2 * N - i - 1] + heapq.heappushpop(hq, -a[2 * N - i - 1]))

ans = -100000000000000
for i in range(N + 1):
    ans = max(ans, left_max[i] - right_min[N - i])

print(ans)

Solution (Python):
from heapq import heappush, heappop
n = int(input())
a = input().split()
a = [int(m) for m in a]
t1 = []
t2 = []
mt3 = []
for i in range(3 * n):
    if i < (3 * n) // 3:
        t1.append(a[i])
    elif (3 * n) // 3 <= i < (3 * n) // 3 * 2:
        t2.append(a[i])
    else:
        mt3.append(-a[i])
t1.sort()
mt3.sort()
t1sumli = [sum(t1)]
t3sumli = [-sum(mt3)]
for i in range(n):
    pp = heappop(t1)
    heappush(t1, max(pp, t2[i]))
    t1sumli.append(t1sumli[-1] - pp + max(pp, t2[i]))

for i in range(n - 1, -1, -1):
    qq = -heappop(mt3)
    heappush(mt3, -min(qq, t2[i]))
    t3sumli.append(t3sumli[-1] - qq + min(qq, t2[i]))

sumli = []
for i in range(n + 1):
    sumli.append(t1sumli[i] - t3sumli[-i-1])
print(max(sumli))

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

n = int(input())
lst = list(map(int, input().split()))
preQue = sorted(lst[:n])
mid = lst[n:2*n]
sufQue = sorted([-i for i in lst[2*n:]])

preScore = sum(preQue)
preScores = [preScore]
heapify(preQue)
for i in mid:
    v = heappop(preQue)
    if v < i:
        preScore += (i - v)
        heappush(preQue, i)
    else:
        heappush(preQue, v)
    preScores.append(preScore)

sufScore = sum(sufQue)
sufScores = [sufScore]
heapify(sufQue)
for i in mid[::-1]:
    v = heappop(sufQue)
    if -v > i:
        sufScore += (-v - i)
        heappush(sufQue, -i)
    else:
        heappush(sufQue, v)

    sufScores.append(sufScore)

sufScores.reverse()
ans = max([p + s for p, s in zip(preScores, sufScores)])
print(ans)

Solution (Python):
import heapq
N = int(input())
A = list(map(int, input().split()))

al = A[:N]
heapq.heapify(al)
sal = sum(al)
suml = [sal]
for i in range(N, 2*N):
    if al[0] < A[i]:
        tmp = heapq.heappop(al)
        heapq.heappush(al, A[i])
        sal += A[i]-tmp
    suml.append(sal)

ar = [-a for a in A[2*N:]]
heapq.heapify(ar)
sar = -sum(ar)
sumr = [sar]

ans = -10**15
for i in range(N, 2*N):
    if -ar[0] > A[3*N-1-i]:
        tmp = -heapq.heappop(ar)
        heapq.heappush(ar, -A[3*N-1-i])
        sar += A[3*N-1-i]-tmp
    sumr.append(sar)
for i in range(len(suml)):
    ans = max(ans, suml[i]-sumr[-(i+1)])
print(ans)