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 heapq
N = int(input())
a = [int(i) for i in input().split()]

before = []
after = []
before_sum = 0
after_sum = 0
for i in range(N):
    heapq.heappush(before, a[i])
    before_sum += a[i]

for i in range(2*N, 3*N):
    heapq.heappush(after, -a[i])
    after_sum -= a[i]

c = [0] * (N+1)
c[0] = before_sum
c[N] = after_sum
for i in range(N):
    before_sum = before_sum - heapq.heappushpop(before, a[N+i]) + a[N+i]
    c[i+1] += before_sum
    after_sum = after_sum - heapq.heappushpop(after, -a[(2*N)-i-1]) - a[(2*N)-i-1]
    c[N-i-1] += after_sum

print(max(c))

Submission status: Accepted

Solution code:
def d_3n_numbers(N, A):
    import heapq
    left = A[:N]
    heapq.heapify(left)
    # heappopはキューの最小値を取り出すが、rightからは最大値を取り出したいので-1を掛ける
    # 後にマイナスが付いているところは、それの帳尻を合わせている
    right = [-i for i in A[2 * N:]]
    heapq.heapify(right)

    # 最初、leftには数列の先頭N個が、rightには末尾N個が格納されている
    # 数列のN番目から2N番目まで順に、leftに格納して最小値を捨てることを繰り返す
    # 数列の2N番目からN番目まで順に、rightに格納して最大値を捨てることを繰り返す
    left_sum = [sum(left)]
    right_sum = [-sum(right)]
    for k in range(N, 2 * N):
        heapq.heappush(left, A[k])
        v = heapq.heappop(left)
        left_sum.append(left_sum[-1] + A[k] - v)
    for k in range(2 * N - 1, N - 1, -1):
        heapq.heappush(right, -A[k])
        v = heapq.heappop(right)
        right_sum.append(right_sum[-1] + A[k] - (-v))

    score = [a - b for a, b in zip(left_sum, right_sum[::-1])]
    return max(score)

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

Submission status: Accepted

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

def main():
    input = sys.stdin.readline
    N = int(input())

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

    F = [0 for _ in range(N+1)]
    B = [0 for _ in range(N+1)]
    F[0] = sum(A[:N])
    B[N] = sum(A[2*N:])

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

    for i in range(1, N+1):
        F[i] = F[i-1] + A[N-1+i] - heappushpop(Ffactors, A[N-1+i])
        B[N-i] = B[N+1-i] + A[2*N-i] + heappushpop(Bfactors, -A[2*N-i])

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

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,heapq
#これを加える！！！！
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,input().split()))

res = [0]*(n+1)
head = a[:n:]
heapq.heapify(head)
p = sum(head)
for i in range(n+1):
    res[i] = p
    p += a[n+i]
    heapq.heappush(head,a[n+i])
    p -= heapq.heappop(head)
end = a[2*n::]
heapq._heapify_max(end)
q = sum(end)
for i in range(n+1):
    res[n-i] -= q
    q += a[2*n-1-i]
    _heappush_max(end,a[2*n-1-i])
    q -= _heappop_max(end)
print(max(res))

Submission status: Accepted

Solution code:
import heapq


class PriorityQueue:
    def __init__(self):
        self.__heap = []
        self.__count = 0

    def empty(self) -> bool:
        return self.__count == 0

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        self.__count -= 1
        return heapq.heappop(self.__heap)

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__heap, v)

    def __len__(self):
        return self.__count


def _3N_numbers(N: int, A: list)->int:
    # first half
    q = PriorityQueue()
    first_half = [0] * (N+1)
    for i in range(N):
        q.enqueue(A[i])
        first_half[0] += A[i]

    for k in range(N):
        q.enqueue(A[N+k])
        decrement = q.dequeue()
        first_half[k+1] = first_half[k] - decrement + A[N+k]

    # second half
    q = PriorityQueue()
    second_half = [0] * (N+1)
    for i in range(N):
        q.enqueue(-A[3*N-1-i])
        second_half[N] += A[3*N-1-i]

    for k in range(N):
        q.enqueue(-A[2*N-1-k])
        decrement = -q.dequeue()
        second_half[N-(k+1)] = second_half[N-k] - decrement + A[2*N-1-k]

    return max(f - s for f, s in zip(first_half, second_half))


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _3N_numbers(N, A)
    print(ans)

Submission status: Accepted

Solution code:
import heapq

n = int(input())

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

func = lambda p: p * (-1)

b = list(map(func,a[:]))

#print(a)
#print(b)

l = [0] * (3*n)

first = a[0:n]
second = b[2*n:3*n]

x = [0] * (3*n)
y = [0] * (3*n)

x[n-1] = sum(first)
y[2*n-1] = sum(second)

heapq.heapify(first)
heapq.heapify(second)

for i in range(n,2*n):
    heapq.heappush(first, a[i])
    s = first[0]
    heapq.heappop(first)
    x[i] = x[i-1] + a[i] - s

for i in range(n,2*n):
    heapq.heappush(second, b[-i-1])
    t = second[0]
    heapq.heappop(second)
    y[-i-2] = y[-i-1] + b[-i-1] - t
    
for i in range(n-1,2*n):
    l[i] = x[i] + y[i]
    
#print(x)
#print(y)
#print(l)

print(max(l[n-1:2*n]))

Submission status: Accepted

Solution code:
import heapq

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

ante, post = alist[:n], alist[-n:]
antesums = [0 for _ in range(n+1)]
postsums = [0 for _ in range(n+1)]
antesums[0] = sum(ante)
postsums[0] = sum(post)
post = list(map(lambda x: -x, post))
heapq.heapify(ante)
heapq.heapify(post)

for k in range(n):
  minante = heapq.heappushpop(ante, alist[n+k])
  antesums[k+1] = antesums[k] + alist[n+k] - minante
  maxpost = heapq.heappushpop(post, -alist[2*n-k-1])
  postsums[k+1] = postsums[k] + alist[2*n-k-1] + maxpost

ans = -sum(alist)
for k in range(n+1):
  if ans < antesums[k] - postsums[-k-1]:
    ans = antesums[k] - postsums[-k-1]
print(ans)

Submission status: Accepted

Solution code:
import heapq
import copy
N = int(input())
a = list(map(int,input().split()))
leftHeap = copy.copy(a[0:N])
rightHeap = [-a[i] for i in range(2*N,3*N)]
heapq.heapify(leftHeap)
heapq.heapify(rightHeap)
leftSideTakenSum = [0] #take smallest i num from left [0,N+i) 
rightSideTakenSum = [0] #take largest i num from right [2*N-i, 3*N)
for i in range(1,N+1):
  left = heapq.heappushpop(leftHeap,a[N+i-1])
  right = -heapq.heappushpop(rightHeap,-a[2*N-i])
  leftSideTakenSum.append(leftSideTakenSum[i-1]+left)
  rightSideTakenSum.append(rightSideTakenSum[i-1]+right)

leftSideSum = 0
for i in range(N):
  leftSideSum += a[i]
totalSum = sum(a)
rightSideSum = totalSum - leftSideSum
answer = -totalSum
for i in range(N+1):
  candidate = leftSideSum - leftSideTakenSum[i] - (rightSideSum - rightSideTakenSum[N-i])
  #print(i,N+i,leftSideSum,rightSideSum,candidate)
  answer = max(answer,candidate)
  leftSideSum += a[N+i]
  rightSideSum -= a[N+i]
print(answer)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
a = list(map(int, input().split()))
a1 = a[:N]
a2 = [-x for x in a[2 * N:]]
sum1, sum2 = sum(a1), -sum(a2)
heapq.heapify(a1)
heapq.heapify(a2)
s1, s2 = [sum1], [sum2]
for i in range(N):
    heapq.heappush(a1, a[N + i])
    m = heapq.heappop(a1)
    if a[N + i] > m:
        sum1 += a[N + i] - m
    s1.append(sum1)
    heapq.heappush(a2, -a[2 * N - 1 - i])
    m = -heapq.heappop(a2)
    if a[2 * N - 1 - i] < m:
        sum2 += a[2 * N - 1 - i] - m
    s2.append(sum2)
ans = -float("inf")
for i in range(N + 1):
    if ans < s1[i] - s2[N - i]:
        ans = s1[i] - s2[N - i]
print(ans)

Submission status: Accepted

Solution code:
import heapq


def main():
    N = int(input())
    A = list(map(int, input().split()))
    X = [0] * (N+1)
    X[0] = sum(A[:N])
    Y = [0] * (N+1)
    Y[0] = sum(A[2*N:])
    h = A[:N]
    heapq.heapify(h)
    for i in range(N):
        heapq.heappush(h, A[N + i])
        minimum = heapq.heappop(h)
        X[i+1] = X[i] + A[N + i] - minimum
    h = [-x for x in A[2*N:]]
    heapq.heapify(h)
    for i in range(N):
        heapq.heappush(h, -A[2*N-1 - i])
        maximum = -heapq.heappop(h)
        Y[i+1] = Y[i] + A[2*N-1 - i] - maximum
    ans = - float("inf")
    for i in range(N+1):
        ans = max(ans, X[i] - Y[N-i])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def f(a):
 q=a[:n];s=sum(q);heapify(q);yield s
 for e in a[n:2*n]:s+=e-heappushpop(q,e);yield s
from heapq import*;r=reversed;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),r(list(f([-e for e in r(a)])))))))

Submission status: Accepted

Solution code:
import heapq

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

p = [0] * (n + 1)
q = [] + p

L = []
R = []
C = [] + a[n:n * 2]

for i in range(n):
    heapq.heappush(L, a[i])
    heapq.heappush(R, - a[n * 2 + i])

p[0] = sum(L)
q[n] = sum(R)
for i in range(n):
    if C[i] > L[0]:
        p[i + 1] = p[i] + C[i] - L[0]
        heapq.heappop(L)
        heapq.heappush(L, C[i])
    else:
        p[i + 1] = p[i]

    temp = C[n - 1 - i] * -1
    if temp > R[0]:
        q[n - 1 - i] = q[n - i] + temp - R[0]
        heapq.heappop(R)
        heapq.heappush(R, temp)
    else:
        q[n - 1 - i] = q[n - i]

ans = p[n] + q[n]
for i in range(n):
    ans = max(ans, p[i] + q[i])

print(ans)

Submission status: Accepted

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


left_seq = sorted(a[0:n])
right_seq =  sorted(a[2*n:3*n],reverse=True)
for i in range(n):
  right_seq[i]=-right_seq[i]

#print(left_seq)
#print(right_seq)

#left_sum[i]はa_0からa_(n+i-1)までaのうち、大きいものをn個集めたときの和
#right_sum[i]はa_(n+i)からa_(3n-1)までaのうち、小さいものをn個集めたときの和
left_sum = [0]*(n+1)
right_sum = [0]*(n+1)
left_sum[0] =  sum(left_seq) 
right_sum[n] =  sum(right_seq) 

#print(left_seq)
for i in range(n):
  if left_seq[0]<a[n+i]:
    left_sum[i+1] = left_sum[i] + a[n+i] - left_seq[0]
    heapq.heappop(left_seq)
    heapq.heappush(left_seq, a[n+i])
  else:
    left_sum[i+1] = left_sum[i]
  #print(left_seq,left_sum[i+1],i+1)
  
#print(right_seq)
for i in range(n)[::-1]:
  if right_seq[0]<-a[n+i]:
    right_sum[i] = right_sum[i+1] + (-a[n+i]) - right_seq[0]
    #print(right_seq)
    heapq.heappop(right_seq)
    heapq.heappush(right_seq, -a[n+i])
    #print(right_seq)
  else:
    right_sum[i] = right_sum[i+1]
  #print(right_seq,right_sum[i],i)

ans = -float("inf")
for i in range(n+1):
  #print(left_sum[i],right_sum[i],left_sum[i]+right_sum[i])
  ans = max(ans,left_sum[i]+right_sum[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

sum1 = 0
sum2 = 0
left = []
used = set()
unused = []

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


for v, i in sorted((a[i], i) for i in range(n, n * 3)):
    if len(used) < n:
        sum2 += v
        used.add((v, i))
    else:
        heapq.heappush(unused, (v, i))

ans = sum1 - sum2
for i in range(n, 2 * n):
    # v1: これから挿入しようとしている値
    # v2: 現状の最小値
    v1 = a[i]
    v2, j = left[0]
    if v2 < v1:
        sum1 = sum1 + v1 - v2
        heapq.heappop(left)
        heapq.heappush(left, (v1, i))

    # v1: これから削除する可能性がある値
    # v2: 候補のうちで最小の値
    while True:
        v2, j = unused[0]
        if i <= j:
            break
        heapq.heappop(unused)
        
    if (v1, i) in used:
        sum2 = sum2 - v1 + v2
        used.remove((v1, i))
        used.add((v2, j))
        heapq.heappop(unused)

    ans = max(ans, sum1 - sum2)

print(ans)

Submission status: Accepted

Solution code:
# ABC062
# https://atcoder.jp/contests/abc062/tasks/arc074_b

# 方針
# 数列のなかで左から1個目のものをx=1とする(1<=x<=3N)
# このとき点P(x=p,N<=p<=2N)をおき、pを動かして考える

# A = (a1,a2,a3..apの中から大きいものN個の和)
# B = (a(p+1),a(p+2)..a(3n)の中から小さいものN個の和) とすると
# 求めたいのは A-B
# pを動かしてA-Bの最大値を求めればそれが答えになる

# 愚直に実装するとO(N^2)であるためTLE

# プライオリティキューを用いることによりO(N)で実装できる
# pがインクリメントされる毎に
# A -> 一番小さい値をpop
# B -> 一番大きい値をpop すれば良い

from heapq import heappush,heappop

N=int(input())
*a,=map(int,input().split())
a=[0]+a

A,B=0,0
As,Bs=[None]*(3*N+1),[None]*(3*N+1)
l,r=[],[]

for p in range(1,N+1):
    heappush(l,a[p])
A=sum(l)
As[N]=A
for p in range(N+1,2*N+1):
    heappush(l,a[p])
    b=heappop(l)
    A=A+a[p]-b
    As[p]=A

for p in range(2*N+1,3*N+1)[::-1]:
    heappush(r,-a[p])
B=-sum(r)
Bs[2*N+1]=B
for p in range(N+1,2*N+1)[::-1]:
    heappush(r,-a[p])
    b=heappop(r)
    B=B+a[p]+b
    Bs[p]=B
    
ans=max(As[p]-Bs[p+1] for p in range(N,2*N+1))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

r=[None]*(3*N)
s=[None]*(3*N)
p=[]
q=[]
ans=-float("inf")

for i in range(N):
    heappush(p,a[i])
v=sum(p)
r[N-1]=v
for i in range(N,2*N):
    heappush(p,a[i])
    b=heappop(p)
    v=v+a[i]-b
    r[i]=v

for i in range(2*N,3*N)[::-1]:
    heappush(q,-a[i])
v=sum(q)
s[2*N]=-v
for i in range(N,2*N)[::-1]:
    heappush(q,-a[i])
    b=heappop(q)
    v=v-a[i]-b
    s[i]=-v

for i in range(N-1,2*N):
    ans=max(ans,r[i]-s[i+1])

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

hq = a[0: N]
left_max = [sum(hq)]
heapq.heapify(hq)
for i in range(N):
    left_max.append(left_max[i] + a[N + i] - heapq.heappushpop(hq, a[N + i]))

hq = [-i for i in a[2 * N: 3 * N]]
right_min = [-sum(hq)]
heapq.heapify(hq)
for i in range(N):
    right_min.append(right_min[i] + a[2 * N - i - 1] + heapq.heappushpop(hq, -a[2 * N - i - 1]))

ans = -100000000000000
for i in range(N + 1):
    ans = max(ans, left_max[i] - right_min[N - i])

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
n = int(input())
a = input().split()
a = [int(m) for m in a]
t1 = []
t2 = []
mt3 = []
for i in range(3 * n):
    if i < (3 * n) // 3:
        t1.append(a[i])
    elif (3 * n) // 3 <= i < (3 * n) // 3 * 2:
        t2.append(a[i])
    else:
        mt3.append(-a[i])
t1.sort()
mt3.sort()
t1sumli = [sum(t1)]
t3sumli = [-sum(mt3)]
for i in range(n):
    pp = heappop(t1)
    heappush(t1, max(pp, t2[i]))
    t1sumli.append(t1sumli[-1] - pp + max(pp, t2[i]))

for i in range(n - 1, -1, -1):
    qq = -heappop(mt3)
    heappush(mt3, -min(qq, t2[i]))
    t3sumli.append(t3sumli[-1] - qq + min(qq, t2[i]))

sumli = []
for i in range(n + 1):
    sumli.append(t1sumli[i] - t3sumli[-i-1])
print(max(sumli))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

n = int(input())
lst = list(map(int, input().split()))
preQue = sorted(lst[:n])
mid = lst[n:2*n]
sufQue = sorted([-i for i in lst[2*n:]])

preScore = sum(preQue)
preScores = [preScore]
heapify(preQue)
for i in mid:
    v = heappop(preQue)
    if v < i:
        preScore += (i - v)
        heappush(preQue, i)
    else:
        heappush(preQue, v)
    preScores.append(preScore)

sufScore = sum(sufQue)
sufScores = [sufScore]
heapify(sufQue)
for i in mid[::-1]:
    v = heappop(sufQue)
    if -v > i:
        sufScore += (-v - i)
        heappush(sufQue, -i)
    else:
        heappush(sufQue, v)

    sufScores.append(sufScore)

sufScores.reverse()
ans = max([p + s for p, s in zip(preScores, sufScores)])
print(ans)

Submission status: Accepted

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

al = A[:N]
heapq.heapify(al)
sal = sum(al)
suml = [sal]
for i in range(N, 2*N):
    if al[0] < A[i]:
        tmp = heapq.heappop(al)
        heapq.heappush(al, A[i])
        sal += A[i]-tmp
    suml.append(sal)

ar = [-a for a in A[2*N:]]
heapq.heapify(ar)
sar = -sum(ar)
sumr = [sar]

ans = -10**15
for i in range(N, 2*N):
    if -ar[0] > A[3*N-1-i]:
        tmp = -heapq.heappop(ar)
        heapq.heappush(ar, -A[3*N-1-i])
        sar += A[3*N-1-i]-tmp
    sumr.append(sar)
for i in range(len(suml)):
    ans = max(ans, suml[i]-sumr[-(i+1)])
print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

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

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

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

from heapq import heapify, heappushpop

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

mids = aN[N:N*2]
# とりあえず前後半確定の部分をキューに詰める
L = aN[:N]
R = [-aN[i] for i in range(N*2, N*3)]
heapify(L)
heapify(R)

# 未確定の真ん中1/3について調べていく
l_sum = [0] * (N+1)
l_sum[0] = sum(aN[:N])
for i in range(N):
    # ある値をpushして最小値をpopする
    num = heappushpop(L, mids[i])
    # それに合わせて合計値も更新
    l_sum[i+1] = l_sum[i] + mids[i] - num

# 後半部分は逆方向からやる
r_sum = [0] * (N+1)
r_sum[N] = sum(aN[N*2:])
for i in range(N-1, -1, -1):
    # 正負逆転させれば最大値にも使える
    num = -(heappushpop(R, -mids[i]))
    r_sum[i] = r_sum[i+1] + mids[i] - num

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

Submission status: Accepted

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

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

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

from heapq import heappush, heappushpop

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

mids = aN[N:N*2]
L = []
R = []
for i in range(N):
    # とりあえず前後半確定の部分をキューに詰める
    heappush(L, aN[i])
    heappush(R, -aN[i+N*2])

# 未確定の真ん中1/3について調べていく
l_sum = [0] * (N+1)
l_sum[0] = sum(aN[:N])
for i in range(N):
    # ある値をpushして最小値をpopする
    num = heappushpop(L, mids[i])
    # それに合わせて合計値も更新
    l_sum[i+1] = l_sum[i] + mids[i] - num

# 後半部分は逆方向からやる
r_sum = [0] * (N+1)
r_sum[N] = sum(aN[N*2:])
for i in range(N-1, -1, -1):
    # 正負逆転させれば最大値にも使える
    num = -(heappushpop(R, -mids[i]))
    r_sum[i] = r_sum[i+1] + mids[i] - num

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

Submission status: Accepted

Solution code:
from heapq import heapify,heappush, heappop

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

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


T1=[]
T1.append(sum1)

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


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



T2=[]
T2.append(sum2)

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

	T2.append(sum2)


T2.reverse()


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

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

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

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

M = A[N:2*N]
# 左側
for k in range(N):
    lo = heapq.heappushpop(Left, M[k])
    Left_SUM.append(Left_SUM[-1] + M[k] - lo)

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

# 最大値を計算
ans = max([l - r for l, r in zip(Left_SUM, Right_SUM[::-1])])
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

max_score = - float("inf")

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

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

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

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

Submission status: Accepted

Solution code:
import heapq

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

max_score = - float("inf")

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

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

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

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

Submission status: Accepted

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


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
# keypoint: いちいちsumすると線形時間かかるのでsum_hoge[-1]でアクセスする
for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


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

Submission status: Accepted

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappushpop


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

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

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

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

Submission status: Accepted

Solution code:
import sys
# If available, use C implementation
try:
    from _heapq import heapify, heappushpop
except ImportError:
    from heapq import heapify, heappushpop
try:
    from _heapq import _heapreplace_max
except ImportError:
    pass
try:
    from _heapq import _heapify_max as heapify_max
except ImportError:
    from heapq import _heapify_max as heapify_max
try:
    from _heapq import _siftup_max
except ImportError:
    from heapq import _siftup_max


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


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

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

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

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

Submission status: Accepted

Solution code:
#import sys
from heapq import heapify, heappushpop
from heapq import _heapify_max as heapify_max, _siftup_max


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


# fin = sys.stdin.readline
N, *a_list = map(int, open(0).read().split())

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

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

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

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappushpop
from heapq import _heapify_max as heapify_max, _siftup_max


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


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

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

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

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

Submission status: Accepted

Solution code:
# time complexity: O(NlgN)
# space complexity: O(N)

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

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

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

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


# move partitions and calculate a global maximum
left_sum = sum(left)
heapify(left)
# dirty trick
thrown_away.append(False)
max_score = left_sum - right_sum
for i, item in enumerate(right[:N]):
    if not thrown_away[i]:
        # update right
        updated_idx = -1
        # pick a item which has not moved to the left.
        while thrown_away[updated_idx] == False:
            updated_item, updated_idx = heappop(discarded_items)
        right_sum += updated_item - item
        thrown_away[updated_idx] = False
    else:
        # want to remove item from discarded_items, but it take O(N)
        # instead, set thrown_away[i] = False so as to know this is moved to the left.
        thrown_away[i] = False
    # update left
    if item > left[0]:
        old_item = heappop(left)
        heappush(left, item)
        left_sum += item - old_item
    max_score = max(max_score, left_sum - right_sum)

print(max_score)