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 = list(map(int, input().split()))

n1 = a[:N]

heapq.heapify(n1)

sum1 = sum(n1)

arr1 = [sum1]

for i in range(N, 2*N):
    heapq.heappush(n1, a[i])
    sum1 += a[i]
    sum1 -= heapq.heappop(n1)
    arr1.append(sum1)

n2 = [-i for i in a[2*N:]]

heapq.heapify(n2)
sum2 = sum(n2)

arr2 = [sum2]

for i in range(1, N+1):
    heapq.heappush(n2, -a[2*N-i])
    sum2 += -a[2*N-i]
    sum2 -= heapq.heappop(n2)
    arr2.append(sum2)

ans = -10**17

for i, j in zip(arr1, reversed(arr2)):
    ans = max(ans, i+j)

print(ans)

Solution (Python):


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

from heapq import *

pq1 = a[:n]
heapify(pq1)
s = sum(pq1)
score1 = [s]
for i in range(n):
    c=heappushpop(pq1, a[n+i])
    s += a[n+i] - c
    score1.append(s)

pq2 = [-i for i in a[2*n:]]
heapify(pq2)
s = sum(pq2)
score2 = [s]
for i in range(1,n+1):
    c=heappushpop(pq2, -a[2*n-i])
    s += -a[2*n-i] - c
    score2.append(s)



ans = -10**17
for i,j in zip(score1,reversed(score2)):
    ans = max(ans, i+j)

print(ans)

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

pq1 = a[:N]
pq2 = [-x for x in a[2 * N:]]

heapify(pq1)
heapify(pq2)

s1 = sum(pq1)
s2 = sum(pq2)

ans1 = [s1]
ans2 = [s2]

for k in range(N, 2 * N):
    heappush(pq1, a[k])
    x = heappop(pq1)
    s1 += a[k] - x
    ans1.append(s1)
    
    heappush(pq2, -a[3 * N - k - 1])
    x = heappop(pq2)
    s2 += -a[3 * N - k - 1] - x
    ans2.append(s2)
    
print(max(ans1[i] + ans2[-i - 1] for i in range(len(ans1))))

Solution (Python):

import sys
import heapq


inf = float("inf")

def solve(N: int, a: "List[int]"):
    L = a[:N]
    R = [-x for x in a[2*N:]]
    heapq.heapify(L)
    heapq.heapify(R)
    M = a[N:2*N]
    sumL = [0 for _ in range(N+1)] 
    sumR = [0 for _ in range(N+1)] 

    sumL[0] = sum(L)
    sumR[N] = sum(R)

    for i in range(N):
        heapq.heappush(L, M[i])
        l = heapq.heappop(L)
        diff = M[i] - l
        sumL[i+1] = sumL[i] + diff
    
    for i in range(N-1, -1, -1):
        heapq.heappush(R, -M[i])
        r = heapq.heappop(R)
        diff = -M[i] - r
        sumR[i] = sumR[i+1] + diff
    
    res = max(suml + sumr for suml, sumr in zip(sumL, sumR))
    print(res)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [ int(next(tokens)) for _ in range(3*N) ]  
    solve(N, a)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import heapq
from collections import deque


inf = float("inf")

def solve(N: int, a: "List[int]"):
    L = a[:N]
    R = [-x for x in a[2*N:]]
    heapq.heapify(L)
    heapq.heapify(R)
    M = a[N:2*N]
    sumL = [0 for _ in range(N+1)] 
    sumR = [0 for _ in range(N+1)] 

    sumL[0] = sum(L)
    sumR[N] = sum(R)

    for i in range(N):
        l = heapq.heappop(L)
        diff = M[i] - l
        if diff > 0:
            sumL[i+1] = sumL[i] + diff
            heapq.heappush(L, M[i])
        else:
            sumL[i+1] = sumL[i]
            heapq.heappush(L, l)
    
    for i in range(N-1, -1, -1):
        r = heapq.heappop(R)
        diff = -M[i] - r
        if diff > 0:
            sumR[i] = sumR[i+1] + diff
            heapq.heappush(R, -M[i])
        else:
            sumR[i] = sumR[i+1]
            heapq.heappush(R, r)
    
    res = -inf
    for suml, sumr in zip(sumL, sumR):
        res = max(res, suml + sumr)
    print(res)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [ int(next(tokens)) for _ in range(3*N) ]  
    solve(N, a)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
n=int(input())
a=[int(i) for i in input().split()]
f=a[:n]
l=[-i for i in a[2*n:]]
heapq.heapify(f)
heapq.heapify(l)
fs=[0]*(n+1)
ls=[0]*(n+1)
fs[0]=sum(f)
ls[n]=-sum(l)

for i in range(n):
    c=a[n+i]
    m=heapq.heappushpop(f,c)
    fs[i+1]=fs[i]+c-m

for i in range(n):
    c=a[2*n-1-i]
    m=heapq.heappushpop(l,-c)
    ls[n-i-1]=ls[n-i]+c+m

ans=fs[0]-ls[0]
for k in range(n+1):
    ans=max(ans,fs[k]-ls[k])
print(ans)

Solution (Python):
import heapq
import sys
from collections import deque
input=sys.stdin.readline

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

f=a[:n]
l=[-i for i in a[2*n:]]
heapq.heapify(f)
heapq.heapify(l)
fs=[0]*(n+1)
ls=[0]*(n+1)
fs[0]=sum(f)
ls[n]=-sum(l)

for i in range(n):
    c=a[n+i]
    m=heapq.heappushpop(f,c)
    fs[i+1]=fs[i]+c-m


for i in range(n):
    c=a[2*n-1-i]
    m=heapq.heappushpop(l,-c)
    ls[n-i-1]=ls[n-i]+c+m



ans=fs[0]-ls[0]
for k in range(n+1):
    ans=max(ans,fs[k]-ls[k])
print(ans)

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

def calc(front_sum, back_sum):
    heapq.heapify(a_front)
    heapq.heapify(a_back)
    front_sums = [front_sum]
    back_sums = [back_sum]
    for i in a_center:
        front_sum += i - heapq.heappushpop(a_front, i)
        front_sums += [front_sum]
    a_center.reverse()
    for i in a_center:
        back_sum += i + heapq.heappushpop(a_back, -i)
        back_sums += [back_sum]
    return max([front_sums[i] - back_sums[-i-1] for i in range(n+1)])



if __name__ == "__main__":
    n = int(input())
    a = [int(i) for i in input().split()]
    k = 0
    a_front = []
    a_center = []
    a_back = []
    front_sum = 0
    back_sum = 0

    for i in a:
        k += 1
        if k <= n:
            a_front += [i]
            front_sum += i
        elif k <= 2 * n:
            a_center += [i]
        else:
            a_back += [-i]
            back_sum += i

    print(calc(front_sum, back_sum))

Solution (Python):
import heapq

def calc(front_sum, back_sum):
    heapq.heapify(a_front)
    heapq.heapify(a_back)
    front_sums = [front_sum]
    back_sums = [back_sum]
    for i in a_center:
        front_sum += i - heapq.heappushpop(a_front, i)
        front_sums += [front_sum]
    a_center.reverse()
    for i in a_center:
        back_sum += i + heapq.heappushpop(a_back, -i)
        back_sums += [back_sum]
    return max([front_sums[i] - back_sums[-i-1] for i in range(n+1)])



if __name__ == "__main__":
    n = int(input())
    a = [int(i) for i in input().split()]
    k = 0
    a_front = []
    a_center = []
    a_back = []
    front_sum = 0
    back_sum = 0

    for i in a:
        k += 1
        if k <= n:
            a_front += [i]
            front_sum += i
        elif k <= 2 * n:
            a_center += [i]
        else:
            a_back += [-i]
            back_sum += i

    print(calc(front_sum, back_sum))

Solution (Python):
import heapq

def calc(front_sum, back_sum):
    heapq.heapify(a_front)
    heapq.heapify(a_back)
    front_sums = [front_sum]
    back_sums = [back_sum]
    for i in range(n):
        front_sum += a_center[i] - heapq.heappushpop(a_front, a_center[i])
        front_sums += [front_sum]
        back_sum += a_center[-i - 1] + heapq.heappushpop(a_back, -a_center[-i - 1])
        back_sums += [back_sum]
    return max([front_sums[i] - back_sums[-i-1] for i in range(n+1)])



if __name__ == "__main__":
    n = int(input())
    a = [int(i) for i in input().split()]
    k = 0
    a_front = []
    a_center = []
    a_back = []
    front_sum = 0
    back_sum = 0

    for i in a:
        k += 1
        if k <= n:
            a_front += [i]
            front_sum += i
        elif k <= 2 * n:
            a_center += [i]
        else:
            a_back += [-i]
            back_sum += i

    print(calc(front_sum, back_sum))

Solution (Python):
import heapq
n = int(input())
a = [int(i) for i in input().split()]
k = 0
a_front = []
a_center = []
a_back = []
front_sum = 0
back_sum = 0

for i in a:
    k += 1
    if k <= n:
        a_front += [i]
        front_sum += i
    elif k <= 2 * n:
        a_center += [i]
    else:
        a_back += [-i]
        back_sum += i

heapq.heapify(a_front)
heapq.heapify(a_back)

front_sums = [front_sum]
back_sums = [back_sum]

for i in range(n):
        front_sum += a_center[i] - heapq.heappushpop(a_front, a_center[i])
        front_sums += [front_sum]
        back_sum += a_center[-i-1] + heapq.heappushpop(a_back, -a_center[-i-1])
        back_sums += [back_sum]

print(max([front_sums[i] - back_sums[-i-1] for i in range(n+1)]))

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):
from heapq import heapify, heappushpop

N = int(input())
*A, = map(int, input().split())
INF = 10**16
first = A[:N]
heapify(first)
second = [-a for a in A[2*N:]]
heapify(second)
f = [0]*(N+1)
s = [0]*(N+1)
f[0] = sum(first)
s[N] = - sum(second)
for k in range(1, N+1):
    a = heappushpop(first, A[N-1+k])
    f[k] = f[k-1] + A[N-1+k] - a
for k in range(N-1, -1, -1):
    a = heappushpop(second, -A[N+k])
    s[k] = s[k+1] + A[N+k] + a
ans = -INF
for k in range(N+1):
    ans = max(ans, f[k] - s[k])
print(ans)

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

Solution (Python):
import heapq

N = int(input())
A = list(map(int, input().split()))
n1 = A[:N]
s1 = [sum(n1)]
heapq.heapify(n1)
for i in range(N):
    heapq.heappush(n1,A[N+i])
    p = heapq.heappop(n1)
    s1.append(s1[-1]-p+A[N+i])

n3 = [-a for a in A[-N:]]
s3 = [(sum(n3))]
heapq.heapify(n3)
for i in range(N):
    heapq.heappush(n3,-A[-N-i-1])
    p = heapq.heappop(n3)
    s3.append(s3[-1]-p-A[-N-i-1])
M = -10**15

for i,j in zip(s1,s3[::-1]):
    
    M = max(M,i+j)

print(M)

Solution (Python):
import heapq

N = int(input())
A = list(map(int, input().split()))
n1 = A[:N]
s1 = [sum(n1)]
heapq.heapify(n1)
for i in range(N):
    heapq.heappush(n1,A[N+i])
    p = heapq.heappop(n1)
    s1.append(s1[-1]-p+A[N+i])

s3 = [-(sum(A[-N:]))]
n3 = [-a for a in A[-N:]]
heapq.heapify(n3)
for i in range(N):
    heapq.heappush(n3,-A[-N-i-1])
    p = heapq.heappop(n3)
    s3.append(s3[-1]-p-A[-N-i-1])
M = -10**15

for i,j in zip(s1,s3[::-1]):
    
    M = max(M,i+j)

print(M)

Solution (Python):
n=int(input())
a_list=list(map(int,input().split()))
import heapq
pre=a_list[0:n]
heapq.heapify(pre)
pre_list=[sum(a_list[0:n])]
for i in range(n):
    heapq.heappush(pre,a_list[i+n])
    pre_list.append(pre_list[-1]+a_list[i+n]-heapq.heappop(pre))
b_list=[]
for i in range(2*n,3*n):
    b_list.append(-a_list[i])
post=b_list
heapq.heapify(post)
post_list=[sum(b_list)]
for i in range(n):
    heapq.heappush(post,-a_list[2*n-1-i])
    post_list.append(post_list[-1]-a_list[2*n-1-i]-heapq.heappop(post))
ans=-10**16
for i in range(n+1):
    Max=pre_list[i]+post_list[n-i]
    ans=max(ans,Max)
print(ans)

Solution (Python):
import heapq
import numpy as np

n = int(input())
a = list(map(int, input().split()))
s_front = [0] * (n + 1)
s_back = [0] * (n + 1)

a_front = a[:n]
heapq.heapify(a_front)
s_front[0] = sum(a_front)
for k in range(n):
    heapq.heappush(a_front, a[n + k])
    b = heapq.heappop(a_front)
    s_front[k + 1] = s_front[k] + a[n + k] - b

a_back = [(-x, x) for x in a[2 * n:]]
heapq.heapify(a_back)
s_back[0] = sum([x[1] for x in a_back])
for k in range(n):
    heapq.heappush(a_back, (-1 * a[2 * n - k - 1], a[2 * n - k - 1]))
    b = heapq.heappop(a_back)[1]
    s_back[k + 1] = s_back[k] + a[2 * n - k - 1] - b

s_front = np.array(s_front)
s_back = np.array(s_back[::-1])
print(max(s_front - s_back))

Solution (Python):
from heapq import heappop,heappush
N=int(input())
A=list(map(int,input().split()))
X=[]
Y=[]
Xnow=sum(A[0:N])
Ynow=-1*sum(A[2*N:3*N])
ansX=[Xnow]
ansY=[Ynow]
for i in range(N):
    heappush(X,A[i])
    heappush(Y,-1*A[i+2*N])
for i in range(N):
    a=A[N+i]
    Xnow+=a
    heappush(X,a)
    a=heappop(X)
    Xnow-=a
    ansX+=[Xnow]
    
    a=-1*A[2*N-1-i]
    Ynow+=a
    heappush(Y,a)
    a=heappop(Y)
    Ynow-=a
    ansY+=[Ynow]

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

Solution (Python):
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n = int(input())
a = list(map(int,input().split()))
left = a[:n]
suml = sum(left)
right = [-a[i] for i in range(3*n-1,2*n-1,-1)]
sumr = sum(right)
Suml = [suml]
Sumr = [sumr]
heapify(left)
heapify(right)


for i in range (n,2*n):
    heappush(left,a[i])
    x = heappop(left) 
    suml += a[i]-x
    Suml.append(suml)
for i in range(2*n-1,n-1,-1):
    heappush(right,-a[i])
    y = heappop(right)
    sumr += -a[i]-y
    Sumr.append(sumr)
ans = -inf
for i in range(n+1):
    ans = max(ans,Suml[i]+Sumr[n-i])
print(ans)

Solution (Python):
import numpy as np
from heapq import heapreplace, heapify
N=int(input())
A=np.array([int(a) for a in input().split(" ")])
lheap, rheap = list(A[:N]), list(-A[2*N:])
heapify(lheap)
heapify(rheap)
Lsum, Rsum = sum(lheap), sum(rheap)
left = [Lsum]
right = [Rsum]

for i in range(N):
    if A[N+i] > lheap[0]:
        Lsum += (A[N+i]-lheap[0])
        heapreplace(lheap, A[N+i])
    
    if -A[2*N-i-1] > rheap[0]:
        Rsum += (-A[2*N-i-1]-rheap[0])
        heapreplace(rheap, -A[2*N-i-1])
    
    left.append(Lsum)
    right.append(Rsum)
print(max(np.array(left)+np.array(right)[::-1]))

Solution (Python):
import heapq

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

h = []
goukei = 0
for a in a_list[:N]:
    goukei += a
    heapq.heappush(h,a)

k_left_goukei = [goukei]

for a in a_list[N:2*N]:
    goukei += a
    d = heapq.heappushpop(h,a)
    goukei -= d
    k_left_goukei.append(goukei)

h = []
goukei = 0
for a in a_list[::-1][:N]:
    goukei += a
    heapq.heappush(h,(-a,a))
    
k_right_goukei = [goukei]

for a in a_list[::-1][N:2*N]:
    goukei += a
    d = heapq.heappushpop(h,(-a,a))
    goukei -= d[1]
    k_right_goukei.append(goukei)

max_diff = None
for l, r in zip(k_left_goukei, k_right_goukei[::-1]):
    diff = l-r
    if max_diff == None:
        max_diff = diff
    else:
        max_diff = max(diff,max_diff)

print(max_diff)

Solution (Python):
import heapq

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def brute_force():
    N = int(input())
    L = list(map(int, input().split()))

    ans = -float('inf')
    for i in range(N, 2*N+1):
        tmp = sum(list(sorted(L[:i], reverse=True))[:N])\
            - sum(list(sorted(L[i:]))[:N])

        ans = max(ans, tmp)


def solve():
    N = int(input())
    L = list(map(int, input().split()))

    first = L[:N]
    heapq.heapify(first)
    first_sum = [0]*(N+1)
    tmp_first = sum(first)
    first_sum[0] = tmp_first
    for i in range(N, 2*N):
        first_ind = i-N+1
        if L[i] > first[0]:
            rem = heapq.heappop(first)
            heapq.heappush(first, L[i])
            tmp_first += L[i]-rem
        first_sum[first_ind] = tmp_first

    third = [-v for v in L[N*2:]]
    heapq.heapify(third)
    third_sum = [0]*(N+1)
    tmp_third = -sum(third)
    third_sum[-1] = tmp_third
    for i in reversed(range(N+1, 2*N+1)):
        third_ind = i-N-1
        if -L[i-1] > third[0]:
            rem = heapq.heappop(third)
            heapq.heappush(third, -L[i-1])
            tmp_third = tmp_third + rem+L[i-1]
        third_sum[third_ind] = tmp_third

    ans = max([f-l for f, l in zip(first_sum, third_sum)])
    print(ans)



solve()

Solution (Python):
import heapq

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def brute_force():
    N = int(input())
    L = list(map(int, input().split()))

    ans = -float('inf')
    for i in range(N, 2*N+1):
        tmp = sum(list(sorted(L[:i], reverse=True))[:N])\
            - sum(list(sorted(L[i:]))[:N])
        
        
        
        
        
        

        ans = max(ans, tmp)

    


def solve():
    N = int(input())
    L = list(map(int, input().split()))

    first = L[:N]
    heapq.heapify(first)
    first_sum = [0]*(N+1)
    tmp_first = sum(first)
    first_sum[0] = tmp_first
    
    for i in range(N, 2*N):
        first_ind = i-N+1
        
        if L[i] > first[0]:
            rem = heapq.heappop(first)
            heapq.heappush(first, L[i])
            tmp_first += L[i]-rem
            
            
        first_sum[first_ind] = tmp_first
        
        

    third = [-v for v in L[N*2:]]
    heapq.heapify(third)
    third_sum = [0]*(N+1)
    tmp_third = -sum(third)
    third_sum[-1] = tmp_third
    
    for i in reversed(range(N+1, 2*N+1)):
        
        third_ind = i-N-1
        
        
        if -L[i-1] > third[0]:
            rem = heapq.heappop(third)
            
            heapq.heappush(third, -L[i-1])
            tmp_third = tmp_third + rem+L[i-1]
        
        third_sum[third_ind] = tmp_third
        
    
    
    

    ans = max([f-l for f, l in zip(first_sum, third_sum)])
    print(ans)



solve()

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)
	for e in a[n:2*n+1]: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(l,a):
	q=a[:n];s=sum(q);heapify(q);l+=[s]
	for e in a[n:2*n]:s+=e-heappushpop(q,e);l+=[s]
from heapq import*;n,*a=map(int,open(0).read().split());l=[];f(l,a);f(l,[-i for i in a[::-1]]);m=len(l)//2;print(max(l[i]+l[-i-1]for i in range(m)))

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(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):
from heapq import*;n,*a=map(int,open(0).read().split());b,h,c,p=a[:n],heappushpop,[-i for i in a[n:][::-1]],heapify;s,d=sum(b),c[:n];t=sum(d);p(b);p(d);r,l=[s],[t]
for i in range(n,n*2):s+=a[i]-h(b,a[i]);t+=c[i]-h(d,c[i]);r+=[s];l+=[t]
print(max(map(sum,zip(r,l[::-1]))))

Solution (Python):
from heapq import*
n,*a=map(int,open(0).read().split())
b=a[:n]
c=[-i for i in a[n:][::-1]]
d=c[:n]
e=c[n:]
heapify(b)
heapify(d)
s=sum(b)
t=sum(d)
red=[s]
blue=[t]
for i in range(n,n*2):
    s+=a[i]-heappushpop(b,a[i])
    t+=c[i]-heappushpop(d,c[i])
    red+=[s]
    blue+=[t]
print(max(map(sum,zip(red,blue[::-1]))))

Solution (Python):
import heapq

n = int(input())
array = [int(i) for i in input().split()]
ans=-1e14
l_array = []
r_array = []
l_sum = [0]*(n+1)
r_sum = [0]*(n+1)


for i in range(n):
    heapq.heappush(l_array, array[i])
    heapq.heappush(r_array, (-array[3*n-1-i], array[3*n-1-i]))

l_sum[0] = sum(l_array)
r_sum[n] = sum([i[1] for i in r_array])

for i in range(n, 2*n):
    heapq.heappush(l_array, array[i])
    heapq.heappush(r_array, (-array[3*n-1-i], array[3*n-1-i]))
    l_min = heapq.heappop(l_array)
    r_max = heapq.heappop(r_array)[1]

    
    
    l_sum[i-n+1] = l_sum[i-n] - l_min + array[i]
    r_sum[2*n-1-i] = r_sum[2*n-i] - r_max + array[3*n-1-i]

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

print(ans)

Solution (Python):
import heapq

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

a1 = a[:n]
a2 = a[n:2*n]
a3 = [-x for x in a[2*n:]]

suma1 = [sum(a1)]
suma3 = [-sum(a3)]

heapq.heapify(a1)
heapq.heapify(a3)

for i in range(n):
    heapq.heappush(a1,a[n+i])
    heapq.heappush(a3,-a[2*n-1-i])
    suma1.append(suma1[-1]+a[n+i]-heapq.heappop(a1))
    suma3.append(suma3[-1]+a[2*n-1-i]+heapq.heappop(a3))

ans = suma1[0]-suma3[-1]
for i in range(n):
    ans = max(ans, suma1[i+1]-suma3[-2-i])
print(ans)

Solution (Python):
from heapq import heappush, heappop


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


ql = []
for a in A[:N]:
    heappush(ql, a)
L = [sum(A[:N])]
for a in A[N:(2 * N)]:
    heappush(ql, a)
    m = heappop(ql)
    L.append(L[-1] + a - m)


qr = []
for a in A[-N:]:
    heappush(qr, -a)
R = [sum(A[-N:])]
for a in A[-(N + 1):-(2 * N + 1):-1]:
    heappush(qr, -a)
    m = -heappop(qr)
    R.append(R[-1] + a - m)


ans = max(l - r for l, r in zip(L, R[::-1]))


print(ans)

Solution (Python):
import heapq
N = int(input())
A = list(map(int,input().split()))
L = []
R = []
for i in range(N):
  L.append(A[i])
for i in range(N):
  R.append(-A[3*N-i-1])
SUML = [0]*(N+1)
SUMR = [0]*(N+1)
S = sum(L)
T = sum(R)
SUML[0] = S
SUMR[0] = -T
heapq.heapify(L) 
heapq.heapify(R)
for i in range(N,2*N):
  a = heapq.heappushpop(L,A[i])
  S = S-a+A[i]
  SUML[i-N+1] = S
for j in range(N,2*N):
  b = heapq.heappushpop(R,-A[3*N-j-1])
  T = T-b-A[3*N-j-1]
  SUMR[j-N+1] = -T
ans = -float('inf')
for i in range(N+1):
  if SUML[i]-SUMR[N-i] >= ans:
    ans = SUML[i]-SUMR[N-i]
print(ans)

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





L = A[:N]
R = [-a for a in A[2*N:]]
L_sum, R_sum = sum(L), sum(R)
heapq.heapify(L)
heapq.heapify(R)

L_acc = [L_sum]
R_acc = [R_sum]
for i in range(N, 2*N):
    if L[0] >= A[i]:
        if i > N:
            L_acc.append(L_acc[-1])
        elif i == N:
            pass
    else:
        heapq.heappush(L, A[i])
        out = heapq.heappop(L)
        L_acc.append(L_acc[-1] - out + A[i])
    

for i in range(2*N-1, N-1, -1):
    if R[0] >= -A[i]:
        if i <= 2*N-1:
            R_acc.append(R_acc[-1])
        elif i == 2*N-1:
            pass
    else:
        heapq.heappush(R, -A[i])
        out = heapq.heappop(R)
        R_acc.append(R_acc[-1] - out - A[i])
    

ans = -float('inf')
for i in range(len(L_acc)):
     ans = max(ans, L_acc[i]+R_acc[-(i+1)])

print(ans)

Solution (Python):
from heapq import *
from collections import defaultdict
from copy import deepcopy
from math import log
from itertools import accumulate

N=int(input())
A=list(map(int,input().split()))
X=[sum(A[:N])]
Xheap=A[:N]
heapify(Xheap)
for i in range(N,2*N):
    x=heappushpop(Xheap,A[i])
    S=X[-1]+A[i]-x
    X.append(S)
A.reverse()
Y=[sum(A[:N])]
Yheap=[-i for i in A[:N]]
heapify(Yheap)
for i in range(N,2*N):
    y=-heappushpop(Yheap,-A[i])
    S=Y[-1]+A[i]-y
    Y.append(S)
Y.reverse()
ans=-10**19
for i in range(N+1):
    ans=max(ans,X[i]-Y[i])
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
INF = 10**15
n = int(input())
a = [int(item) for item in input().split()]

k_max_h = a[:n]
k_min_h = [-item for item in a[2*n:]]
heapq.heapify(k_max_h)
heapq.heapify(k_min_h)
k_max_h_sum = sum(k_max_h)
k_min_h_sum = sum(k_min_h)

k_max_forward = [-INF] * (n * 3 - 1)
k_min_back = [INF] * (n * 3 - 1)
k_max_forward[n-1] = k_max_h_sum
k_min_back[2*n-1] = k_min_h_sum

for k in range(n, n*2):
    heapq.heappush(k_max_h, a[k])
    k_max_h_sum += a[k] - heapq.heappop(k_max_h)
    k_max_forward[k] = k_max_h_sum

for k in range(n*2-1, n-1, -1):
    heapq.heappush(k_min_h, -a[k])
    k_min_h_sum += -a[k] - heapq.heappop(k_min_h)
    k_min_back[k-1] = k_min_h_sum

ans = -INF
for i in range(n-1, 2*n):
    ans = max(ans, (k_max_forward[i]+k_min_back[i]))
print(ans)

Solution (Python):
from heapq import *

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
    heappush(B,A[i])
sumB=[sum(B)]
for i in range(N,2*N):
    heappush(B,A[i])
    poped=heappop(B)
    sumB.append(sumB[-1]-poped+A[i])

A.reverse()
C=[]
for i in range(N):
    heappush(C,A[i]*(-1))
sumC=[(-1)*sum(C)]
for i in range(N,2*N):
    heappush(C,A[i]*(-1))
    poped=heappop(C)*(-1)
    sumC.append(sumC[-1]-poped+A[i])
sumC.reverse()
ans=-10**19
for i,j in zip(sumB,sumC):
    ans=max(ans,i-j)
print(ans)

Solution (Python):
from heapq import heappush, heappop
n=int(input())
a=list(map(int, input().split()))
q1=[]
q2=[]
s1=[]
s2=[]
for i in range(n):
    heappush(q1, a[i])
s1.append(sum(a[0:n]))
for ai in a[n:2*n]:
    heappush(q1, ai)
    m=heappop(q1)
    s1.append(s1[-1]+ai-m)
a=a[::-1]
for i in range(n):
    heappush(q2, -a[i])
s2.append(-sum(a[0:n]))
for ai in [-i for i in a[n:2*n]]:
    heappush(q2, ai)
    m=heappop(q2)
    s2.append(s2[-1]+ai-m)
ans=s1[0]+s2[-1]
for i in range(n+1):
    ans=max(s1[i]+s2[-i-1], ans)
print(ans)

Solution (Python):
import heapq

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

left = A[:N]
lefty = sum(left)
right = [-A[i] for i in range(3*N-1, 2*N-1, -1)]
righty = sum(right)
left_list = [lefty]
right_list = [righty]

heapq.heapify(left)
heapq.heapify(right)


for i in range(N, 2*N):
    heapq.heappush(left, A[i])
    x = heapq.heappop(left)
    lefty += A[i] - x
    left_list.append(lefty)

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

ans = - float('inf')
for i in range(len(left_list)):
    ans = max(ans, left_list[i]+right_list[len(right_list)-1-i])

print(ans)

Solution (Python):
import heapq

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

left = A[:N]
lefty = sum(left)
right = [-A[i] for i in range(3*N-1, 2*N-1, -1)]
righty = sum(right)
left_list = [lefty]
right_list = [righty]

heapq.heapify(left)
heapq.heapify(right)


for i in range(N, 2*N):
    heapq.heappush(left, A[i])
    x = heapq.heappop(left)
    lefty += A[i] - x
    left_list.append(lefty)

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

ans = - float('inf')
for i in range(len(left_list)):
    ans = max(ans, left_list[i]+right_list[len(right_list)-1-i])

print(ans)

Solution (Python):

import heapq

n = int(input())
al = list(map(int, input().split()))
q = al[:n]
heapq.heapify(q)

s = sum(al[:n])
ll = [s]
for i in range(n,2*n):
    a = al[i]
    s += a
    a = heapq.heappushpop(q, a)
    s -= a
    ll.append(s)

s = 0
q = []
heapq.heapify(q)
for i in range(2*n, 3*n):
    s -= al[i]
    heapq.heappush(q, -al[i])

rl = [-s]
for i in range(2*n-1,n-1,-1):
    a = al[i]
    s += -a
    a = heapq.heappushpop(q, -a)
    s -= a
    rl.append(-s)
rl.reverse()

res = ll[0]-rl[0]
for i in range(1,n+1):
    res = max(res, ll[i]-rl[i])

print(res)

Solution (Python):
import heapq
N = int(input())
a_ls = [int(i) for i in input().split()]
before = []
_sum_before = 0
before_scores = []
after = []
_sum_after = 0
after_scores = []
best = None
for i in range(2*N):
    _sum_before += a_ls[i]
    heapq.heappush(before, a_ls[i])
    _sum_after += a_ls[-i-1]
    heapq.heappush(after, -a_ls[-i-1])
    if i >= N:
        _sum_before -= heapq.heappop(before)
        _sum_after -= -heapq.heappop(after)
    if i >= N - 1:
        before_scores.append(_sum_before)
        after_scores.append(_sum_after)
after_scores = after_scores[::-1]
for i in range(N+1):
    score = before_scores[i] - after_scores[i]
    if best is None:
        best = score
    best = score if best < score else best
print(best)

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

n = int(input())
a = list(map(int, input().split()))
b = a[::-1]

left_q = a[:n]
heapify(left_q)
sum_left = sum(left_q)
left = [sum_left]

right_q = [-i for i in b[:n]]
heapify(right_q)
sum_right = sum(right_q)
right = [sum_right]

for i in range(n):
    if a[i+n] > left_q[0]:
        min_a = heappop(left_q)
        sum_left -= min_a
        sum_left += a[i+n]
        heappush(left_q, a[i+n])
    left.append(sum_left)
    if b[i+n] < -right_q[0]:
        min_b = heappop(right_q)
        sum_right -= min_b
        sum_right += -b[i+n]
        heappush(right_q,-b[i+n])
    right.append(sum_right)
ans = -float("inf")
for i, j in zip(left, right[::-1]):
    ans = max(ans, j+i)
print(ans)

Solution (Python):
import heapq

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


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

for i in range(n,2*n):
    sum = sum1[i-n]
    aa = heapq.heappop(h1)
    if (aa < a[i]):
        heapq.heappush(h1,a[i])
        sum += (a[i] - aa)
    else:
        heapq.heappush(h1,aa)
    sum1.append(sum)

h2 = []
sum2 = [0]
for i in range(n):
    sum2[0] -= a[3*n-i-1] 
    heapq.heappush(h2,-1 * a[3*n-i-1])

for i in range(n,2*n):
    sum = sum2[i-n]
    aa = heapq.heappop(h2)
    if (aa < -1 * a[3*n - i-1]):
        heapq.heappush(h2,-1 * a[3*n - i-1])
        sum += (-1 * a[3*n - i-1] - aa)
    else:
        heapq.heappush(h2,aa)
    sum2.append(sum)


ans = - 10 ** 15
for i in range(n+1):
    ans = max(ans,sum1[i]+sum2[n-i])

print(ans)