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


l = A[0:N]
lsum = [sum(l)]
heapq.heapify(l)

r = list(map(lambda x: -x, A[-N:]))
rsum = [sum(r)]
heapq.heapify(r)
for i in range(N,2*N):
    x = heapq.heappushpop(l,A[i])
    lsum.append(lsum[-1] + A[i] - x)

    x =  - heapq.heappushpop(r, -A[3*N-1-i])
    rsum.append(rsum[-1] - A[3*N-1-i] + x)

ans = -9999999999999999
for i in range(len(rsum)):
    ans = max(ans, lsum[i]+rsum[len(rsum)-1-i])

print(ans)

Solution (Python):


"""
参考：https://img.atcoder.jp/arc074/editorial.pdf
・優先度付きキュー
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from heapq import heapify, heappushpop

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

mids = aN[N:N*2]

L = aN[:N]
R = [-aN[i] for i in range(N*2, N*3)]
heapify(L)
heapify(R)


l_sum = [0] * (N+1)
l_sum[0] = sum(aN[:N])
for i in range(N):
    
    num = heappushpop(L, mids[i])
    
    l_sum[i+1] = l_sum[i] + mids[i] - num


r_sum = [0] * (N+1)
r_sum[N] = sum(aN[N*2:])
for i in range(N-1, -1, -1):
    
    num = -(heappushpop(R, -mids[i]))
    r_sum[i] = r_sum[i+1] + mids[i] - num

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

Solution (Python):


"""
参考：https://img.atcoder.jp/arc074/editorial.pdf
・優先度付きキュー
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from heapq import heappush, heappushpop

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

mids = aN[N:N*2]
L = []
R = []
for i in range(N):
    
    heappush(L, aN[i])
    heappush(R, -aN[i+N*2])


l_sum = [0] * (N+1)
l_sum[0] = sum(aN[:N])
for i in range(N):
    
    num = heappushpop(L, mids[i])
    
    l_sum[i+1] = l_sum[i] + mids[i] - num


r_sum = [0] * (N+1)
r_sum[N] = sum(aN[N*2:])
for i in range(N-1, -1, -1):
    
    num = -(heappushpop(R, -mids[i]))
    r_sum[i] = r_sum[i+1] + mids[i] - num

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

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

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

hq1=A[:N]
heapify(hq1)
sum1=sum(hq1)


T1=[]
T1.append(sum1)

for i in range(N, 2*N):
	x=A[i]
	if hq1[0]<x:
		u=heappop(hq1)
		heappush(hq1,x)
		sum1+=(x-u)
	T1.append(sum1)


hq2=map(lambda x: x*-1, A[2*N:])
sum2=-1*sum(hq2)
heapify(hq2)



T2=[]
T2.append(sum2)

for i in range(2*N-1,N-1,-1):
	x=A[i]
	if x*-1 > hq2[0]<x:
			u=heappop(hq2)
			heappush(hq2,x*-1)
			sum2+=u+x

	T2.append(sum2)


T2.reverse()


ans=float("-inf")
for x, y in zip(T1, T2):
	ans=max(ans , x-y)
print ans

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


l = A[0:N]
lsum = [sum(l)]
heapq.heapify(l)
for i in range(N,2*N):
    x = heapq.heappushpop(l,A[i])
    lsum.append(lsum[-1] + A[i] - x)


r = list(map(lambda x: -x, A[-N:N*3]))
rsum = [sum(r)]
heapq.heapify(r)
for i in range(N,2*N):
    x = heapq.heappushpop(r, -A[3*N-1-i])
    rsum.append(rsum[-1] - A[3*N-1-i] - x)

ans = -9999999999999999
for i in range(len(rsum)):
    ans = max(ans, lsum[i]+rsum[len(rsum)-1-i])

print(ans)

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

Left, Right = A[:N], list(map(lambda a: -a, A[-N:]))
heapq.heapify(Left)
heapq.heapify(Right)
Left_SUM, Right_SUM = [sum(Left)], [-sum(Right)]

M = A[N:2*N]

for k in range(N):
    lo = heapq.heappushpop(Left, M[k])
    Left_SUM.append(Left_SUM[-1] + M[k] - lo)


for k in reversed(range(N)):
    hi = -heapq.heappushpop(Right, -M[k])
    Right_SUM.append(Right_SUM[-1] + M[k] - hi)


ans = max([l - r for l, r in zip(Left_SUM, Right_SUM[::-1])])
print(ans)

Solution (Python):
import heapq

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

max_score = - float("inf")

red_list = a_list[:N]
blue_list = [-a for a in a_list[2 * N:]]
heapq.heapify(red_list)
heapq.heapify(blue_list)
red_sum = [sum(red_list)]
blue_sum = [sum(blue_list)]

for i in range(N, 2 * N):
    heapq.heappush(red_list, a_list[i])
    item = heapq.heappop(red_list)
    red_sum.append(red_sum[-1] + a_list[i] - item)

for i in range(2 * N - 1, N - 1, -1):
    heapq.heappush(blue_list, -a_list[i])
    item = heapq.heappop(blue_list)
    blue_sum.append(blue_sum[-1] - a_list[i] - item)

for i in range(N+1):
    score = red_sum[i] + blue_sum[-(i + 1)]
    if max_score < score:
        max_score = score
print(max_score)

Solution (Python):
import heapq

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

max_score = - float("inf")

red_list = a_list[:N]
blue_list = [-a for a in a_list[2 * N:]]
heapq.heapify(red_list)
heapq.heapify(blue_list)
red_sum = [sum(red_list)]
blue_sum = [sum(blue_list)]

for i in range(N, 2 * N):
    heapq.heappush(red_list, a_list[i])
    item = heapq.heappop(red_list)
    red_sum.append(max(red_sum[-1], red_sum[-1] + a_list[i] - item))

for i in range(2 * N - 1, N - 1, -1):
    heapq.heappush(blue_list, -a_list[i])
    item = heapq.heappop(blue_list)
    blue_sum.append(max(blue_sum[-1], blue_sum[-1] - a_list[i] - item))

for i in range(N+1):
    score = red_sum[i] + blue_sum[-(i + 1)]
    if max_score < score:
        max_score = score
print(max_score)

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



sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))

for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


print(max([r-b for r, b in zip(sum_red, sum_blue[::-1])]))

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



sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))

for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


print(max([r-b for r, b in zip(sum_red, sum_blue[::-1])]))

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

X = A[0:N]
B = A[N:2*N]
Y = [-_ for _ in A[2*N:3*N]]

heapq.heapify(X)
heapq.heapify(Y)

x = [sum(X)]
y = [sum(Y)]

for i in range(N):
    x += [B[i] - heapq.heappushpop(X, B[i])]
    y += [-B[-1-i] - heapq.heappushpop(Y, -B[-1-i])]

for i in range(N):
    x[i+1] = x[i]+x[i+1]
    y[i+1] = y[i]+y[i+1]

print(max([x[_] + y[-1 - _] for _ in range(N+1)]))

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):
import heapq
import copy
n=int(input())
a=list(map(int,input().split()))
ca=copy.deepcopy(a)
f=ca[:n]
heapq.heapify(f)
fs=sum(f)
fsl=[0 for i in range(n+1)]
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
l=list(map(lambda x:-x,ca[2*n:]))
heapq.heapify(l)
ls=sum(l)
lsl=[0 for i in range(n+1)]
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=-float('inf')
for i in range(n+1):
    ans=max(ans,fsl[i]+lsl[i])
print(ans)

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


fin = sys.stdin.readline
N = int(fin())
a_list = [int(elem) for elem in fin().split()]

left_pq = a_list[:N]
right_pq = [-item for item in a_list[2 * N:]]
heapify(left_pq)
heapify(right_pq)

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

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

Solution (Python):
import sys

try:
    from _heapq import heapify, heappushpop
except ImportError:
    from heapq import heapify, heappushpop
try:
    from _heapq import _heapreplace_max
except ImportError:
    pass
try:
    from _heapq import _heapify_max as heapify_max
except ImportError:
    from heapq import _heapify_max as heapify_max
try:
    from _heapq import _siftup_max
except ImportError:
    from heapq import _siftup_max


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


fin = sys.stdin.readline
N = int(fin())
a_list = [int(elem) for elem in fin().split()]

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

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

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

Solution (Python):

from heapq import heapify, heappushpop
from heapq import _heapify_max as heapify_max, _siftup_max


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



N, *a_list = map(int, open(0).read().split())

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

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

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

Solution (Python):
import sys
from heapq import heapify, heappushpop
from heapq import _heapify_max as heapify_max, _siftup_max


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


fin = sys.stdin.readline
N = int(fin())
a_list = [int(elem) for elem in fin().split()]

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

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

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

Solution (Python):



import sys
fin = sys.stdin.readline
from heapq import heappop, heappush, heapify

N = int(fin())
a_list = [int(elem) for elem in fin().split()]
left, right = a_list[:N], a_list[N:]

thrown_away = [False] * (2 * N)
discarded_items = []


right_sum = sum(right)
for i, item in enumerate(right):
    if i < N:
        heappush(discarded_items, (item, i))
        thrown_away[i] = True
        right_sum -= item
    else:
        if item > discarded_items[0][0]:
            old_item, old_idx = heappop(discarded_items)
            thrown_away[old_idx] = False
            heappush(discarded_items, (item, i))
            thrown_away[i] = True
            right_sum += old_item - item



left_sum = sum(left)
heapify(left)

thrown_away.append(False)
max_score = left_sum - right_sum
for i, item in enumerate(right[:N]):
    if not thrown_away[i]:
        
        updated_idx = -1
        
        while thrown_away[updated_idx] == False:
            updated_item, updated_idx = heappop(discarded_items)
        right_sum += updated_item - item
        thrown_away[updated_idx] = False
    else:
        
        
        thrown_away[i] = False
    
    if item > left[0]:
        old_item = heappop(left)
        heappush(left, item)
        left_sum += item - old_item
    max_score = max(max_score, left_sum - right_sum)

print(max_score)

Solution (Python):
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush, heapify

N = int(fin())
a_list = [int(elem) for elem in fin().split()]
left, right = a_list[:N], a_list[N:]

thrown_away = [False] * (2 * N)
discarded_items = []


right_sum = sum(right)
for i, item in enumerate(right):
    if i < N:
        heappush(discarded_items, (item, i))
        thrown_away[i] = True
        right_sum -= item
    else:
        if item > discarded_items[0][0]:
            old_item, old_idx = heappop(discarded_items)
            thrown_away[old_idx] = False
            heappush(discarded_items, (item, i))
            thrown_away[i] = True
            right_sum += old_item - item



left_sum = sum(left)
heapify(left)

thrown_away.append(False)
max_score = left_sum - right_sum
for i, item in enumerate(right[:N]):
    if not thrown_away[i]:
        
        updated_idx = -1
        
        while thrown_away[updated_idx] == False:
            updated_item, updated_idx = heappop(discarded_items)
        right_sum += updated_item - item
        thrown_away[updated_idx] = False
    else:
        
        
        thrown_away[i] = False
    
    if item > left[0]:
        old_item = heappop(left)
        heappush(left, item)
        left_sum += item - old_item
    max_score = max(max_score, left_sum - right_sum)

print(max_score)

Solution (Python):
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush, heapify

N = int(fin())
a_list = [int(elem) for elem in fin().split()]
left, right = a_list[:N], a_list[N:]

thrown_away = [False] * (2 * N)
discarded_items = []


right_sum = sum(right)
for i, item in enumerate(right):
    if i < N:
        heappush(discarded_items, (item, i))
        thrown_away[i] = True
        right_sum -= item
    else:
        if item > discarded_items[0][0]:
            old_item, old_idx = heappop(discarded_items)
            thrown_away[old_idx] = False
            heappush(discarded_items, (item, i))
            thrown_away[i] = True
            right_sum += old_item - item



left_sum = sum(left)
heapify(left)
moved_to_left = [False] * (2 * N + 1)

moved_to_left[-1] = True
max_score = left_sum - right_sum
for i, item in enumerate(right[:N]):
    if not thrown_away[i]:
        
        updated_idx = -1
        while moved_to_left[updated_idx] == True:
            updated_item, updated_idx = heappop(discarded_items)
        right_sum += updated_item - item
        thrown_away[updated_idx] = False
    else:
        
        moved_to_left[i] = True
    
    if item > left[0]:
        old_item = heappop(left)
        heappush(left, item)
        left_sum += item - old_item
    max_score = max(max_score, left_sum - right_sum)

print(max_score)

Solution (Python):
N = int(input())
a = list(map(int,input().split()))
import heapq
hq = a[:N]
fsum = [0]*(N+1)
fsum[0] = sum(hq)
heapq.heapify(hq)
for i in range(N):
    a_ = a[N+i]
    a_min = heapq.heappop(hq)
    if a_min < a_:
        fsum[i+1]=fsum[i]-a_min+a_
        a_min = a_
    else:
        fsum[i+1]=fsum[i]
    heapq.heappush(hq,a_min)
a = [-a[-i-1] for i in range(3*N)]
hq = a[:N]
lsum = [0]*(N+1)
lsum[0] = sum(hq)
heapq.heapify(hq)
for i in range(N):
    a_ = a[N+i]
    a_min = heapq.heappop(hq)
    if a_min < a_:
        lsum[i+1]=lsum[i]-a_min+a_
        a_min = a_
    else:
        lsum[i+1]=lsum[i]
    heapq.heappush(hq,a_min)
lsum.reverse()
ans = -float('inf')
for i in range(N+1):
    diff = fsum[i]+lsum[i]
    if ans < diff:
        ans = diff
print(ans)

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

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

L = a[:n]
sum_l = [sum(L)]
heapify(L)

ML = a[n:2 * n]
ML = deque(ML)

R = list(map(lambda x: (-1) * x, a[2 * n:]))
sum_r = [sum(R)]  
heapify(R)

MR = list(map(lambda x: (-1) * x, a[n:2 * n]))
MR = deque(MR)

for i in range(n):
    add_to_l = ML.popleft()
    heappush(L, add_to_l)
    subtract_to_l = heappop(L)

    t = sum_l[-1] + add_to_l - subtract_to_l
    sum_l.append(t)



for i in range(n):
    add_to_r = MR.pop()
    heappush(R, add_to_r)
    subtract_to_r = heappop(R)

    t = sum_r[-1] + add_to_r - subtract_to_r
    sum_r.append(t)



sum_r = sum_r[::-1]

ans = sum_l[0] + sum_r[0]
for i in range(1, n + 1):
    t = sum_l[i] + sum_r[i]
    ans = max(ans, t)

print(ans)

Solution (Python):
import heapq
N = int(input())
A = list(map(int, input().split()))
R = A[:N]
B = [-a for a in A[2 * N:]]
heapq.heapify(R)
heapq.heapify(B)
R_sum = [sum(R)]
B_sum = [sum(B)]

for i in range(N, 2 * N):
    heapq.heappush(R, A[i])
    q = heapq.heappop(R)
    R_sum.append(max(R_sum[-1], R_sum[-1] + A[i] - q))

for i in range(2 * N - 1, N - 1, -1):
    heapq.heappush(B, -A[i])
    q = heapq.heappop(B)
    B_sum.append(max(B_sum[-1], B_sum[-1] - A[i] - q))

num = -float("inf")
for p, q in zip(R_sum, B_sum[::-1]):
    num = max(num, p + q)

print(num)

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

sumLeft = [0] * (N+1) 
sumLeft[0] = sum(A[:N])
Aleft = A[:N]
heapq.heapify(Aleft)

sumRight = [0] * (N+1) 
sumRight[-1] = sum(A[2*N:]) 
Aright = [-1*i for i in A[2*N:]] 
heapq.heapify(Aright)

for i in range(1, N+1):
    a = A[N+i-1]
    b = -1 * A[2*N-i]
    sumLeft[i] = sumLeft[i-1] + a - heapq.heappushpop(Aleft, a)
    sumRight[-1-i] = sumRight[-i] + heapq.heappushpop(Aright, b) - b

score = sumLeft[0] - sumRight[0]
for i in range(1, N+1):
    score = max(score, sumLeft[i] - sumRight[i])
print(score)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappop, heappush

n = ni()
a = list(li())

first = []
second = []

for ai in a[:n]:
    heappush(first, ai)
    
for ai in a[2*n:]:
    heappush(second, -ai)
    
fsum = [sum(first)]
ssum = [sum(second)]
    
ans = fsum[0] + ssum[0]

for i in range(n,2*n):
    heappush(first, a[i])
    fmin = heappop(first)
    fsum.append(fsum[-1] - fmin + a[i])
    
    heappush(second, -a[3*n-i-1])
    smax = heappop(second)
    ssum.append(ssum[-1] - smax - a[3*n-i-1])
    
ssum = ssum[::-1]

for fs,ss in zip(fsum, ssum):
    ans = max(ans, fs+ss)
    
print(ans)

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

a1 = a[:n]
ax = a[n:2*n]
a2 = list(map(lambda x: -x, a[2*n:]))


sum_a1 = sum(a1)
fdif1 = [sum_a1]
heapq.heapify(a1)
for i in range(n):
    p = heapq.heappushpop(a1,ax[i])
    fdif1.append(fdif1[-1]+ax[i]-p)
    
sum_a2 = sum(a2)
fdif2 = [sum_a2]
heapq.heapify(a2)

for i in range(n):
    p = heapq.heappushpop(a2,-ax[-1-i])
    fdif2.append(fdif2[-1]-ax[-1-i]-p)
fdif2.reverse()

fdif = [fdif1[i]+fdif2[i] for i in range(n+1)]
print(max(fdif))

Solution (Python):
import heapq

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

ans = -10**15
h1 = a[:n]
h2 = [-a[i] for i in range(2*n, 3*n)]
heapq.heapify(h1)
heapq.heapify(h2)

h1sum = sum(a[:n])
h2sum = sum(a[2*n:])

box1 = [h1sum]
box2 = [h2sum]

for i in range(1, n+1):
    heapq.heappush(h1, a[n+i-1])
    h1sum += a[n+i-1] - heapq.heappop(h1)
    box1.append(h1sum)

for i in range(1, n+1):
    heapq.heappush(h2, -a[2*n-i])
    h2sum += a[2*n-i] - (-heapq.heappop(h2))
    box2.append(h2sum)

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

print(ans)

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

lsum = sum(src[:N])
lmem = [lsum]
lq = src[:N][:]
heapq.heapify(lq)
for a in src[N:2*N]:
    if a <= lq[0]:
        lmem.append(lmem[-1])
    else:
        lsum += a - heapq.heappop(lq)
        heapq.heappush(lq, a)
        lmem.append(lsum)

rq = [-a for a in src[-N:]]
rsum = sum(rq)
rmem = [rsum]
heapq.heapify(rq)
for a in reversed(src[N:2*N]):
    if -a <= rq[0]:
        rmem.append(rmem[-1])
    else:
        rsum += -a - heapq.heappop(rq)
        heapq.heappush(rq, -a)
        rmem.append(rsum)

ans = -float('inf')
for l,r in zip(lmem, rmem[::-1]):
    ans = max(ans, l+r)
print(ans)

Solution (Python):
from heapq import heapify, heappushpop
N, *A = map(int, open(0).read().split())
def f(L):
    q = L[:N]
    heapify(q)
    s = sum(q)
    yield s
    for e in L[N:2 * N]:
        s += e - heappushpop(q, e)
        yield s
print(max(map(sum, zip(f(A), list(f([-a for a in A[::-1]]))[::-1]))))

Solution (Python):
from heapq import heapify, heappushpop
N, *a = map(int, open(0).read().split())

hq1 = a[:N]
hq2 = [-ai for ai in a[-N:]]

heapify(hq1)
heapify(hq2)

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

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

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

Solution (Python):
import heapq
N = int( input())
A = list( map( int, input().split()))
fsum = [0]*(N+1)
bsum = [0]*(N+1)
forward = A[:N]
back = A[2*N:]
back = list(map( lambda x:-x, back))
heapq.heapify(forward)
heapq.heapify(back)
fsum[0] = sum(forward)
fsumnow = fsum[0]
bsum[N] = -sum(back)
bsumnow = bsum[N]
for i in range(1,N+1):
    heapq.heappush(forward, A[N+i-1])
    fsumnow += A[N+i-1]
    fsumnow -= heapq.heappop(forward)
    fsum[i] = fsumnow
    heapq.heappush(back, -A[2*N-i])
    bsumnow += A[2*N-i]
    bsumnow += heapq.heappop(back)
    bsum[N-i] = bsumnow
ans = fsum[0] - bsum[0]
for i in range(1,N+1):
    ans = max(ans, fsum[i] - bsum[i])
print(ans)

Solution (Python):
import heapq
N = int(input())
A = [int(x) for x in input().split()]
B = [[0, 0] for i in range(N + 1)]
A1 = A[:N]
B[0][0] = sum(A1)
heapq.heapify(A1)
for i in range(N):
  B[i + 1][0] = B[i][0]
  B[i + 1][0] += A[N + i]
  heapq.heappush(A1, A[N + i])
  B[i + 1][0] -= heapq.heappop(A1)
A2 = [-a for a in A[2 * N:]]
B[N][1] = -sum(A2)
heapq.heapify(A2)
for i in range(N):
  B[N - i - 1][1] = B[N - i][1]
  B[N - i - 1][1] += A[2 * N - i - 1]
  heapq.heappush(A2, -A[2 * N - i - 1])
  B[N - i - 1][1] += heapq.heappop(A2)
ans = - 10 ** 18
for b0, b1 in B:
  ans = max(b0 - b1, ans)
print(ans)

Solution (Python):
import heapq
n = int(input())
a = list(map(int,input().split()))
aka = a[:n]
heapq.heapify(aka)
akasum = [0] * (n+1)
akasum[0] = sum(aka)
ao = a[2*n:]
aosum = [0] * (n+1)
aosum[-1] = sum(ao)
for i in range(len(ao)):
  ao[i] = -ao[i]
heapq.heapify(ao)
for i in range(n,2*n):
  b = heapq.heappop(aka)
  if b >= a[i]:
    heapq.heappush(aka, b)
    akasum[i-n+1] = akasum[i-n] 
  else:
    heapq.heappush(aka, a[i])
    akasum[i-n+1] = akasum[i-n] + a[i] - b
  b = heapq.heappop(ao)
  if b >=  -a[-i-1]:
    heapq.heappush(ao, b)
    aosum[-i+n-2] = aosum[-i+n-1]
  else:
    heapq.heappush(ao, -a[-i-1])
    aosum[-i+n-2] = aosum[-i+n-1] + a[-i-1] + b
ans = - float("inf")
for i in range(n+1):
  kota = akasum[i] - aosum[i]
  ans = max(kota,ans)
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = a[n:2*n]

import heapq

q = a[:n]
heapq.heapify(q)

res = [0]*(n+1)
res[0] = sum(q)
for i, x in enumerate(b):
    heapq.heappush(q, x)
    y = heapq.heappop(q)
    res[i+1] = res[i]+x-y

b.reverse()
q = [-x for x in a[2*n:]]
heapq.heapify(q)
s = -sum(q)
res[-1] -= s

for i, x in enumerate(b):
    heapq.heappush(q, -x)
    y = heapq.heappop(q)
    s += x+y
    res[-2-i] -= s

print(max(res))

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


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(N, A):
    q = []
    lc = [0]*(N+1)
    for i in range(N):
        heapq.heappush(q, A[i])
        lc[0] += A[i]
    for i in range(N, 2*N):

        a = heapq.heappushpop(q, A[i])
        lc[i-N+1] = lc[i-N] + A[i] - a

    q = []
    rc = [0] * (N+1)
    for i in range(3*N-1, 2*N-1, -1):
        heapq.heappush(q, -A[i])
        rc[N] += A[i]
    for i in range(2*N-1, N-1, -1):
        a = -heapq.heappushpop(q, -A[i])
        rc[i-N] = rc[i-N+1] + A[i] - a

    return max(map(lambda x: x[0]-x[1], zip(lc, rc)))


def main():
    N = read_int()
    A = read_int_n()

    print(slv(N, A))


if __name__ == '__main__':
    main()

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

a1 = a[:n]
heapq.heapify(a1)
a1_sum = sum(a1)
a1_sums = [a1_sum]
for i in range(n, 2*n):
    a1_min = heapq.heappop(a1) 
    if a[i] > a1_min:
        heapq.heappush(a1, a[i])
        a1_sum = a1_sum - a1_min + a[i]
    else:
        heapq.heappush(a1, a1_min)
    a1_sums.append(a1_sum)

a2 = a[-n:]
a2_sum = sum(a2)
a2_sums = [a2_sum]
a2_inv = [-aa for aa in a2]
heapq.heapify(a2_inv)
for i in range(2*n-1, n-1, -1):
    a2_max = -heapq.heappop(a2_inv) 
    if a[i] < a2_max:
        heapq.heappush(a2_inv, -a[i])
        a2_sum = a2_sum - a2_max + a[i]
    else:
        heapq.heappush(a2_inv, -a2_max)
    a2_sums.append(a2_sum)
a2_sums = a2_sums[::-1] 

ans = a1_sums[0] - a2_sums[0]
for a1_s, a2_s in zip(a1_sums, a2_sums):
    ans = max(ans, a1_s-a2_s)
print(ans)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

q_b = aa[:N]
q_a = list(map(lambda x: -x, aa[2*N:]))

sum_b = [sum(q_b)]
sum_a = [sum(q_a)]

heapq.heapify(q_b)
heapq.heapify(q_a)

sum = sum_b[0]
for i in range(N,2*N):
	push = aa[i]
	pop = heapq.heappushpop(q_b,push)
	sum = sum - pop + push
	sum_b.append(sum)

sum = sum_a[0]
for i in range(2*N-1,N-1,-1):
	push = -aa[i]
	pop = heapq.heappushpop(q_a,push)
	sum = sum - pop + push
	sum_a.append(sum)

ans = -INF
for i in range(N+1):
	ans = max(ans,sum_b[i] + sum_a[N-i])

print(ans)

Solution (Python):










import heapq

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


H=A[:N]
heapq.heapify(H)


S=sum(A[:N])
F=[S]
for i in range(N,2*N):
  a=heapq.heappop(H)
  if a < A[i]:
    heapq.heappush(H, A[i])
    S+=(A[i]-a)
  else:
    heapq.heappush(H, a)
  F.append(S)


H=[int(x)*-1 for x in A[2*N:]]
heapq.heapify(H)


S=sum(A[2*N:])
F2=[S]
for i in range(2*N-1,N-1,-1):
  a=heapq.heappop(H)*(-1)
  if a > A[i]:
    heapq.heappush(H, A[i]*(-1))
    S+=(A[i]-a)
  else:
    heapq.heappush(H, -a)
  F2.append(S)
  

F2=F2[:][::-1]
ans=(10**14)*(-1)

for i in range(N+1):
  ans=max(ans,F[i]-F2[i])
print(ans)

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

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

q=A[:N]
heapify(q)
q_sum=sum(q)

B=[ float("-inf") for i in range(3*N)]
B[N-1]=q_sum

for i in range(N,2*N):
	x=A[i]
	if x>q[0]:
		tmp=heappop(q)
		q_sum-=tmp
		q_sum+=x
		heappush(q,x)
	B[i]=q_sum

q=map(lambda x: x*-1, A[2*N:] )
heapify(q)

q_sum=sum(q)*-1
B[2*N-1]-=q_sum

for i in range(2*N-1,N-1,-1):
	x=A[i]*-1
	if q[0]<x:
		tmp=heappop(q)
		q_sum-=tmp*-1
		q_sum+=x*-1
		heappush(q,x)
	B[i-1]-=q_sum

print max(B)

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