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.



Sample input:
2
3 1 4 1 5 9


Sample output:
1

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

n = int(input())
a = [0] + list(map(int, input().split())) #index調整
selectleft, selectright= [], []
leftscore, rightscore = [], []
for i in range(1,n+1): heapq.heappush(selectleft, a[i]) # selectleftからは最小値を取り出す
leftscore.append(sum(selectleft)) # 左のn個中n個選ぶとき
for i in range(n+1,2*n+1): # n+1~n+n個の中から選ぶとき
    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]) # selectrightからは最大値を取り出す
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)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


##    for i in range(N + 1):
##        if i == 0:
##            AL_list = A_list[:N + i]
##            AR_list = A_list[N + i:]
##            AL_list = sorted(AL_list, reverse=True)
##            AR_list = sorted(AR_list)
##            L_sum = sum(AL_list[:N])
##            R_sum = sum(AR_list[:N])
##            max_score = max(max_score, (L_sum - R_sum))
##            L_min = AL_list[0]
##            R_min = AR_list[0]
##        else:
##            A = A_list[N + i]
##            if L_min < A:
##                L_index += 1
##                L_sum = (L_sum - L_min) + A
##                L_min(AL_list[L_index])
##            if R_max > A:
##                R_sum = R_sum - A +

    print max_score


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
N=int(input())
a=[int(i) for i in input().split()]
#ans[i]-> k=i+N,
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

zenhan = seq[:N]
kouhan = list(map(lambda x: -x, seq[2*N:])) #後半は-1倍しておく
heapq.heapify(zenhan)
heapq.heapify(kouhan)

zenhan_sum_max = [0 for i in range(N + 1)] #zenhan_sum_max[i] = a0, ..., a_(N+i-1)からN個取るときの最大値
kouhan_sum_min = [0 for i in range(N + 1)] #kouhan_sum_min[i] = a_(N+i), ..., a_(3N-1)からN個取るときの最小値

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):	#最大値を取るために[-x,x]のタプルでlist
	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): # k:区切り位置
	pop = heapq.heappushpop(first_q,a_li[k])	# push + 最小値のpop
	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): # k:区切り位置
	pop = heapq.heappushpop(last_q,[-a_li[k],a_li[k]])[1] # push + 最大値のpop
	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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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()  # type: PriorityQueue[Tuple[int, None]]

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()  # type: PriorityQueue[Tuple[int, None]]

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
        # debug(a[i], b, i)
    right_queue.put(item)
    # debug(item, score, dscore)
    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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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
        # debug(a[i], b, i)
    right_queue.put(item)
    # debug(item, score, dscore)
    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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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