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 heappush, heappop
N,*A = map(int, open(0).read().split())
F = []
fs = 0
S = []
ss = 0
P = []
state = [0]*(3*N)
for i in range(N):
  heappush(F,A[i])
  fs += A[i]
for i in range(N,3*N):
  heappush(S,(-A[i],i))
  ss += A[i]
  state[i] = 1
for i in range(N):
  m,j = heappop(S)
  state[j] = 2
  ss += m
  heappush(P,(-m,j))
ans = fs-ss
for i in range(N,2*N):
  n = heappop(F)
  fs = fs-n+A[i]
  heappush(F,A[i])
  if state[i]==1:
    while state[P[0][1]]==0:
      heappop(P)
    p,j = heappop(P)
    ss += -A[i]+p
    state[j] = 1
  state[i] = 0
  ans = max(ans,fs-ss)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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


L = a[:N]
R = a[(N*2):]
L_sum_list = [sum(L)]
R_sum_list = [sum(R)]

R = [-elem for elem in R]

heapq.heapify(L)
heapq.heapify(R)

for k in range(N):
    #L側
    rem = a[N+k] - heapq.heappushpop(L, a[N+k])
    L_sum_list.append(L_sum_list[-1]+rem)

    #R側
    rem = -(a[N*2-k-1]) - heapq.heappushpop(R, -(a[N*2-k-1]))
    R_sum_list.append(R_sum_list[-1]-rem)

res = []
for k in range(N+1):
    res.append(L_sum_list[k] - R_sum_list[-k-1])

print(max(res))

Submission status: Accepted

Solution code:
import heapq

n = int(input().strip())
a = list(map(int, input().split()))
pre = a[:n]
heapq.heapify(pre)
suf = list(map(lambda x: -x, a[(2 * n):]))
heapq.heapify(suf)
left = {}
right = {}
pre_sum = sum(pre)
suf_sum = -sum(suf)
left[n - 1] = pre_sum
right[2 * n] = suf_sum
for i in range(n, 2 * n):
    heapq.heappush(pre, a[i])
    pre_sum = pre_sum + a[i] - heapq.heappop(pre)
    left[i] = pre_sum
for i in range(2 * n - 1, n - 1, -1):
    heapq.heappush(suf, -a[i])
    suf_sum = suf_sum + a[i] + heapq.heappop(suf)
    right[i] = suf_sum
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:
def main():
    import sys
    input = sys.stdin.readline
    import heapq

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

    sectionX = A[:N]
    sumX = sum(sectionX)
    heapq.heapify(sectionX)
    maxListX = [sumX]
    for i in range(N,2*N):
        a = A[i]
        heapq.heappush(sectionX,a)
        b = heapq.heappop(sectionX)
        sumX += a - b
        maxListX.append(sumX)

    for i in range(3*N):
        A[i] *= -1
    A = A[::-1]
    sectionY = A[:N]
    sumY = sum(sectionY)
    heapq.heapify(sectionY)
    maxListY = [sumY]
    for i in range(N,2*N):
        a = A[i]
        heapq.heappush(sectionY,a)
        b = heapq.heappop(sectionY)
        sumY += a - b
        maxListY.append(sumY)
    for i in range(N+1):
        maxListY[i] *= -1

    maxList = []
    for i in range(N+1):
        maxList.append(maxListX[i]-maxListY[-i-1])
    print(max(maxList))
main()

Submission status: Accepted

Solution code:
import heapq
n=int(input())
a=list(map(int,input().split()))
ans=[0 for i in range(n+1)]
ans[0]=sum(a[:n])
b=a[:n]
heapq.heapify(b)
sb=sum(b)
for i in range(n):
  sb+=a[n+i]
  c=heapq.heappushpop(b,a[n+i])
  sb-=c
  ans[i+1]=sb
b=a[2*n:]
for i in range(n):
  b[i]=-b[i]
heapq.heapify(b)
ans[n]+=sum(b)
sb=sum(b)
for i in range(n-1,-1,-1):
  sb-=a[n+i]
  c=heapq.heappushpop(b,-a[n+i])
  sb-=c
  ans[i]+=sb
print(max(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 18:58:46 2020

@author: naoki
"""
from heapq import heappush, heappop
import sys

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

hq = []
hq_r = []
for i in range(N):
    heappush(hq,a[i])
    heappush(hq_r,-1*a[-1-i])


max_A = [0 for _ in range(N+1)]
max_A[0] = sum(hq)

min_C = [0 for _ in range(N+1)]
min_C[0] = sum(hq_r) * (-1)

for i in range(N):
    heappush(hq, a[N+i])
    heappush(hq_r, -1*a[-N-1-i])
    minus = heappop(hq)
    minus_r = heappop(hq_r)
    max_A[i+1] = max_A[i] + a[N+i] - minus
    min_C[i+1] = min_C[i] + a[-N-1-i] + minus_r
    
max_val = -10e+100
for i in range(N+1):
    kari = max_A[i] - min_C[-1-i]
    if max_val < kari:
        max_val =kari
print(max_val)

Submission status: Accepted

Solution code:
import heapq

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

#N~2N要素まで、左に関して最大のN個、右に関して最小のN個をとってきたときの和を求める
#これはヒープで実装すれば簡単

left_sum_list = [0 for i in range(N+1)]
right_sum_list = [0 for i in range(N+1)]

left_heap = As[:N]
right_heap = As[2*N:]
right_heap = [-1*x for x in right_heap]

heapq.heapify(left_heap)
heapq.heapify(right_heap)

left_sum_list[0] =sum(left_heap)
right_sum_list[N] =-1*sum(right_heap)


for i in range(0,N):
    temp1 = heapq.heappushpop(left_heap, As[N+i])
    left_sum_list[i+1] = left_sum_list[i]+As[N+i]-temp1

    temp2 = heapq.heappushpop(right_heap, -1*As[2*N-i-1])
    right_sum_list[N-i-1] = right_sum_list[N-i]+(As[2*N-i-1])-(-1*temp2)

max_val = -10**23

for i in range(N+1):
    new_val = left_sum_list[i]-right_sum_list[i]
    if new_val>max_val:
        max_val = new_val

print(max_val)

Submission status: Accepted

Solution code:
import heapq

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    L, R, p = [], [], A[:N]
    L.append(sum(p))
    heapq.heapify(p)

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

    A = [-a for a in A[::-1]]
    q = A[:N]
    R.append(sum(q))
    heapq.heapify(q)

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

    ret = -10 ** 20
    for x, y in zip(L, R):
        ret = max(ret, x- y)
    print(ret)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n=int(input())
a=list(map(int,input().split()))
q=a[0:n]
sums=[0]*(n+1)
sums[0]=sum(q)
heapq.heapify(q)
am=a[n:2*n]
for i in range(0,n):
    heapq.heappush(q,am[i])
    sums[i+1]=sums[i]+am[i]-heapq.heappop(q)
p=a[2*n:3*n]
p=list(map(lambda x: x*(-1),p))
sump=sum(p)
sums[n]+=sump
heapq.heapify(p)
for i in range(n-1,-1,-1):
    heapq.heappush(p,(-1)*am[i])
    sump=sump-am[i]-heapq.heappop(p)
    sums[i]+=sump
print(max(sums))

Submission status: Accepted

Solution code:
import heapq
N = int(input())
a = list(map(int,input().split()))
fa = a[:N:]
ba = list(map(lambda x: x*(-1), a[2*N::]))
heapq.heapify(fa)
heapq.heapify(ba)
sumf = sum(fa)
sumb = sum(ba)
suml = [sumf]

k = -2

for i in range(N, 2*N):
    heapq.heappush(fa, a[i])
    sumf += a[i]
    sumf -= heapq.heappop(fa)
    suml.append(sumf)

suml[-1] += sumb

for j in range(2*N-1, N-1, -1):
        heapq.heappush(ba, -a[j])
        sumb -= a[j]
        sumb -= heapq.heappop(ba)
        suml[k] += sumb
        k -= 1
    


print(max(suml))

Submission status: Accepted

Solution code:
import heapq

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

B = []
C = []

for i in range(N):
    B.append(A[i])
    C.append(A[2*N+i]*(-1))

heapq.heapify(B)
heapq.heapify(C)

M = []
b = 0

for i in range(N+1):
    if i == 0:
        b = sum(B)
    else:
        heapq.heappush(B,A[N+i-1])
        b = b + A[N+i-1] - heapq.heappop(B)
    M.append(b)

m = []
c = 0

for i in range(N+1):
    if i == 0:
        c = sum(C)
    else:
        heapq.heappush(C,A[2*N-i]*(-1))
        c = c - A[2*N-i] - heapq.heappop(C)
    m.append(c*(-1))

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

print(ans)

Submission status: Accepted

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

a_l = a[:n]
a_c = a[n:2*n]
a_r = [ -1*i for i in  a[2*n:]]

left = [0] * (n+1)
right = [0] * (n+1)

# ヒープキュー（最小値・最大値の取得）
from heapq import heapify,heappop,heappush

left[0] = sum(a_l)
heapify(a_l)
for i,val in enumerate(a_c):
    heappush(a_l,val)
    left[i+1] = left[i] + val - heappop(a_l)

right[-1] = -1 * sum(a_r)
heapify(a_r)
for i,val in enumerate(a_c[::-1],1):
    heappush(a_r,val * -1)
    right[n-i] = right[n+1-i] + val + heappop(a_r)

lr = [i-j for i,j in zip(left,right)]
print(max(lr))

Submission status: Accepted

Solution code:
INF=10**30
from heapq import heapify,heappop,heappush
N=int(input())
a=list(map(int,input().split()))

right=list(map(lambda x:-x,a[2*N:]));heapify(right)
rmin=[INF]*(3*N);rmin[2*N]=sum(right)*-1

for i in reversed(range(N,2*N)):
    p=heappop(right)*-1
    b=min(p,a[i])
    d=0 if b==p else b-p
    heappush(right,b*-1)
    rmin[i]=rmin[i+1]+d

left=a[:N];heapify(left)
lmax=[-INF]*(3*N);lmax[N-1]=sum(left)
for i in range(N,2*N):
    p=heappop(left)
    b=max(p,a[i])
    d=0 if b==p else b-p
    heappush(left,b)
    lmax[i]=lmax[i-1]+d
res=-INF
for i in range(N,2*N+1):
    res=max(res,lmax[i-1]-rmin[i])
print(res)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
import heapq
B=A[:N]
C=[]
for i in range(N):
  C.append(-1*A[-1*(i+1)])
BP=[]
CP=[]
heapq.heapify(B)
heapq.heapify(C)
Bnow=sum(B)
Cnow=sum(C)*(-1)
BP.append(Bnow)
CP.append(Cnow)
for i in range(N):
  heapq.heappush(B,A[N+i])
  heapq.heappush(C,A[2*N-i-1]*(-1))
  b=heapq.heappop(B)
  c=heapq.heappop(C)
  Bnow+=A[N+i]-b
  Cnow+=c-A[2*N-i-1]*(-1)
  BP.append(Bnow)
  CP.append(Cnow)
D=CP[::-1]
ans=BP[0]-D[0]
for i in range(1,N+1):
  d=BP[i]-D[i]
  ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from heapq import heappush, heappop

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

    add = [0] * (N + 1)
    sub = [0] * (N + 1)

    add_sum = 0
    h = []
    for x in a[:N]:
        heappush(h, x)
        add_sum += x

    add[0] = add_sum
    for i, x in enumerate(a[N:N * 2], 1):
        heappush(h, x)
        r = heappop(h)
        add_sum += x - r
        add[i] = add_sum

    a.reverse()
    *a, = map(lambda x: -x, a)
    sub_sum = 0
    h = []
    for x in a[:N]:
        heappush(h, x)
        sub_sum += x

    sub[0] = sub_sum
    for i, x in enumerate(a[N:N * 2], 1):
        heappush(h, x)
        r = heappop(h)
        sub_sum += x - r
        sub[i] = sub_sum

    ans = -10 ** 14
    for i in range(N + 1):
        ans = max(ans, add[i] + sub[N - i])
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

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

b = a[:N]
c = a[-N:]
L = [0]*(N+1)
R = [0]*(N+1)

L[0] = sum(b)


heapq.heapify(b)

R[-1] = sum(c)
c = list(map(lambda x: -x, c))
heapq.heapify(c)

for i in range(N):
    k = a[i+N]
    x = heapq.heappop(b)
    if x < k:
        L[i+1] = L[i] + k - x
        heapq.heappush(b, k)
    else:
        L[i+1] = L[i]
        heapq.heappush(b, x)

for i in range(N-1, -1, -1):
    k = a[i+N]
    x = heapq.heappop(c)
    if -x > k:
        heapq.heappush(c, -k)
        R[i] = R[i+1] + x + k
    else:
        R[i] = R[i+1]
        heapq.heappush(c, x)
ans = -10**14
for i in range(N+1):
    ans = max(ans, L[i]-R[i])
#print(L, R)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
first = [a[0]]
first_sum = [a[0]] + [0] * (3*N-1)
for i in range(1, 3*N):
    if i < N:
        first_sum[i] = first_sum[i-1] + a[i]
        heappush(first, a[i])
    else:
        first_sum[i] = first_sum[i-1] + a[i] - heappushpop(first, a[i])

second = [-a[-1]]
second_sum = [0] * (3*N-1) + [a[-1]]
for i in range(3*N-1)[::-1]:
    if i >= 2*N:
        second_sum[i] = second_sum[i+1] + a[i]
        heappush(second, -a[i])
    else:
        second_sum[i] = second_sum[i+1] + a[i] - (-heappushpop(second, -a[i]))
ans = max(first_sum[i] - second_sum[i+1] for i in range(N-1, 2*N))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop, heappop
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
first = [a[0]]
first_sum = [0] * (3*N)
first_sum[0] = a[0]
for i in range(1, 3*N):
    if i < N:
        first_sum[i] = first_sum[i-1] + a[i]
        heappush(first, a[i])
    else:
        first_sum[i] = first_sum[i-1] + a[i] - heappushpop(first, a[i])

second = [-a[-1]]
second_sum = [0] * (3*N)
second_sum[-1] = a[-1]
for i in range(3*N-1)[::-1]:
    if i >= 2*N:
        second_sum[i] = second_sum[i+1] + a[i]
        heappush(second, -a[i])
    else:
        heappush(second, -a[i])
        x = -heappop(second)
        second_sum[i] = second_sum[i+1] + a[i] - x
ans = max(first_sum[i] - second_sum[i+1] for i in range(N-1, 2*N))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq
n = int(input())
a = [int(i) for i in input().split()]
a_l = [];a_r = []
sum_a_l = 0;sum_a_r = 0
a = tuple(a)
heapq.heapify(a_l);heapq.heapify(a_r)

for i in range(n):
  heapq.heappush(a_l,a[i])
  heapq.heappush(a_r,-a[3*n-1-i])
  sum_a_l += a[i]
  sum_a_r += a[3*n-1-i]
chk_1 = [sum_a_l]
chk_2 = [sum_a_r]
import collections
chk_1 = collections.deque(chk_1)
chk_2 = collections.deque(chk_2)
ans = -float('inf')
for i in range(n):
  heapq.heappush(a_l,a[n+i])
  heapq.heappush(a_r,-a[2*n-1-i])
  x = heapq.heappop(a_l)
  y = heapq.heappop(a_r)
  chk_1_append=chk_1.append
  chk_2_append=chk_2.append
  sum_a_l += a[n+i]-x
  sum_a_r += y+a[2*n-1-i]
  chk_1_append(sum_a_l)
  chk_2_append(sum_a_r)

for i in range(n+1):
  ans = max(chk_1.pop()-chk_2.popleft(),ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def main():
    n=II()
    aa=LI()

    l=[0]*3*n
    s=sum(aa[:n])
    hp=aa[:n]
    heapify(hp)
    for i,a in enumerate(aa[n:2*n+1],n):
        l[i]=s
        s+=a
        a=heappushpop(hp,a)
        s-=a

    r=[0]*3*n
    s=0
    hp=[]
    for a in aa[2*n:]:
        s+=a
        heappush(hp,-a)
    for i in range(2*n-1,n-2,-1):
        a=aa[i]
        r[i+1]=s
        s+=a
        a=-heappushpop(hp,-a)
        s-=a
    ans=max(l[i]-r[i] for i in range(n,2*n+1))
    print(ans)

main()

Submission status: Accepted

Solution code:
import heapq

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

dataf=[]
datab=[]

q=A[0:N]
heapq.heapify(q)
s=sum(q)
dataf.append(s)
for i in range(N,2*N):
    test=A[i]
    m=heapq.heappop(q)
    if test>m:
        s+=test-m
        dataf.append(s)
        heapq.heappush(q,test)
    else:
        dataf.append(s)
        heapq.heappush(q,m)

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

q=A[2*N:3*N]
heapq.heapify(q)
s=sum(q)
datab.append(s)
for x in range(N+1,2*N+1):
    i=3*N-x
    test=A[i]
    m=heapq.heappop(q)
    if test>m:
        s+=test-m
        datab.append(s)
        heapq.heappush(q,test)
    else:
        datab.append(s)
        heapq.heappush(q,m)

datab=datab[::-1]

print(max(dataf[i]+datab[i] for i in range(0,len(dataf))))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
N = int(input())
M = 3 * N
A = list(map(int, input().split()))
B = A[::-1]

L = [0] * (N + 1)
que = A[:N]
heapify(que)
S = sum(que)
L[0] = S
for i, a in enumerate(A[N: 2 * N], start=1):
    S += a
    heappush(que, a)
    S -= heappop(que)
    L[i] = S

R = [0] * (N + 1)
que = [-a for a in B[:N]]
heapify(que)
S = sum(que)
R[0] = S
for i, b in enumerate(B[N: 2 * N], start=1):
    b = -b
    S += b
    heappush(que, b)
    S -= heappop(que)
    R[i] = S
R = R[::-1]

ans = -10**18
for l, r in zip(L, R):
    ans = max(ans, l + r)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = list(map(int, input().split()))
F = []
L = []
for i in range(N):
    F.append(A[i])
for i in range(2*N, 3*N):
    L.append(A[i]*(-1))
heapq.heapify(F)
heapq.heapify(L)
f_sum = sum(F)
f_list = [f_sum]
l_sum = sum(L)
l_list = [l_sum]
for i in range(N, 2*N):
    f = heapq.heappushpop(F, A[i])
    f_sum = f_sum - f + A[i]
    f_list.append(f_sum)
    l = heapq.heappushpop(L, A[-i-1]*(-1))
    l_sum = l_sum - l + A[-i-1]*(-1)
    l_list.append(l_sum)

ans = (-1) * 10 ** 15
for k in range(N+1):
    ans = max(ans, f_list[k]+l_list[-k-1])
print(ans)

Submission status: Accepted

Solution code:
import heapq

n = int(input())
A = list(map(int, 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:  # 配列の個数がn+1になってしまっているので引き算が必要
            m = heapq.heappop(h)
            current_sum -= m
        if i >= n - 1:  # 配列の長さがnになっているのでresultに記録する
            result.append(current_sum)
    return result


from_left = get_sum_list(A)
from_right = get_sum_list(A_rev)[::-1]

ans = -float('inf')
for i in range(n + 1):
    score = from_left[i] + from_right[i]
    ans = max(ans, score)
print(ans)

Submission status: Accepted

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

import heapq
f1 = []; f2 = []
heapq.heapify(f1); heapq.heapify(f2)
f1_sum = 0; f2_sum = 0

for i in range(n):
  heapq.heappush(f1,a[i])
  f1_sum += a[i]
  heapq.heappush(f2,-a[3*n-1-i])
  f2_sum += a[3*n-1-i]
  
L = [f1_sum]
R = [f2_sum]

from collections import deque
L = deque(L)
R = deque(R)

for i in range(n,2*n):
  heapq.heappush(f1,a[i])
  f1_sum += a[i]
  f1_sum -= heapq.heappop(f1)
  L.append(f1_sum)
  
  heapq.heappush(f2,-a[3*n-1-i])
  f2_sum += a[3*n-1-i]
  f2_sum -= -heapq.heappop(f2)
  R.append(f2_sum)

ans = -float('inf')
for i in range(n+1):
  ans = max(ans,L.pop()-R.popleft())
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, _heapify_max, heappushpop, _heappushpop_max

N = int(input())

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

left = numbers[:N]
left_sum = sum(left)
left_memo = [0] * N
heapify(left)

right = numbers[2 * N:]
right_sum = sum(right)
right_memo = [0] * N
_heapify_max(right)

middle = numbers[N:2 * N]

for i in range(0, N):
  left_sum += (middle[i] - heappushpop(left, middle[i]))
  left_memo[i] = left_sum

for i in range(N - 1, -1, -1):
  right_sum += (middle[i] - _heappushpop_max(right, middle[i]))
  right_memo[i] = right_sum

left_memo.insert(0, sum(numbers[:N]))
right_memo.insert(0, None)
right_memo.append(sum(numbers[2 * N:]))
    
print(
  max([left_memo[i] - right_memo[i + 1] for i in range(N + 1)])
)

Submission status: Accepted

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

from heapq import heappush, heappop,heappushpop,heapify
hq1 = a[:n]
now=sum(hq1)
heapify(hq1)
lis1=[now]
for k in range(n,2*n):
    now+=a[k]
    p=heappushpop(hq1,a[k])
    now-=p
    lis1.append(now)

a.reverse()
hq2=[]
for i in range(n):
    hq2.append(-a[i])
now=sum(hq2)
heapify(hq2)
lis2=[now]
for k in range(n,2*n):
    now-=a[k]
    p=heappushpop(hq2,-a[k])
    now-=p
    lis2.append(now)
lis2.reverse()

ans=-float("inf")
for i in range(len(lis1)):
    num = lis1[i]+lis2[i]
    ans=max(ans,num)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


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

    first_half = PriorityQueue(a[:N])
    second_half = PriorityQueue(list(map(lambda x: -x, a[2 * N:])))
    f_max, s_min = [0] * (N + 1), [0] * (N + 1)
    f_max[0], s_min[-1] = sum(a[:N]), sum(a[2 * N:])

    for k in range(N):
        first_half.push(a[k + N])
        f_max[k + 1] = f_max[k] + a[k + N] - first_half.pop()
        second_half.push(-a[-N - 1 - k])
        s_min[N - 1 - k] = s_min[N - k] + a[-N - 1 - k] + second_half.pop()

    ans = -float('inf')
    for k in range(N + 1):
        if ans < f_max[k] - s_min[k]:
            ans = f_max[k] - s_min[k]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
from sys import stdin

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

# 前半と後半
first, second = [], []
heapq.heapify(first)
heapq.heapify(second)

first_sum, second_sum = 0, 0

for i in range(N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]

# first, secondそれぞれ0 - Nまで探索
L_sum = [first_sum]
R_sum = [second_sum]

for i in range(N, 2 * N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    first_sum -= heapq.heappop(first)
    L_sum.append(first_sum)

    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]
    second_sum -= - heapq.heappop(second)
    R_sum.append(second_sum)

ans = -10 ** 15

R_sum = R_sum[::-1]

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

# print(L_sum, R_sum)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq as h

input=sys.stdin.readline

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

formersum=[0 for i in range(0,N+1)]
former=A[0:N]
formersum[0]=sum(former)
h.heapify(former)
for i in range(1,N+1):
    end=i+N-1
    new=A[end]
    m=h.heappop(former)
    if m<new:
        formersum[i]=formersum[i-1]+new-m
        h.heappush(former,new)
    else:
        formersum[i]=formersum[i-1]
        h.heappush(former,m)

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

latersum=[0 for i in range(0,N+1)]
later=A[0:N]
latersum[0]=sum(later)
h.heapify(later)
for i in range(1,N+1):
    end=i+N-1
    new=A[end]
    m=h.heappop(later)
    if m<new:
        latersum[i]=latersum[i-1]+new-m
        h.heappush(later,new)
    else:
        latersum[i]=latersum[i-1]
        h.heappush(later,m)

latersum=latersum[::-1]
ans=[formersum[i]+latersum[i] for i in range(0,N+1)]
print(max(ans))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

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

L = A[:N]
heapify(L)
sumL = [sum(A[:N])]

for i in range(N):
    x = heappop(L)
    if x < A[N + i]:
        sumL.append(sumL[-1] - x + A[N + i])
        heappush(L, A[N + i])
    else:
        sumL.append(sumL[-1])
        heappush(L, x)

R = list(map(lambda x: -x, A[2 * N:]))
heapify(R)
sumR = [sum(A[2 * N:])]

for i in range(N):
    x = -heappop(R)
    if x > A[2 * N - 1 - i]:
        sumR.append(sumR[-1] - x + A[2 * N - 1 - i])
        heappush(R, -A[2 * N - 1 - i])
    else:
        sumR.append(sumR[-1])
        heappush(R, -x)

res = -10**18

for i in range(N + 1):
    res = max(res, sumL[i] - sumR[-1 - i])

print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

N = int(input())
A = list(map(int, input().split()))
B = [-a for a in A[:: -1]]

L = [0] * (N * 3)
que = A[:N]
heapify(que)
now = sum(A[:N])
for mid in range(N, N * 2 + 1):
    L[mid] = now
    a = A[mid]
    if a > que[0]:
        now -= heappop(que)
        heappush(que, a)
        now += a

R = [0] * (N * 3)
que = B[:N]
heapify(que)
now = sum(B[:N])
for mid in range(N, N * 2 + 1):
    R[mid] = now
    a = B[mid]
    if a > que[0]:
        now -= heappop(que)
        heappush(que, a)
        now += a

R = R[:: -1]

ans = -10**18
for mid in range(N, N * 2 + 1):
    x = L[mid] + R[mid - 1]
    ans = max(ans, x)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))

X = A[0:n]
S = sum(X)
import heapq
heapq.heapify(X)
L = [0]*(n+1)
L[0] = S
for k in range(n, 2*n):
    s = heapq.heappop(X)
    t = A[k]
    S += max(s, t) - s
    heapq.heappush(X, max(s, t))
    L[k-n+1] = S

Y = A[2*n:3*n]
T = sum(Y)
import heapq
Y = [(-1)*y for y in Y]
heapq.heapify(Y)
R = [0]*(n+1)
R[-1] = T
for k in reversed(range(n, 2*n)):
    s = heapq.heappop(Y)
    t = -A[k]
    T -= max(s, t) - s
    heapq.heappush(Y, max(s, t))
    R[k-n] = T

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

Submission status: Accepted

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

cums = [0]
for a in A:
    cums.append(cums[-1] + a)

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

    def size(self):
        return len(self.hq)

pq = Heapq(A[:N], False)
ps = [sum(A[:N])]
for a in A[N:2*N]:
    pq.push(a)
    b = pq.pop()
    ps.append(ps[-1] + a - b)

mq = Heapq(A[2*N:], True)
ms = [sum(A[2*N:])]
for a in reversed(A[N:2*N]):
    mq.push(a)
    b = mq.pop()
    ms.append(ms[-1] + a - b)

ans = -float('inf')
for p,m in zip(ps,reversed(ms)):
    ans = max(ans, p-m)
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]

    left = sum(A[:N])
    right = 0
    used = [False] * (3 * N)
    leftq, rightq = [], []
    heapify(leftq)
    heapify(rightq)
    for i, a in enumerate(A):
        if i < N: heappush(leftq, (a, i))
        else:heappush(rightq, (a, i))
    for _ in range(N):
        ca, ci = heappop(rightq)
        right += ca
        used[ci] = True

    Ans = left - right
    for i in range(N, 2 * N):
        left += A[i]
        heappush(leftq, (A[i], i))
        ma, mi = heappop(leftq)
        left -= ma

        if used[i] == True:
            right -= A[i]
            while rightq:
                pa, pi = heappop(rightq)
                if pi > i and not used[pi]:
                    right += pa
                    used[pi] = True
                    break

        Ans = max(Ans, left - right)
    print(Ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import heapq
import sys
def main():
    N = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    front = A[:N]
    back = list(map(lambda x:x*(-1),A[2*N:]))
    heapq.heapify(front)
    heapq.heapify(back)
    s1 = sum(front)
    s2 = sum(back)
    s1_list = [s1]
    ans = 0
    for i in range(N,2*N):
        a = A[i]
        heapq.heappush(front,a)
        min_front = heapq.heappop(front)
        s1 = s1-min_front+a
        s1_list.append(s1)
    ans = s2 +s1_list.pop()
    for i in reversed(range(N,2*N)):
        b = -A[i]
        heapq.heappush(back,b)
        min_back = heapq.heappop(back)
        s2 = s2-min_back+b
        ans = max(ans,s2+s1_list.pop())
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import collections
import sys
import heapq

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


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


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())
A = lmi()

lq = []  # normal
hq = []  # * -1
for a in A[:N]:
    heapq.heappush(lq, a)
for a in A[2 * N:]:
    heapq.heappush(hq, - a)

dpl = [0 for _ in range(N + 1)]  # middle をNまで消費したときの (a′の前半N要素の総和)
dph = [0 for _ in range(N + 1)]  # middle をNまで消費したときの (a′の後半N要素の総和)

middle = A[N:2 * N]
dpl[0] = sum(A[:N])
last_val = dpl[0]
for count in range(1, N + 1):
    heapq.heappush(lq, middle[count - 1])
    v = heapq.heappop(lq)
    dpl[count] = dpl[count - 1] - v + middle[count - 1]

dph[N] = sum(A[2 * N:])
for count in reversed(range(N)):
    heapq.heappush(hq, -middle[count])
    v = -  heapq.heappop(hq)  # bigger value
    dph[count] = dph[count + 1] - v + middle[count]


print(max(dpl[i] - dph[i] for i in range(N+1)))

Submission status: Accepted

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

import heapq
que1 = []
heapq.heapify(que1)
S = [0] * (2*N + 1)
for i in range(N):
    S[i + 1] = S[i] + a[i]
    #que1.append(a[i])
    heapq.heappush(que1, a[i])
que2 = []
heapq.heapify(que2)
T = [0] * (2*N + 1)
for i in range(N):
    T[i + 1] = T[i] + a[3*N - i - 1]
    #que2.append(-a[3*N - i - 1])
    heapq.heappush(que2, -a[3*N - i - 1])

for i in range(N, 2*N):
    mi = heapq.heappop(que1)
    #print(mi)
    if a[i] > mi:
        S[i + 1] = S[i] - mi + a[i]
        #heapq.heappop(que1)
        heapq.heappush(que1, a[i])
    else:
        S[i + 1] = S[i]
        heapq.heappush(que1, mi)
for i in range(N, 2*N):
    ma = heapq.heappop(que2) * -1
    #print(ma)
    if a[3*N - i - 1] < ma:
        T[i + 1] = T[i] - ma + a[3*N - i - 1]
        #heapq.heappop(que2)
        #que2.append(-a[3*N - i - 1])
        heapq.heappush(que2, -a[3*N - i - 1])
    else:
        T[i + 1] = T[i]
        heapq.heappush(que2, -ma)

res = -float('Inf')
for i in range(N, 2*N + 1):
    res = max(res, S[i] - T[3*N - i])
print(res)