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:
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左側A[:k] (N<=k<=2*N)までの最大値を求める
# 同様に右側も求める
N = ir()
A = lr()
left_sum = [0] * (N+1)
right_sum = [0] * (N+1)
left = A[:N]; heapify(left)
right = A[-N:]
right = [-x for x in right]
heapify(right)
cur = sum(left)
left_sum[0] = cur
center = A[N:-N]
for i in range(N):
    heappush(left, center[i])
    l = heappop(left)
    cur = cur - l + center[i]
    left_sum[i+1] = cur

cur = sum(right)
right_sum[N] = cur
for i in range(N):
    heappush(right, -center[N-1-i])
    r = heappop(right)
    cur = cur - r + (-center[N-1-i])
    right_sum[N-1-i] = cur

answer = -10 ** 15
for i in range(N+1):
    temp = left_sum[i] + right_sum[i]
    if temp > answer:
        answer = temp

print(answer)
# 05

Submission status: Accepted

Solution code:
import heapq
n = int(input())
a = list(map(int, input().split()))
fh_sum = [0]*(n+1) 
sh_sum = [0]*(n+1) 
fh_sum[0] = sum(a[:n])
sh_sum[-1] = sum(a[2*n:])

fh = a[:n]
heapq.heapify(fh)
for i in range(n):
  ai = a[n+i]
  heapq.heappush(fh, ai)
  small = heapq.heappop(fh)
  fh_sum[i+1] = fh_sum[i] + ai - small

sh = list(map(lambda x:-x, a[2*n:]))
heapq.heapify(sh)

for i in range(n):
  bi = a[2*n-i-1]
  heapq.heappush(sh, -1*bi)
  large = -1 * heapq.heappop(sh)
  sh_sum[n-i-1] = sh_sum[n-i] + bi - large 

ans = -float('inf')
for f, s in zip(fh_sum, sh_sum):
  ans = max(ans, f-s)

print(ans)

Submission status: Accepted

Solution code:
from heapq import*
n,*a=map(int,open(0).read().split())
hq1=[x for x in a[:n]]
hq2=[-x for x in a[n+n:]]
su1=sum(hq1)
su2=-sum(hq2)
mem1=[su1]
mem2=[su2]
heapify(hq1)
heapify(hq2)
for x in a[n:n+n]:
	y=heappop(hq1)
	if x>y:
		heappush(hq1,x)
		su1+=x-y
	else:
		heappush(hq1,y)
	mem1.append(su1)
for x in reversed(a[n:n+n]):
	y=-heappop(hq2)
	if x<y:
		heappush(hq2,-x)
		su2-=y-x
	else:
		heappush(hq2,-y)
	mem2.append(su2)
print(max(f-b for f,b in zip(mem1,mem2[::-1])))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import heapq

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

    l = a[:N]
    heapq.heapify(l)
    ls = sum(l)
    use = [ls]
    for i in range(N):
        num = a[N+i]
        ln = heapq.heappop(l)
        if ln > num:
            heapq.heappush(l,ln)
        else:
            heapq.heappush(l,num)
            ls += num-ln
        use.append(ls)

    b = []
    for num in a[::-1]:
        b.append(-1*num)
        
    r = b[:N]
    heapq.heapify(r)
    rs = sum(r)
    use[-1] += rs
    for i in range(N):
        num = b[N+i]
        rn = heapq.heappop(r)
        if rn < num:
            heapq.heappush(r,num)
            rs += (num-rn)
        else:
            heapq.heappush(r,rn)
        use[-i-2] += rs

    print(max(use))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

class MaxHeap:
    def __init__(self, li):
        self.hp = []
        for e in li:
            heappush(self.hp, -e)

    def push(self, x):
        heappush(self.hp, -x)

    def pop(self):
        ret = heappop(self.hp)
        ret *= -1
        return ret

    def seak(self):
        return -self.hp[0]

    def sum(self):
        return -sum(self.hp)

A1=A[:N]
A2=A[N:2*N]
A3=A[2*N:]

heapify(A1)
A1_sum=sum(A1)
A1_li=[A1_sum]
for a in A2:
  heappush(A1, a)
  p=heappop(A1)
  A1_sum+=a-p
  A1_li.append(A1_sum)
  
A3_sum=sum(A3)
A3=MaxHeap(A3)

A3_li=[A3_sum]
for a in A2[::-1]:
  A3.push(a)
  A3_sum+=a
  p=A3.pop()
  A3_sum-=p
  A3_li.append(A3_sum)
  
A3_li=A3_li[::-1]  
ans=False
for a1, a3 in zip(A1_li, A3_li):
  if not ans:
    ans=a1-a3
  else:
    ans=max(ans, a1-a3)
print(ans)

Submission status: Accepted

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

L = A[:N]
R = [-a for a in A[-N:]]
mid = A[N:-N]

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

Lsum = [sum(L)]
Rsum = [sum(R)]

for m in mid:
    if m > L[0]:
        Lsum.append(Lsum[-1] + m - L[0])
        heapq.heappushpop(L, m)
    else:
        Lsum.append(Lsum[-1])

for m in mid[::-1]:
    if -m > R[0]:
        Rsum.append(Rsum[-1] - m - R[0])
        heapq.heappushpop(R, -m)
    else:
        Rsum.append(Rsum[-1])
Rsum = Rsum[::-1]


ans = -10 ** 18
for x, y in zip(Lsum, Rsum):
    ans = max(ans, x + y)

print(ans)

Submission status: Accepted

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

L = A[0:n]
R = A[2*n:3*n]
import heapq
sl = sum(L)
heapq.heapify(L)
sls = [0]*(n+1)
sls[0] = sl
for i in range(n, 2*n):
    heapq.heappush(L, A[i])
    x = heapq.heappop(L)
    sl += A[i]-x
    sls[i-n+1] = sl
#print(sls)

sr = sum(R)
R = [-c for c in R]
heapq.heapify(R)
srs = [0]*(n+1)
srs[-1] = sr
for i in reversed(range(n, 2*n)):
    heapq.heappush(R, -A[i])
    x = -heapq.heappop(R)
    sr += A[i]-x
    srs[i-n] = sr
#print(srs)
ans = - 10**18
for i in range(n+1):
    ans = max(ans, sls[i]-srs[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math

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

lst=A[:N]
_sum=sum(lst)
heapify(lst)

sumlstleft=[0 for i in range(N+1)]
sumlstleft[0]=_sum
for i in range(N,2*N):
    heappush(lst,A[i])
    a=heappop(lst)
    _sum+=A[i]-a
    sumlstleft[i-N+1]=_sum
lst=A[N*2:]
_sum=sum(lst)
lst=[-i for i in lst]
heapify(lst)
sumlstright=[0 for i in range(N+1)]
sumlstright[-1]=_sum
for i in range(2*N-1,N-1,-1):
    heappush(lst,-A[i])
    a=heappop(lst)
    _sum-=-a
    _sum+=A[i]
    sumlstright[i-N]=_sum
print(max([sumlstleft[i]-sumlstright[i] for i in range(N+1)]))

Submission status: Accepted

Solution code:
import sys
import heapq
input=sys.stdin.readline
N=int(input())
A=tuple(map(int,input().split()))
hq=list(A[:N])
heapq.heapify(hq)
s=[0]*(N+1)
s[0]=sum(hq)
for i in range(N):
  x=heapq.heappop(hq)
  if x >= A[N+i]:
    s[i+1]=s[i]
    heapq.heappush(hq,x)
  else:
    s[i+1]=s[i]+A[N+i]-x
    heapq.heappush(hq,A[N+i])
    
hq=list(map(lambda x:-x, A[2*N:]))
heapq.heapify(hq)
t=[0]*(N+1)
t[-1]=-sum(hq)
for i in range(N-1,-1,-1):
  x=heapq.heappop(hq)
  x=-x
  if x <= A[N+i]:
    t[i]=t[i+1]
    heapq.heappush(hq,-x)
  else:
    t[i]=t[i+1]-x+A[N+i]
    heapq.heappush(hq,-A[N+i])
ans=-10**15
for x,y in zip(s,t):
  ans=max(x-y,ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    from heapq import heapify, heappush, heappop
    h1 = A[:N]
    h2 = [-a for a in A[2*N:]]
    heapify(h1)
    heapify(h2)

    s = sum(A[:N])
    ans = s
    S1 = [s]*(N+1)
    for i in range(N):
        c = A[N+i]
        if h1[0] < c:
            S1[i+1] = S1[i] - heappop(h1) + c
            heappush(h1, c)
        else:
            S1[i+1] = S1[i]
    s = sum(A[2*N:])
    ans -= s
    S2 = [s]*(N+1)
    for i in range(N):
        c = A[2*N-i-1]
        if -h2[0] > c:
            S2[N-i-1] = S2[N-i] + heappop(h2) + c
            heappush(h2, -c)
        else:
            S2[N-i-1] = S2[N-i]

    # print(S1, S2)
    for s1, s2 in zip(S1, S2):
        ans = max(ans, s1-s2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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

SUM = 0

""" 前半 """
left = a[:N]
SUM += sum(left)
heapify(left)

""" 後半 """
# 除外候補リスト
delete = [(i,a[i]) for i in range(N,3*N)]
delete.sort(key=lambda x:-x[1])

right = []
heapify(right)
for _ in range(N):
    tmp = delete.pop()
    SUM -= tmp[1]
    heappush(right, tmp)

def main(SUM):
    ans = SUM
    for i in range(N,2*N):
        # 前半
        tmp = heappop(left)
        if a[i] > tmp:
            SUM += a[i] - tmp
            heappush(left, a[i])
        else:
            heappush(left, tmp)
        
        # 後半
        tmp = heappop(right)
        if i == tmp[0]:
            while delete:
                sub = delete.pop()
                if i < sub[0]:
                    break
            SUM += tmp[1] - sub[1]
            heappush(right, sub)
        else:
            heappush(right, tmp)

        ans = max(ans, SUM)

    print(ans)

if __name__ == "__main__":
    main(SUM)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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

SUM = 0

""" 前半 """
left = a[:N]
SUM += sum(left)
heapify(left)

""" 後半 """
delete = [(i,a[i]) for i in range(N,3*N)]
delete.sort(key=lambda x:-x[1])
right = []
heapify(right)
for _ in range(N):
    tmp = delete.pop()
    SUM -= tmp[1]
    heappush(right, tmp)

ans = SUM
for i in range(N,2*N):
    # 前半
    tmp = heappop(left)
    if a[i] > tmp:
        SUM += a[i] - tmp
        heappush(left, a[i])
    else:
        heappush(left, tmp)
    
    # 後半
    tmp = heappop(right)
    if i == tmp[0]:
        while delete:
            sub = delete.pop()
            if i < sub[0]:
                break
        SUM += tmp[1] - sub[1]
        heappush(right, sub)
    else:
        heappush(right, tmp)

    ans = max(ans, SUM)

print(ans)

Submission status: Accepted

Solution code:
from heapq import *
N, = map(int, input().split())
A = list(map(int, input().split()))
s = sum(A[:N])
rs = [s] + [0] * N
l = []
for i in range(N):
    heappush(l, A[i])
for i in range(N, 2*N):
    s += A[i]
    heappush(l, A[i])
    x = heappop(l)
    s -= x
    rs[i-N+1] = s
l2 = []
s2 = 0
for i in range(2*N, 3*N):
    heappush(l2, -A[i])
    s2+=A[i]

rs2 = [0] * N + [s2]
for i in range(2*N-1, N-1, -1):
    s2 += A[i]
    heappush(l2, -A[i])
    x = -heappop(l2)
#    print(A[i])
#    print(x)
    s2 -= x
    rs2[i-N] = s2
#print(rs2)
r = -10**18
for i in range(N+1):
    c = rs[i] - rs2[i]
    r = max(c, r)
print(r)

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()]
    Type = [False] * (3 * N)
    Front, Back = [], []
    heapify(Front)
    heapify(Back)
    sumA = 0
    sumB = 0
    for i in range(N):
        heappush(Front, A[i])
        sumA += A[i]
    for i in range(N, 3*N):
        heappush(Back, (A[i], i))
    for i in range(N):
        bV, bI = heappop(Back)
        Type[bI] = True
        sumB += bV
    ans = sumA - sumB
    for i in range(N, 2*N):
        heappush(Front, A[i]) #前半の処理
        sumA += A[i]
        sumA -= heappop(Front)
        #後半の処理、境界条件
        newBack, newBackI = heappop(Back)
        if Type[i]:
            sumB -= A[i]
            while newBackI <= i: newBack, newBackI = heappop(Back)
            sumB += newBack
            Type[newBackI] = True
        elif newBackI > i: heappush(Back, (newBack, newBackI))
        ans = max(ans, sumA - sumB)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import heapq

li = []
li2 = []
n = int(input())
a = list(map(int, input().split()))

first = sum(a[:n])
last = sum(a[2*n:])

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

sd = []
sd.append(first)

for i in range(n):
    heapq.heappush(li,a[n+i])
    s = heapq.heappop(li)
    first = first + a[n+i] - s
    sd.append(first)
    
la = []
la.append(last)

for i in range(n):
    heapq.heappush(li2,-a[2*n-1-i])
    s = heapq.heappop(li2)
    last = last + a[2*n-1-i] + s
    la.append(last)

ans = -11451419198104545364364    

for i in range(n+1):
    ans = max(ans , sd[i]-la[n-i])
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_minus = list(map(lambda x: -x, a))
    a_bef, a_aft = a[:n], a_minus[-n:]
    a_bef_sum, a_aft_sum = {n: sum(a_bef)}, {2 * n: -sum(a_aft)}

    heapq.heapify(a_bef)
    heapq.heapify(a_aft)
    for i in range(n):
        bef_key = n + i
        heapq.heappush(a_bef, a[bef_key])
        a_bef_sum[bef_key+1] = a_bef_sum[bef_key] - heapq.heappop(a_bef) + a[bef_key]

        aft_key = n * 2 - i - 1
        heapq.heappush(a_aft, a_minus[aft_key])
        a_aft_sum[aft_key] = a_aft_sum[aft_key+1] + heapq.heappop(a_aft) + a[aft_key]

    ans = - pow(10, 15)
    for i in range(n + 1):
        diff = a_bef_sum[n+i] - a_aft_sum[n+i]
        if diff > ans:
            ans = diff
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
f=a[:n]
heapq.heapify(f)
b=[-i for i in a[2*n:]]
heapq.heapify(b)
maxi=sum(f)
mini=-sum(b)
fmax=[0]*(n+1)
fmax[0]=maxi
bmin=[0]*(n+1)
bmin[n]=mini
for i in range(n):
  heapq.heappush(f,a[n+i])
  fa=heapq.heappop(f)
  maxi+=a[n+i]-fa
  fmax[i+1]=maxi
  heapq.heappush(b,-a[2*n-1-i])
  ba=-heapq.heappop(b)
  mini+=a[2*n-1-i]-ba
  bmin[n-i-1]=mini
ans=-float('inf')
for i in range(n+1):
  ans=max(ans,fmax[i]-bmin[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import numpy as np
input = sys.stdin.readline
N = int(input())
a = [int(x) for x in input().strip().split()]
a_a = a[:N]
sum_a_a = sum(a_a)
a_b = [-1 * i for i in a[-N:]]
sum_a_b = -sum(a_b)
l = [0] * (N + 1)
l[0] = sum_a_a
l[-1] = -sum_a_b
heapq.heapify(a_a)
heapq.heapify(a_b)
for i in range(N):
    t = heapq.heappop(a_a)
    sum_a_a = sum_a_a - t + max(t, a[N+i])
    heapq.heappush(a_a, max(t, a[N+i]))
    l[i+1] += sum_a_a
    t = -heapq.heappop(a_b)
    sum_a_b = sum_a_b - t + (min(t, a[-1-N-i]))
    heapq.heappush(a_b, max(-t, -1*a[-1-N-i]))
    l[-2-i] -= sum_a_b

print(max(l))

Submission status: Accepted

Solution code:
import heapq as hq
N = int(input())
a = list(map(int,input().split()))
heap = a[:N].copy()
hq.heapify(heap)
s = sum(heap)
ls = [s]
for k in range(N,2*N):
    x = hq.heappushpop(heap, a[k])
    s = s + a[k] - x
    ls.append(s)
heap = [-x for x in a[2*N:]]
hq.heapify(heap)
s = sum(heap)
rs = [s]
for k in range(2*N-1, N-1, -1):
    x = hq.heappushpop(heap,-a[k])
    s = s - a[k] - x
    rs.append(s)
print(max([ls[k] + rs[-k-1] for k in range(N+1)]))

Submission status: Accepted

Solution code:

def solve():
    from heapq import heapify, heappush, heappop

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

    before = A[:N]
    after = [-n for n in A[N * 2:]]
    bes = sum(before)
    afs = sum(after)
    
    heapify(before)
    heapify(after)
    
    result = [0] * (N + 1)
    result[0] = bes
    result[-1] = afs
    
    for i in range(N, N * 2):
        a = A[i]
        heappush(before, a)
        k = heappop(before)
        bes += a - k
        result[i-N+1] += bes
    
    for i in range(N * 2 - 1, N - 1, -1):
        # print(i, i - N)
        a = -A[i]
        heappush(after, a)
        k = heappop(after)
        afs += a - k
        result[i - N] += afs

    return max(result)

print(solve())

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop
from itertools import accumulate

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

L, C, R = A[:N], A[N:2 * N], A[2 * N:]

heapify(L)
F = accumulate([sum(L)] + [c - heappushpop(L, c) for c in C])

R = [-r for r in R]
heapify(R)
B = reversed(list(accumulate([sum(R)] + [- c - heappushpop(R, -c) for c in reversed(C)])))

print(max(f + b for f, b in zip(F, B)))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush


class MaxHeap:
    def __init__(self, li):
        self.hp = []
        for e in li:
            heappush(self.hp, -e)

    def push(self, x):
        heappush(self.hp, -x)

    def pop(self):
        ret = heappop(self.hp)
        ret *= -1
        return ret

    def seak(self):
        return -self.hp[0]

    def sum(self):
        return -sum(self.hp)


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

f = a[:n]
s = a[n:2*n]
t = a[2*n:]

heapify(f)
t = MaxHeap(t)

f_sm = sum(f)
f_sm_li = [f_sm]
for e in s:
    heappush(f, e)
    f_sm += e
    pp = heappop(f)
    f_sm -= pp
    f_sm_li.append(f_sm)

t_sm = t.sum()
t_sm_li = [t_sm]
for e in s[::-1]:
    t.push(e)
    t_sm += e
    pp = t.pop()
    t_sm -= pp
    t_sm_li.append(t_sm)

t_sm_li = t_sm_li[::-1]
ans = -float("inf")
for ef, et in zip(f_sm_li, t_sm_li):
    ans = max(ans, ef - et)

print(ans)

Submission status: Accepted

Solution code:
import bisect
import heapq
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
a_left = sorted(a[:N])
a_right = sorted(a[2*N:])
sum_left = sum(a_left)
sum_right = sum(a_right)
#res = sum_left - sum_right
res = sum_left - sum(sorted(a[N:])[:N])
a_right = [-elem for elem in a_right]
heapq.heapify(a_right)
heapq.heapify(a_left)
sr = [0]*(N+1)
sr[0] = sum_right

for i,elem in enumerate(reversed(a[N:2*N])):
    now = -heapq.heappop(a_right)
    if now > elem:
        heapq.heappush(a_right, -elem)
        sum_right += (elem-now)
    else:
        heapq.heappush(a_right, -now)
    sr[i+1] = sum_right

for i,elem in enumerate(a[N:2*N]):
    now = heapq.heappop(a_left)
    if now < elem:
        heapq.heappush(a_left, elem)
        sum_left += (elem-now)
    else:
        heapq.heappush(a_left, now)
    res = max(res, sum_left-sr[N-i-1])
print(res)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp1,dp2=[0]*(n+1),[0]*(n+1)
from heapq import heappop,heappush
q1,q2=[],[]
for i in range(2*n):
  heappush(q1,a[i])
  heappush(q2,-a[-i-1])
  if i<n:
    dp1[0]+=a[i]
    dp2[-1]+=a[-i-1]
  else:
    dp1[i-n+1]=dp1[i-n]+a[i]-heappop(q1)
    dp2[n-i-2]=dp2[n-i-1]+a[-i-1]+heappop(q2)
print(max([dp1[i]-dp2[i] for i in range(n+1)]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq

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

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

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

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

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

# print(red)
# print(blue)
res = red[0] - blue[-1]
for i in range(n+1):
    res = max(res, red[i] - blue[-1-i])

print(res)

Submission status: Accepted

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        N = len(init_val)
        self.num = 2**(N-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(N):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted([(a, i) for i, a in enumerate(A)], key=lambda x:x[0])
z = dict()
for i, (b, j) in enumerate(B):
    z[(b, j)] = i

ss = SegTree([3*N]*3*N, 3*N, min)
bs = []
y = 0
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[(x, i)], z[(x, i)])
    y += x
    if i < N-1:
        continue
    if i == N-1:
        bs.append(y)
    else:
        mx = ss.query(0, 3*N)
        y = y - B[mx][0]
        ss.update(mx, 3*N)
        bs.append(y)

ss = SegTree([-1]*3*N, -1, max)
nbs = []
#tmp = set()
y = 0
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[(x, 3*N-i-1)], z[(x, 3*N-i-1)])
#    tmp.add((x, i))
    y += x
    if i < N-1:
        continue
    if i == N-1:
        nbs.append(y)
    else:
        mx = ss.query(0, 3*N)
#        print(max(tmp), B[mx])
#        tmp.remove(max(tmp))
        y = y - B[mx][0]
        ss.update(mx, -1)
        nbs.append(y)

#print(B)
#print(bs)
#print(nbs)
r = -10**18
for i in range(N+1):
    r = max(r, bs[i] - nbs[N-i])
print(r)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = list(map(int, input().split()))
F = A[:N]
M = A[N:2*N]
L = list(map(lambda x: -x, A[2*N:3*N]))
former = sum(F)
latter = -sum(L)
ans = [0] * (N + 1)
ans[0] = former
ans[-1] = -latter

heapq.heapify(F)
heapq.heapify(L)

for i in range(N):
    tmp = heapq.heappushpop(F, M[i])
    former = former - tmp + M[i]
    ans[i+1] += former
    tmp = heapq.heappushpop(L, -M[N-i-1])
    latter = latter + tmp + M[N-i-1]
    ans[N-i-1] -= latter

print(max(ans))

Submission status: Accepted

Solution code:
import itertools
import math
import heapq

N = int(input())
nums = list(map(int,input().split(" ")))

half1 = nums[:N]
middle= nums[N:2 *N]
half2 = nums[2 *N:]
half2  = list(map(lambda x:-x ,half2) )

heapq.heapify(half1)
heapq.heapify(half2)
count = 0
lsum = sum(half1)
rsum = sum(half2)
ruiseki_left = [lsum]
ruiseki_right= [rsum]

for i in range(N):
    head = half1[0]
    if middle[i] > head:
        ruiseki_left.append(ruiseki_left[-1]  - head +  middle[i])
        heapq.heappop(half1)
        heapq.heappush(half1,middle[i])
    else:
        ruiseki_left.append(ruiseki_left[-1] )
middle.reverse()
for i in range(N):
    head = half2[0]
    if middle[i] > head:
        ruiseki_right.append(ruiseki_right[-1]  - head +   (-middle[i]))
        heapq.heappop(half2)
        heapq.heappush(half2,-middle[i])
    else:
        ruiseki_right.append(ruiseki_right[-1])
# print(ruiseki_left)
# print(ruiseki_right)
ans = - (10 **20)
for i in range(N + 1):

    ans = max(ans,ruiseki_left[i] + ruiseki_right[N - i])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

import heapq
N = int(input())
a = list(map(int, input().split()))
ra = -np.array(a[::-1])

def serchPop(alst):
    h = []
    total = []
    sum = 0
    for i in range(2 * N):
        heapq.heappush(h, alst[i])
        sum += alst[i]
        if i >= N:
            tmp = heapq.heappop(h)
            sum -= tmp

        if i >= N - 1:
            total.append(sum)

    return total

ans = -10 ** 20
ltotal = serchPop(a)
rtotal = serchPop(ra)
for i in range(N + 1):
    ans = max(ans, ltotal[i] + rtotal[N - i])

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import copy


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


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

sum_h1 = [0] * (N+1)
sum_h2 = [0] * (N+1)

'''
N=2
0 1 2 3 4 5 6
3 1 4 1 5 9
'''

h1 = A[0:N]
h2 = A[N*2:N*3]

heapq.heapify(h1)
heapq._heapify_max(h2)

#print("h1", h1)
#print("h2", h2)
sum_h1[0] = sum(h1)
sum_h2[N] = sum(h2)

for k in range(N):
    #print("A[N+k]", A[N+k])
    #print("k+1", k+1)

    sum_h1[k+1] = sum_h1[k]
    sum_h1[k+1] += A[N+k]
    a = heapq.heappushpop(h1, A[N+k])
    sum_h1[k+1] -= a

    #sum_h1[k+1] = sum(h1)

    #print("A[2*N-k-1]", A[2*N-k-1])
    #print("N-k-1", N-k-1)

    sum_h2[N-k-1] = sum_h2[N-k]
    sum_h2[N-k-1] += A[2*N-k-1]
    _heappush_max(h2, A[2*N-k-1])
    sum_h2[N-k-1] -= _heappop_max(h2)

    #sum_h2[N-k-1] = sum(h2)


mx = None

#print("sum_h1", sum_h1)
#print("sum_h2", sum_h2)

for i in range(N+1):
    a = sum_h1[i] - sum_h2[i]

    if(mx == None or a > mx):
        mx = a

print(mx)

'''
for i in range(N+1):
    h1 = A[0:N+i]
    h2 = A[N+i:N*3]

    heapq.heapify(h1)
    heapq._heapify_max(h2)

    for k in range(N):
        if i <= k:
            _heappop_max(h2)
        else:
            heapq.heappop(h1)

    s = sum(h1) - sum(h2)

    if (mx == None or s > mx):
        mx = s
'''

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop

N = int(input())

A = list(map(int, input().split()))
lsum = [0] * (N + 1)
rsum = [0] * (N + 1)
lq = []
rq = []
ans = [0] * (N + 1)

for i in range(N):
    a = A[i]
    heappush(lq, a)
    lsum[0] += a

    b = A[3 * N - 1 - i]
    heappush(rq, -1 * b)
    rsum[N] += b

for k in range(1, N + 1):
    na = A[N - 1 + k]
    lsum[k] = lsum[k - 1] + na - heappushpop(lq, na)

    nb = A[2 * N - k]
    rsum[N - k] = rsum[N - k + 1] + nb - (-1) * heappushpop(rq, -1 * nb)

for i in range(N + 1):
    ans[i] = lsum[i] - rsum[i]

print(max(ans))

Submission status: Accepted

Solution code:
import heapq 
n = int(input())
a = list(map(int, input().split()))
f_ans = [0]*(n+1)
b_ans = [0]*(n+1)

def f_sum():
  f = a[:n]
  heapq.heapify(f)
  foward_sum = sum(f)
  f_ans[0] = foward_sum
  for i in range(n, 2*n):
    heapq.heappush(f, a[i])
    foward_sum = foward_sum + a[i] - heapq.heappop(f)
    f_ans[i-n+1] = foward_sum

def b_sum():
  b = a[2*n:]
  backward_sum = sum(b)  
  b = [-1*i for i in b]
  heapq.heapify(b)
  b_ans[-1] = backward_sum
  for i in range(2*n-1, n-1, -1):
    heapq.heappush(b, -a[i])
    backward_sum = backward_sum + a[i] + heapq.heappop(b)
    b_ans[i-n] = backward_sum
    

f_sum()
b_sum()
ans = -float('inf')
for i in range(len(f_ans)):
  f = f_ans[i]
  b = b_ans[i]
  ans = max(ans, f-b)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heapify, heappush

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

a_front = a[0 : n]
a_back = list(map(lambda x: -1*x, a[2*n : 3*n]))
heapify(a_front)
heapify(a_back)

sum_f = [0]*(n+1)
sum_b = [0]*(n+1)
sum_f[0] = sum(a_front)
sum_b[n] = sum(a_back)*-1

for i in range(n, 2*n):
    # 前半の処理
    heappush(a_front, a[i])
    sum_f[i-n+1] = sum_f[i-n] + a[i] - heappop(a_front)
    # 後半の処理
    heappush(a_back, -1 * a[3*n-i-1])
    sum_b[2*n-i-1] = sum_b[2*n-i] + a[3*n-i-1] + heappop(a_back)

ans = sum_f[0] - sum_b[0]
for i in range(1, n+1):
    tmp = sum_f[i] - sum_b[i]
    if tmp > ans:
        ans = tmp
        
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq
def main():
    N = int(input())
    a = [int(x) for x in input().split()]
    left = [0]*(N+1)
    left_a = a[:N]
    left[0] = sum(left_a)

    heapq.heapify(left_a)
    for i in range(1,N+1):
        now = heapq.heappop(left_a)

        if now<a[N-1+i]:
            heapq.heappush(left_a,a[N-1+i])
            left[i] = left[i-1]+a[N-1+i]-now
        else:
            heapq.heappush(left_a,now)
            left[i] = left[i-1]
    
    right = [0]*(N+1)
    right_a = [-int(x) for x in a[2*N:]]
    right[-1] = -sum(right_a)
    
    heapq.heapify(right_a)
    for i in range(N):
        now = -1 * heapq.heappop(right_a)
        if now>a[2*N-1-i]:
            heapq.heappush(right_a,-a[2*N-1-i])
            right[N-i-1] = right[N-i]-now+a[2*N-1-i]
        else:
            heapq.heappush(right_a,-now)
            right[N-i-1] = right[N-i]

    ans = -1 * float("inf")
    for i in range(len(left)):
        ans = max(ans,left[i]-right[i])
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappushpop, heapify

N,*A = map(int,read().split())

def from_left(A):
    q = A[:N]
    S = sum(q)
    heapify(q)
    B = [0] * (N+N+N)
    B[N-1] = S
    for i,x in enumerate(A[N:],N):
        S += x
        S -= heappushpop(q,x)
        B[i] = S
    return B

L = from_left(A)
R = [-x for x in from_left([-x for x in A[::-1]])[::-1]]

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

Submission status: Accepted

Solution code:
import heapq

N = int(input())
arr = list(map(int,input().split()))
hq_l = arr[:N]
hq_r = list(map(lambda x:x*(-1),arr[-N:]))
heapq.heapify(hq_l)
heapq.heapify(hq_r)

l_sum = [0]*(N+1)
l_sum[0] = sum(hq_l)
r_sum = [0]*(N+1)
r_sum[-1] = -sum(hq_r)

for i in range(1,N + 1):
    heapq.heappush(hq_l,arr[N-1+i])
    a = heapq.heappop(hq_l)
    l_sum[i] = l_sum[i-1] + arr[N-1+i] - a
    heapq.heappush(hq_r,-arr[2*N-i])
    a = -heapq.heappop(hq_r)
    r_sum[-1-i] = r_sum[-i] + arr[2*N-i] - a

ans = -float('inf')
for l,r in zip(l_sum,r_sum):
    ans = max((l-r),ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import heapq
    n=int(input())
    a=list(map(int,input().split()))
    h=a[:n]
    dp1=[sum(h)]
    heapq.heapify(h)
    for i in range(n):
        j=heapq.heappop(h)
        if a[n+i]>j:
            dp1.append(dp1[-1]+a[n+i]-j)
            heapq.heappush(h,a[n+i])
        else:
            dp1.append(dp1[-1])
            heapq.heappush(h,j)
    h=[-i for i in a[2*n:]]
    dp2=[sum(h)]
    heapq.heapify(h)
    for i in range(n):
        j=heapq.heappop(h)
        if -a[2*n-i-1]>j:
            dp2.append(dp2[-1]-a[2*n-i-1]-j)
            heapq.heappush(h,-a[2*n-i-1])
        else:
            dp2.append(dp2[-1])
            heapq.heappush(h,j)
    dp2=dp2[::-1]
    print(max([dp1[i]+dp2[i] for i in range(n+1)]))
main()