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()]
heap1=[]
heap2=[]
a_max=[]
b_max=[]
s=0
for i in range(n):
    heapq.heappush(heap1, a[i])
    s+=a[i]
a_max.append(s)
for i in range(n):
    heapq.heappush(heap1,a[n+i])
    mini=heapq.heappop(heap1)
    s=s+a[n+i]-mini
    a_max.append(s)
s=0
for i in range(n):
    heapq.heappush(heap2,-a[2*n+i])
    s=s-a[2*n+i]
b_max.append(s)    
for i in range(n):
    heapq.heappush(heap2,-a[2*n-1-i])
    mini=heapq.heappop(heap2)
    s=s-a[2*n-1-i]-mini
    b_max.append(s)
ans=a_max[0]+b_max[len(b_max)-1]
for i in range(n+1):
    res=a_max[i]+b_max[-(i+1)]
    ans=max(ans, res)
print(ans)

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

FN = []
SN = []
for i in range(n):
    FN.append(a[i])
for i in range(2*n,3*n):
    SN.append(-a[i])
heapq.heapify(FN)
heapq.heapify(SN)


sumFN = [0]*(n+1)
sumSN = [0]*(n+1)
sumFN[0] = sum(FN)
sumSN[n] = -sum(SN)

for i in range(1,n+1):
    k = 0
    k += a[n-1+i]
    heapq.heappush(FN,a[n-1+i])
    k -= heapq.heappop(FN)
    sumFN[i] = sumFN[i-1]+k

for i in range(n-1,-1,-1):
    k = 0
    k += a[n+i]
    heapq.heappush(SN,-a[n+i])
    k -= -heapq.heappop(SN)
    sumSN[i] = sumSN[i+1]+k

res = sumFN[0]-sumSN[0]
for i in range(n+1):
    res = max(res,sumFN[i]-sumSN[i])
print(res)

Solution (Python):
import heapq

n = int(input())
a = [0] + list(map(int, input().split())) 
selectleft, selectright= [], []
leftscore, rightscore = [], []
for i in range(1,n+1): heapq.heappush(selectleft, a[i]) 
leftscore.append(sum(selectleft)) 
for i in range(n+1,2*n+1): 
    heapq.heappush(selectleft, a[i])
    tmpscore = leftscore[-1] + a[i]
    poped = heapq.heappop(selectleft)
    tmpscore -= poped
    leftscore.append(tmpscore)
for i in range(2*n+1,3*n+1):
    heapq.heappush(selectright, (-1)*a[i]) 
rightscore.append(sum(selectright)*(-1))
for i in range(2*n,n,-1):
    heapq.heappush(selectright, (-1)*a[i])
    tmpscore = rightscore[-1] + a[i]
    poped = heapq.heappop(selectright) * (-1)
    tmpscore -= poped
    rightscore.append(tmpscore)
rightscore.reverse()
print(max(map(lambda x,y:x-y, leftscore, rightscore)))

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

first = []
second = []
for i in range(n):
    first.append(a[i])
for i in range(2*n,3*n):
    second.append(-a[i])
heapq.heapify(first)
heapq.heapify(second)


sumfirst = [0]*(n+1)
sumsecond = [0]*(n+1)
sumfirst[0] = sum(first)
sumsecond[n] = -sum(second)

for i in range(1,n+1):
    k = 0
    k += a[n-1+i]
    heapq.heappush(first,a[n-1+i])
    k -= heapq.heappop(first)
    sumfirst[i] = sumfirst[i-1]+k

for i in range(n-1,-1,-1):
    k = 0
    k += a[n+i]
    heapq.heappush(second,-a[n+i])
    k -= -heapq.heappop(second)
    sumsecond[i] = sumsecond[i+1]+k

res = sumfirst[0]-sumsecond[0]
for i in range(n+1):
    res = max(res,sumfirst[i]-sumsecond[i])
print(res)

Solution (Python):
import heapq
n=int(input())
A=list(map(int,input().split()))
que_left,que_right=[],[]
left,right=[-float("inf")]*(3*n),[float("inf")]*(3*n)
for i in range(n):
    heapq.heappush(que_left,A[i])
    if i==0:
        left[i]=A[i]
    else:
        left[i]=left[i-1]+A[i]
for i in range(n,2*n):
    heapq.heappush(que_left,A[i])
    tmp=heapq.heappop(que_left)
    left[i]=left[i-1]+A[i]-tmp
for i in range(2*n,3*n)[::-1]:
    heapq.heappush(que_right,-A[i])
    if i==3*n-1:
        right[i]=A[i]
    else:
        right[i]=right[i+1]+A[i]
for i in range(n,2*n)[::-1]:
    heapq.heappush(que_right,-A[i])
    tmp=heapq.heappop(que_right)
    right[i]=right[i+1]+A[i]+tmp
ans=-float("inf")
for i in range(n-1,2*n):
    ans=max(ans,left[i]-right[i+1])
print(ans)

Solution (Python):
import heapq as hq
n = input()
arr = map(int,raw_input().split())
h = []
for i in range(n):
	hq.heappush(h,arr[i])
s = sum(h)
z = [s]
for i in range(n,2*n):
	sm = hq.heappop(h)
	hq.heappush(h,max(arr[i],sm))
	s = s-sm+max(sm,arr[i])
	z.append(s)
arr1 = arr[::-1]
h = []
for i in range(n):
	hq.heappush(h,-arr1[i])
s = sum(h)
s = -s
z1 = [s]
for i in range(n,2*n):
	sm = hq.heappop(h)
	hq.heappush(h,max(sm,-arr1[i]))
	s = s+sm+min(-sm,arr1[i])
	z1.append(s)
z1 = z1[::-1]
ans = -10**20
for i in range(len(z)):
	ans = max(ans,z[i]-z1[i])
print ans

Solution (Python):
import sys
sys.setrecursionlimit(100000)
import heapq
n=int(input())
data=[]
a=list(map(int,input().split()))
amax=0
for i in range(n):
    heapq.heappush(data,a[i])
    amax+=a[i]
ansdata=[amax]
for i in range(n,2*n):
    heapq.heappush(data,a[i])
    amax+=a[i]
    amax-=heapq.heappop(data)
    ansdata.append(amax)
data=[]
bmin=0
for i in range(2*n,3*n):
    heapq.heappush(data,-a[i])
    bmin+=a[i]
ansdata[-1]-=bmin
for i in range(n):
    t=i
    i=2*n-1-i
    heapq.heappush(data,-a[i])
    bmin+=a[i]
    bmin+=heapq.heappop(data)
    ansdata[-t-2]-=bmin

print(max(ansdata))

Solution (Python):
import heapq

n=int(input())
*a,=map(int,input().split())
inf=float("inf")

pos=n
q,r=[],[]
u,d=[-inf]*(3*n),[inf]*(3*n)

for i in range(n):
    heapq.heappush(q,a[i])
    u[i]=u[i-1] if i else 0
    u[i]+=a[i]

for i in range(n,2*n):
    heapq.heappush(q,a[i])
    b=heapq.heappop(q)
    u[i]=u[i-1]+a[i]-b

for i in range(2*n,3*n)[::-1]:
    heapq.heappush(r,-a[i])
    d[i]=d[i+1] if i!=3*n-1 else 0
    d[i]+=a[i]

for i in range(n,2*n)[::-1]:
    heapq.heappush(r,-a[i])
    b=heapq.heappop(r)
    d[i]=d[i+1]+a[i]+b

ans=-inf
for i in range(n-1,2*n):
    ans=max(ans,u[i]-d[i+1])

print(ans)

Solution (Python):
import heapq

n=int(input())
*a,=map(int,input().split())
inf=float("inf")

pos=n
q,r=[],[]
u,d=[-inf]*(3*n),[inf]*(3*n)

for i in range(n):
    heapq.heappush(q,a[i])
    u[i]=u[i-1] if i else 0
    u[i]+=a[i]

for i in range(n,2*n):
    heapq.heappush(q,a[i])
    b=heapq.heappop(q)
    u[i]=u[i-1]+a[i]-b

for i in range(2*n,3*n)[::-1]:
    heapq.heappush(r,-a[i])
    d[i]=d[i+1] if i!=3*n-1 else 0
    d[i]+=a[i]

for i in range(n,2*n)[::-1]:
    heapq.heappush(r,-a[i])
    b=heapq.heappop(r)
    d[i]=d[i+1]+a[i]+b

ans=-inf
for i in range(n-1,2*n):
    ans=max(ans,u[i]-d[i+1])

print(ans)

Solution (Python):
import heapq
import copy
N=int(input())
A=list(map(int,input().split()))
ca=copy.deepcopy(A)
fsl=[0 for i in range(N+1)]
f=ca[:N]
heapq.heapify(f)
fs=sum(f)
fsl[0]=fs
for i in range(N,2*N):
    heapq.heappush(f,A[i])
    fs=fs+A[i]-heapq.heappop(f)
    fsl[i-N+1]=fs
lsl=[0 for i in range(N+1)]
l=list(map(lambda x:-x,ca[2*N:]))
heapq.heapify(l)
ls=sum(l)
lsl[-1]=ls
for i in range(N,2*N):
    heapq.heappush(l,-A[3*N-i-1])
    ls=ls-A[3*N-i-1]-heapq.heappop(l)
    lsl[2*N-i-1]=ls
ans=-10**20
for i in range(N+1):
  ans=max(ans,fsl[i]+lsl[i])
print(ans)

Solution (Python):

from heapq import heappush,heappushpop,heapify

n = int(input())
a = [int(x) for x in input().split()]

q = []
s = 0
for i in range(n):
    heappush(q, a[i])
    s += a[i]
left = [s]
for k in range(n):
    x = heappushpop(q, a[n+k])
    s = s - x + a[n+k]
    left.append(s)

q = []
s = 0
for i in range(n):
    heappush(q, -1*a[3*n-1-i])
    s += a[3*n-1-i]
right = [0 for _ in range(n+1)]
right[n] = s
for k in range(n):
    x = heappushpop(q, -1*a[2*n-1-k])
    s = s - (-1*x) + a[2*n-1-k]
    right[n-1-k] = s

m = None
for k in range(n+1):
    if m is None:
        m = left[k] - right[k]
    else:
        m = max(m, left[k]-right[k])

print(m)

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

import heapq

front = [a[i] for i in range(N)]
heapq.heapify(front)
middle = list(a[N:2*N])
back = list(a[2*N:3*N])

sumfront = [0 for _ in range(N+1)]
sumfront[0] = sum(list(a[0:N]))
for i in range(1,N+1):
    sumfront[i] = sumfront[i-1] + middle[i-1] \
    - heapq.heappushpop(front,middle[i-1]) 

minusmiddle = [-1*middle[i] for i in range(N)]
minusback = [-1*a[i+2*N] for i in range(N)]
heapq.heapify(minusback)
sumback = [0 for _ in range(N+1)]
sumback[N] = -1*sum(list(a[2*N:3*N]))
for i in range(N-1,-1,-1):
    sumback[i] = sumback[i+1] + minusmiddle[i] - heapq.heappushpop(minusback,minusmiddle[i])

ans = -1*float('inf')
for i in range(N+1):
    ans = max(ans,sumfront[i] + sumback[i])
print(ans)

Solution (Python):
import heapq


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

    sum_max, sum_min = [0] * (n+1), [0] * (n+1)
    mx_pq, mn_pq = [], []

    for i in range(n):
        heapq.heappush(mx_pq, a[i])
        heapq.heappush(mn_pq, -a[3*n-i-1])

    sum_max[0], sum_min[n] = sum(mx_pq), -sum(mn_pq)

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

        if mn_pq[0] < -a[2*n-i]:
            sum_min[n-i] = sum_min[n-i+1] + a[2*n-i] + heapq.heappop(mn_pq)
            heapq.heappush(mn_pq, -a[2*n-i])
        else:
            sum_min[n-i] = sum_min[n-i+1]

    ans = -10 ** 16
    for i in range(n+1):
        ans = max(ans, sum_max[i]-sum_min[i])

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappushpop

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

l_list = sorted(A[:N])
l_sum = [sum(l_list)]
for a in A[N:2 * N]:
    l_sum.append(l_sum[-1] - heappushpop(l_list, a) + a)

r_list = sorted(-x for x in A[-N:])
r_sum = [sum(r_list)]
for a in reversed(A[N:2 * N]):
    r_sum.append(r_sum[-1] - heappushpop(r_list, -a) - a)

ans = -(10 ** 15)
for l, r in zip(l_sum, r_sum[::-1]):
    ans = max(ans, l + r)
print(ans)

Solution (Python):
ai = lambda: list(map(int,input().split()))

n = int(input())
a = ai()

big = sum(a[:n])
small = sum(a[2*n:])

import heapq
af = a[:n]
heapq.heapify(af)
ar = [-i for i in a[2*n:]]
heapq.heapify(ar)

ans = [[0,0] for _ in range(n+1)]
ans[0][0] = big
ans[-1][1] = small

for k in range(n):
    if af[0] < a[n+k]:
        b = heapq.heapreplace(af, a[n+k])
        big += a[n+k] - b
    ans[k+1][0] = big

for k in range(n):
    if -ar[0] > a[-n-k-1]:
        s = heapq.heapreplace(ar, -a[-n-k-1])
        small += a[-n-k-1] + s
    ans[-k-2][1] = small

print(max(i-j for i,j in ans))

Solution (Python):
import heapq
import bisect

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

left = a[0:n//3]
right = list(-i for i in a[2*n//3:])

leftsum = [0 for i in range(n//3+1)]
rightsum = [0 for i in range(n//3+1)]

heapq.heapify(left)
leftsum[0] = sum(left)
for i in range(n//3):
    k = i + n//3
    heapq.heappush(left,a[k])
    temp = heapq.heappop(left)
    leftsum[i+1] = leftsum[i]+a[k]-temp

heapq.heapify(right)
rightsum[-1] = -sum(right)
for i in range(n//3)[::-1]:
    k = i + n//3
    heapq.heappush(right,-a[k])
    temp = -heapq.heappop(right)
    rightsum[i] = rightsum[i+1] - temp + a[k]




mxm = -sum(a)
for i in range(n//3+1):
    if leftsum[i]-rightsum[i] > mxm:
        mxm = leftsum[i]-rightsum[i]
print(mxm)

Solution (Python):
import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [long(input_raw[0])]
    A_list = []
    input_raw = read_func().strip().split()
    for i in range(3* N):
        A_list.append(long(input_raw[i]))

    AL_list = A_list[:N]
    L_sum = [0 for i in range(N + 1)]
    L_sum[0] = sum(AL_list)
    heapq.heapify(AL_list)
    for i in range(N, 2 * N):
        if AL_list[0] < A_list[i]:
            heapq.heappush(AL_list, A_list[i])
            min_L = heapq.heappop(AL_list)
            L_sum[i + 1- N] = L_sum[i - N] - min_L + A_list[i]
        else:
            L_sum[i + 1- N] = L_sum[i - N]

    AR_list = [-A_list[i] for i in range(2 * N, 3 * N)]
    R_sum = [0 for i in range(N + 1)]
    R_sum[N] = sum(AR_list)
    heapq.heapify(AR_list)
    for i in range(2 * N - 1, N - 1, -1):
        if AR_list[0] < -A_list[i]:
            heapq.heappush(AR_list, -A_list[i])
            min_R = heapq.heappop(AR_list)
            R_sum[i - N] = R_sum[i - N + 1] - min_R + (-A_list[i])
        else:
            R_sum[i - N] = R_sum[i - N + 1]

    max_score = -long(sys.maxint * sys.maxint)
    for i in range(N + 1):
        max_score = max(max_score, L_sum[i] + R_sum[i])






















    print max_score


if __name__ == '__main__':
    main()

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

INF = 1 << 60

N = read()
A = reads()

maxf = [-1] * (3*N+1)
minl = [INF] * (3*N+1)

hp = A[:N]; heapify(hp)
maxf[N] = sum(hp)
for i in range(N, 2*N):
  removed = heappushpop(hp, A[i])
  maxf[i+1] = maxf[i] + A[i] - removed

hp = [-x for x in A[2*N:]]; heapify(hp)
minl[2*N] = -sum(hp)
for i in range(2*N-1, N-1, -1):
  removed = -heappushpop(hp, -A[i])
  minl[i] = minl[i+1] + A[i] - removed

ans = max(maxf[i] - minl[i] for i in range(N, 2*N+1))
print(ans)

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

red=[0 for i in range(N+1)]
blue=[0 for i in range(N+1)]
r=list(a[:N])
b=list([-i for i in a[2*N:]])
heapq.heapify(r)
heapq.heapify(b)
red[0]=sum(a[:N])
for i in range(N):
    k=i+N
    tmp1=a[k]
    heapq.heappush(r,a[k])
    tmp2=heapq.heappop(r)
    red[i+1]=red[i]-tmp2+tmp1
blue[-1]=sum(a[2*N:])
for i in range(N)[::-1]:
    k=i+N
    tmp1=a[k]
    heapq.heappush(b,-a[k])
    tmp2=-heapq.heappop(b)
    blue[i]=blue[i+1]-tmp2+tmp1
ans=[red[i]-blue[i] for i in range(N+1)]
print(max(ans))

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]

from heapq import *

L = [0] * (N + 1)

t = 0
h = []
for a in A[:N]:
    heappush(h, a)
    t += a

L[0] = t
for i in range(N):
    x = A[N + i]
    heappush(h, x)
    y = heappop(h)
    t += x - y
    L[i + 1] = t

R = [0] * (N + 1)

t = 0
h = []
for a in A[N * 2:]:
    heappush(h, -a)
    t -= a

R[N] = t
for i in range(N - 1, -1, -1):
    x = A[N + i]
    heappush(h, -x)
    y = heappop(h)
    t += -x - y
    R[i] = t

result = max(l + r for l, r in zip(L, R))

print(result)

Solution (Python):
import heapq

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

zenhan = seq[:N]
kouhan = list(map(lambda x: -x, seq[2*N:])) 
heapq.heapify(zenhan)
heapq.heapify(kouhan)

zenhan_sum_max = [0 for i in range(N + 1)] 
kouhan_sum_min = [0 for i in range(N + 1)] 

zenhan_sum_max[0] = sum(seq[:N])
kouhan_sum_min[N] = sum(list(map(lambda x: -x, seq[2*N:])))
for i in range(N):
    new = seq[N + i]
    pop = heapq.heappushpop(zenhan, new)
    zenhan_sum_max[i + 1] = zenhan_sum_max[i] + new - pop

for i in range(N - 1, -1, -1):
    new = -seq[N + i]
    pop = heapq.heappushpop(kouhan, new)
    kouhan_sum_min[i] = kouhan_sum_min[i + 1] + new - pop

print(max([zenhan_sum_max[i] + kouhan_sum_min[i] for i in range(N + 1)]))

Solution (Python):
from heapq import heapify, heappushpop

n = int(input())
xs = [int(x) for x in input().split()]

xs1 = xs[:n]
heapify(xs1)
r1 = [sum(xs1)]
for x in xs[n:2*n]:
    r1.append(r1[-1] + x - heappushpop(xs1, x))

xs2 = [-x for x in xs[2*n:]]
heapify(xs2)
r2 = [sum(xs2)]
for x in reversed(xs[n:2*n]):
    r2.append(r2[-1] + (-x) - heappushpop(xs2, -x))

print(max(a+b for a,b in zip(r1, reversed(r2))))

Solution (Python):
import heapq

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

first_q = a_li[0:N] 
last_q = []			

first_ans = sum(first_q)
last_ans = 0

for i in range(2*N,3*N):	
	last_q.append([-a_li[i],a_li[i]])
	last_ans += a_li[i]
	

heapq.heapify(first_q)
heapq.heapify(last_q)
 
first_ans_li = []
last_ans_li = []

first_ans_li.append(first_ans)
last_ans_li.append(last_ans)


for k in range(N,2*N): 
	pop = heapq.heappushpop(first_q,a_li[k])	
	push = a_li[k]
	first_ans = first_ans + push - pop
	first_ans_li.append(first_ans)
	

for k in range(2*N-1,N-1,-1): 
	pop = heapq.heappushpop(last_q,[-a_li[k],a_li[k]])[1] 
	push = a_li[k]
	last_ans = last_ans + push - pop
	last_ans_li.append(last_ans)

ans = -10**20
	
for i in range(0,N+1):
	ans_dush = first_ans_li[i] - last_ans_li[N-i]
	ans = max(ans,ans_dush)

print(ans)

Solution (Python):

import sys
from queue import PriorityQueue
try:
    from typing import List, Tuple, Dict
except ImportError:
    pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


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


left_queue = PriorityQueue()  

for i in range(N):
    item = (a[i], None)
    left_queue.put(item)


score = sum(a[:N])
left_scores = [score]

for i in range(N, 2*N):
    b, none = left_queue.get()
    if a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (a[i], None)
        dscore = a[i] - b
    left_queue.put(item)
    score += dscore
    left_scores.append(score)


right_queue = PriorityQueue()  

for i in range(2*N, 3*N):
    item = (-a[i], None)
    right_queue.put(item)


score = - sum(a[2*N:])
right_scores = [score]

for i in range(2*N-1, N-1, -1):
    b, none = right_queue.get()
    if -a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (-a[i], None)
        dscore = -a[i] - b
        
    right_queue.put(item)
    
    score += dscore
    right_scores.append(score)


scores = []
for i in range(N+1):
    scores.append(left_scores[i] + right_scores[N-i])

debug(scores)
print(max(scores))

Solution (Python):

import sys
from queue import PriorityQueue
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


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


left_queue = PriorityQueue()

for i in range(N):
    item = (a[i], None)
    left_queue.put(item)


score = sum(a[:N])
left_scores = [score]

for i in range(N, 2*N):
    b, none = left_queue.get()
    if a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (a[i], None)
        dscore = a[i] - b
    left_queue.put(item)
    score += dscore
    left_scores.append(score)


right_queue = PriorityQueue()

for i in range(2*N, 3*N):
    item = (-a[i], None)
    right_queue.put(item)


score = - sum(a[2*N:])
right_scores = [score]

for i in range(2*N-1, N-1, -1):
    b, none = right_queue.get()
    if -a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (-a[i], None)
        dscore = -a[i] - b
        
    right_queue.put(item)
    
    score += dscore
    right_scores.append(score)


scores = []
for i in range(N+1):
    scores.append(left_scores[i] + right_scores[N-i])

debug(scores)
print(max(scores))

Solution (Python):
import heapq
N = int(input())
A = [int(i) for i in input().split()]
posi=[]
posidata=[]
nega=[]
negadata=[]
for i in range(N):
    heapq.heappush(posi,A[i])
    heapq.heappush(nega,-A[3*N-1-i])
posisum = sum(posi)
negasum = sum(nega)
posidata.append(posisum)
negadata.append(negasum)
for i in range(N):
    heapq.heappush(posi,A[N+i])
    a = heapq.heappop(posi)
    posisum += A[N+i]-a
    posidata.append(posisum)
    heapq.heappush(nega,-A[2*N-1-i])
    b = heapq.heappop(nega)
    negasum += -A[2*N-1-i]-b
    negadata.append(negasum)
print(max(posidata[i]+negadata[-1-i] for i in range(N+1)))

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

max_result = -1000000

big_a = a[:N]
big_sum = [sum(big_a)]
heapq.heapify(big_a)
for i in range(N):
  heapq.heappush(big_a, a[N+i])
  p = heapq.heappop(big_a)
  big_sum.append(big_sum[-1] + a[N+i] - p)

small_a = [-i for i in a[-N:]]
small_sum = [sum(small_a)]
heapq.heapify(small_a)
for i in range(N):
  heapq.heappush(small_a, -a[-N-i-1])
  p = heapq.heappop(small_a)
  small_sum.append(small_sum[-1] - a[-N-i-1] - p)

max_result = -float('inf')

for m,s in zip(big_sum, small_sum[::-1]):
  max_result = max(m + s, max_result)

print(max_result)

Solution (Python):
import heapq

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

first = a[:n]
second = a[n : 2 * n]
third = a[2 * n:]

s_minus = [-i for i in second]
t_minus = [-i for i in third]

former = [sum(first)]
latter = [sum(t_minus)]

heapq.heapify(first)
for k in range(n):
	heapq.heappush(first, second[k])
	former.append(former[-1] + second[k] - heapq.heappop(first))

heapq.heapify(t_minus)
for k in range(n):
	heapq.heappush(t_minus, s_minus[-(k + 1)])
	latter.append(latter[-1] + s_minus[-(k + 1)] - heapq.heappop(t_minus))

new_latter = [latter[-(i + 1)] for i in range(n + 1)]

ans = -5000000000000000000000000000000
for f, l in zip(former, new_latter):
	if f + l >= ans:
		ans = f + l

print(ans)

Solution (Python):
from heapq import *
def score(key):
    num = sum(key[:n])
    ans = [num]
    l = key[:n]
    heapify(l)

    for k in key[n:2 * n]:
        num -= heappushpop(l, k)
        num += k
        ans.append(num)
    return ans

n = int(input())
a = list(map(int, input().split()))
b = list(map(lambda x:-x,reversed(a)))

max_score = 0
le = score(a)
ri = reversed(score(b))
cou = map(lambda x,y:x+y, le, ri)
print (max(cou))

Solution (Python):
import heapq

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

s1 = sum(src[:N])
r1 = [s1]
q1 = src[:N]
heapq.heapify(q1)
for i in range(N):
    heapq.heappush(q1,src[N+i])
    p = heapq.heappop(q1)
    r1.append(r1[-1] + src[N+i] - p)

s2 = -sum(src[-N:])
r2 = [s2]
q2 = [-a for a in src[-N:]]
heapq.heapify(q2)
for i in range(N):
    heapq.heappush(q2,-src[-N-i-1])
    p = heapq.heappop(q2)
    r2.append(r2[-1] - src[-N-i-1] - p)

ans = -float('inf')
for a,b in zip(r1,r2[::-1]):
    ans = max(ans, a+b)
print(ans)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
import heapq
q=a[:n]
rq=[-a[i] for i in range(2*n,3*n)[::-1]]
dd=sum(q)
rdd=sum(rq)
d=[dd]
rd=[rdd]

heapq.heapify(q)
heapq.heapify(rq)

for i in range(n,2*n):
 heapq.heappush(q, a[i])
 x=heapq.heappop(q)
 dd=dd+a[i]-x
 d.append(dd)
for i in range(n,2*n)[::-1]:
 heapq.heappush(rq, -a[i])
 x=heapq.heappop(rq)
 rdd=rdd-a[i]-x
 rd.append(rdd)
c=-float("inf")
for i in range(len(d)):
  c=max(c,d[i]+rd[len(rd)-1-i])
print(c)

Solution (Python):

def inpl(): return list(map(int, input().split()))
from heapq import heapify, heapreplace 

N = int(input())
A = inpl()
L = A[:N]
M = A[N:2*N]
R = [-a for a in A[2*N:]]
ans = sum(L) + sum(R)
heapify(L)
heapify(R)


i = 0
j = N+1

S = [0]*(N+1)

s = 0
for i, m in enumerate(M):
    if m > L[0]:
        s += m - heapreplace(L, m)
    S[i+1] += s

s = 0
for i, m in enumerate(M[::-1]):
    if m < -R[0]:
        s += -m - heapreplace(R, -m)
    S[-i-2] += s

ans += max(S)
print(ans)

Solution (Python):


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

'''
方針
N/3から2N/3まで動かして、その時の差分の最大値を返す
前半では、要素を追加して、最小値を取り出す
後半では、要素を
'''


import heapq
q = [] 
heapq.heappush(q, 1) 


heapq.heappush(q, 2) 


heapq.heappush(q, 0) 

q1 = []
sum_q1 = 0
sum_q1s = []

for i in range(0,N,1):
    heapq.heappush(q1, As[i])
    sum_q1 += As[i]
sum_q1s.append(sum_q1)
for i in range(N,2*N,1):
    heapq.heappush(q1, As[i])
    pop_q1 = heapq.heappop(q1)
    sum_q1 = sum_q1 - pop_q1 + As[i]
    sum_q1s.append(sum_q1)

q2 = []
sum_q2 = 0
sum_q2s = []

for i in range(2*N,3*N,1):
    heapq.heappush(q2, -As[i])
    sum_q2 += -As[i]
sum_q2s.append(sum_q2)
for i in range(2*N-1,N-1,-1):
    heapq.heappush(q2, -As[i])
    pop_q2 = heapq.heappop(q2)
    sum_q2 = sum_q2 - pop_q2 - As[i]
    sum_q2s.append(sum_q2)

max_value = -float('inf')
for i in range(0,N+1,1):
    max_value = max(max_value, sum_q1s[i] + sum_q2s[N-i])

print(max_value)

Solution (Python):

def inpl(): return list(map(int, input().split()))
from heapq import heapify, heappop, heappush
from copy import deepcopy

N = int(input())
A = inpl()

before = deepcopy(A[:N])
heapify(before)
middle = A[N:-N]
after = [-a for a in A[-N:]]
heapify(after)

sb = sum(A[:N])
sa = -sum(A[-N:])

SB = [sb]
SA = [sa]

for m in middle:
    b = heappop(before)
    if b < m:
        heappush(before, m)
        sb += m - b
    else:
        heappush(before, b)
    SB.append(sb)    

for m in middle[::-1]:
    m = -m
    a = heappop(after)
    if a < m:
        heappush(after, m)
        sa += m - a
    else:
        heappush(after, a)
    SA.append(sa) 

    
print(max([b+a for b, a in zip(SB, SA[::-1])]))

Solution (Python):

from heapq import heappush, heappushpop

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

pq1 = []
pq2 = []
for i in range(N):
    heappush(pq1, A[i])
    heappush(pq2, -A[-i - 1])

acc1 = [sum(pq1)] * (N + 1)     
acc2 = [sum(pq2)] * (N + 1)     
for (i, a) in enumerate(A[N:2 * N]):
    acc1[i + 1] = acc1[i] + a - heappushpop(pq1, a)
for (i, a) in enumerate(A[N:2 * N][::-1]):
    acc2[-i - 2] = acc2[-i - 1] + (-a) - heappushpop(pq2, -a)

ans = float('-inf')
for x, y in zip(acc1, acc2):
    ans = max(ans, x - (-y))

print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**9
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    b = []
    c = []
    for i in range(n):
        heapq.heappush(b, a[i])
        heapq.heappush(c, -a[i+n*2])
    sb = sum(b)
    sc = sum(c)
    ba = {}
    ba[n-1] = sb
    for i in range(n):
        t = heapq.heappop(b)
        if a[n+i] > t:
            sb -= t
            heapq.heappush(b, a[n+i])
            sb += a[n+i]
        else:
            heapq.heappush(b, t)
        ba[n+i] = sb

    ca = {}
    ca[n*2-1] = sc
    for i in range(n-1,-1,-1):
        t = heapq.heappop(c)
        if -a[n+i] > t:
            sc -= t
            heapq.heappush(c, -a[n+i])
            sc -= a[n+i]
        else:
            heapq.heappush(c, t)
        ca[n+i-1] = sc


    r = -inf
    for k in ba.keys():
        tr = ba[k] + ca[k]
        if tr > r:
            r = tr

    return r



print(main())

Solution (Python):
import sys, heapq

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = na()

ln = a[0:n]
rn = [-x for x in a[2*n: 3*n]]
heapq.heapify(ln)
heapq.heapify(rn)
ls = sum(ln)
rs = sum(rn)

lb = [ls]
rb = [rs]
for i in range(1, n+1):
    heapq.heappush(ln, a[n-1+i])
    vl = heapq.heappop(ln)
    ls = ls - vl + a[n-1+i]
    lb.append(ls)

    heapq.heappush(rn, -a[2*n-i])
    vr = heapq.heappop(rn)
    rs = rs - vr - a[2*n-i]
    rb.append(rs)

ans = -float('inf')
for i in range(n+1):
    ans = max(ans, lb[i] + rb[n-i])

print (ans)

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
n = int(input())
xs = list(map(int, input().split()))
head = [(x, x) for x in xs[:n]]
heapq.heapify(head)
body = xs[n:-n]
tail = [(-x, x) for x in xs[-n:]]
heapq.heapify(tail)

def f(heap, body, sign, initial):
    answer = [initial]
    acc = initial
    for b in body:
        heapq.heappush(heap, (sign*b, b))
        _, x = heapq.heappop(heap)
        acc = acc + b - x
        answer.append(acc)
    return answer
 
print(max(x - y for x, y in zip(
    f(head, body, 1, sum(xs[:n])),
    f(tail, body[::-1], -1, sum(xs[-n:]))[::-1])))

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

inf = 1<<60

def solve():
    n = int(input())
    a = [int(i) for i in input().split()]

    ps = [sum(a[:n])]
    minhp = a[:n]
    heapify(minhp)

    for i in range(n):
        heappush(minhp, a[n + i])
        x = heappop(minhp)
        ps.append(ps[-1] + a[n + i] - x)

    ss = [sum(a[2*n:])]
    maxhp = [-ai for ai in a[2*n:]]
    heapify(maxhp)

    for i in range(n):
        heappush(maxhp, -a[2*n - 1 - i])
        x = -heappop(maxhp)
        ss.append(ss[-1] + a[2*n - 1 - i] - x)

    ans = -inf

    for i in range(n + 1):
        ans = max(ans, ps[i] - ss[n - i])

    print(ans)

if __name__ == '__main__':  
    solve()

Solution (Python):

import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    a = ILI()
    return (N, a)


def solve(N, a):
    a_lef = a[0: N]
    a_rig = [-i for i in a[2 * N: 3 * N]]
    heapq.heapify(a_lef)
    heapq.heapify(a_rig)
    sum_lef = sum(a_lef)
    sum_rig = sum(a_rig)
    l_sum_lef = [sum_lef]
    l_sum_rig = [sum_rig]
    
    for i in range(1, N + 1):
        heapq.heappush(a_lef, a[N - 1 + i])
        lef_pop = heapq.heappop(a_lef)
        sum_lef += a[N - 1 + i] - lef_pop
        l_sum_lef.append(sum_lef)
        
        heapq.heappush(a_rig, -a[2 * N - i])
        rig_pop = heapq.heappop(a_rig)
        sum_rig += -a[2 * N - i] - rig_pop
        l_sum_rig.append(sum_rig)

    ans = -INF

    for i in range(N + 1):
        num_dif = l_sum_lef[i] + l_sum_rig[N - i]
        ans = max(ans, num_dif)

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()