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())
a1=[]
b1=[]
a2=[]
b2=[]
s=input().split()
for i in range(3*n):
    if i<n:
        a1.append(int(s[i]))
    elif i>=2*n:
        b1.append(-int(s[i]))
    else:
        a2.append(int(s[i]))
        b2.append(-int(s[3*n-i-1]))
suma=[sum(a1)]
sumb=[sum(b1)]
heapq.heapify(a1)
heapq.heapify(b1)

for i in range(0,n):
    heapq.heappush(a1,a2[i])
    k=heapq.heappop(a1)
    l=suma[-1]
    suma.append(l+a2[i]-k)
for i in range(0,n):
    heapq.heappush(b1,b2[i])
    k=heapq.heappop(b1)
    l=sumb[-1]
    sumb.append(l+b2[i]-k)

ma=-1000000000000000
for i in range(n+1):
    ma=max(ma,suma[i]+sumb[-i-1])
print(ma)

Submission status: Accepted

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

left = a[:n]
right = a[2*n:]
heapify(left)
l = [sum(left)]
r = [sum(right)]
sl = sum(left)
sr = sum(right)
for i in range(n):
    k = heappop(left)
    sl -= k
    heappush(left, max(k, a[n+i]))
    sl += max(k, a[n+i])
    l.append(sl)

right = [-i for i in right]
heapify(right)
for i in range(n):
    k = -heappop(right)
    sr -= k
    mini = min(k, a[2*n-1-i])
    heappush(right, -mini)
    sr += mini
    r.append(sr)

r.reverse()
ans = -10**15
for i in range(n+1):
    ans = max(l[i] - r[i], ans)

print(ans)

Submission status: Accepted

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

import sys
from heapq import heapify, heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A1 = A[:N]
A2 = A[N:]
sm1 = sum(A1)
sm2 = sum(A2)
que1 = []
que2 = []
S = set()
for i, a in enumerate(A1):
    que1.append((a, i))
heapify(que1)
A2 = [(a, i) for i, a in enumerate(A2, N)]
A2.sort(reverse=1)
for a, i in A2[:N]:
    sm2 -= a
    S.add(i)
    que2.append((a, i))
heapify(que2)

ans = sm1 - sm2
for i in range(N, N*2):
    # 前半
    heappush(que1, (A[i], i))
    sm1 += A[i]
    a, _ = heappop(que1)
    sm1 -= a
    # 後半
    if i not in S:
        sm2 -= A[i]
        while 1:
            a, j = heappop(que2)
            S.remove(j)
            if j > i:
                sm2 += a
                break
    ans = max(ans, sm1 - sm2)
print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
n = int(input())
a = list(map(int,input().split()))
x = sum(a[:n])
y = sum(a[2*n:])
fsum = [x]
lsum = [y]
hqx = a[:n]
hqy = [-a[2*n+i] for i in range(n)]
hq.heapify(hqx)
hq.heapify(hqy)
for i in range(n):
    hq.heappush(hqx,a[n+i])
    hq.heappush(hqy,-a[2*n-i-1])
    xmin = hq.heappop(hqx)
    ymax = -hq.heappop(hqy)
    fsum.append(fsum[-1]+a[n+i]-xmin)
    lsum.append(lsum[-1]+a[2*n-i-1]-ymax)
ans = -10**18
for i in range(n+1):
    ans = max(ans,fsum[i]-lsum[-i-1])
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

left = sorted(a[:N])
max_left = [sum(left)]

right = sorted([-x for x in a[-N:]])
min_right = [sum(right) * -1]

for i in range(N, 2 * N):
    j = 3 * N - i - 1

    heappush(left, a[i])
    v = heappop(left)
    max_left.append(max_left[-1] - v + a[i])

    heappush(right, a[j] * -1)
    v = heappop(right) * -1
    min_right.append(min_right[-1] - v + a[j])

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

Submission status: Accepted

Solution code:
import heapq

n = int(input())
a = list(map(int, input().split()))
plus = [sum(a[:n])]
minus = [-sum(a[-n:])]
p = a[:n]
m = [-i for i in a[-n:]]
heapq.heapify(p)
heapq.heapify(m)
for i in range(n,2*n):
  pn = a[i]
  mn = -a[-(i+1)]
  if pn > p[0]:
    plus.append(plus[-1] + pn - heapq.heappop(p))
    heapq.heappush(p, pn)
  else:
    plus.append(plus[-1])
  if mn > m[0]:
    minus.append(minus[-1] + mn - heapq.heappop(m))
    heapq.heappush(m, mn)
  else:
    minus.append(minus[-1])
minus.reverse()
ans = []
for i,j in zip(plus,minus):
  ans.append(i+j)
print(max(ans))

Submission status: Accepted

Solution code:
import heapq

N = int(input())

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

left = A[:N]
left_total = [(sum(left))]
heapq.heapify(left)

for i in range(N, 2*N):
    l = heapq.heappop(left)
    # 入れ替える場合
    if l < A[i]:
        heapq.heappush(left,A[i])
        left_total.append(left_total[-1] - l + A[i])
    # Aのある要素よりleftの最小要素の方が大きいので入れ替えない
    else:
        heapq.heappush(left,l)
        left_total.append(left_total[-1])
        

#rightもN要素から始めるが、leftとの対応のために最後にtotalをひっくり返すのを忘れない
right = [-i for i in A[2 * N:]]
right_total = [sum(right)]
heapq.heapify(right)

for i in reversed(range(N, 2*N)):
    r = heapq.heappop(right)
    if r < -A[i]:
        heapq.heappush(right, -A[i])
        right_total.append(right_total[-1] - r - A[i])
    # rの最小値の方がちいさいのでそのまま
    else:
        heapq.heappush(right, r)
        right_total.append(right_total[-1])


# left_totalとの対応のために逆にする
right_total = right_total[::-1]

ans = -float("inf")
for i in range(len(left_total)):
    ans = max(ans, left_total[i] + right_total[i])

print(ans)

Submission status: Accepted

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

import heapq

lefts = a[:n]
lefts_sums = [sum(lefts)]
heapq.heapify(lefts)

for x in range(n, 2 * n):
    l = heapq.heappop(lefts)
    if l < a[x]:
        heapq.heappush(lefts, a[x])
        lefts_sums.append(lefts_sums[-1] - l + a[x])
    else:
        heapq.heappush(lefts, l)
        lefts_sums.append(lefts_sums[-1])

rights = [-_a for _a in a[2 * n:]]
rights_sums = [sum(rights)]
heapq.heapify(rights)

for x in reversed(range(n, 2 * n)):
    r = heapq.heappop(rights)
    if r < -a[x]:
        heapq.heappush(rights, -a[x])
        rights_sums.append(rights_sums[-1] - r - a[x])
    else:
        heapq.heappush(rights, r)
        rights_sums.append(rights_sums[-1])

rights_sums = rights_sums[::-1]
ans = -float('inf')
for i in range(len(lefts_sums)):
    ans = max(ans, lefts_sums[i] + rights_sums[i])
# print(lefts_sums, rights_sums)
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import *

n, *a = map(int, sys.stdin.read().split())

def optimize(arr):
    res = arr[:n]
    heapify(res)
    sum_arr = [sum(res)]
    for x in arr[n:]:
        y = heappop(res)
        heappush(res, max(x, y))
        sum_arr.append(sum_arr[-1] + max(0, x - y))
    return sum_arr

def main():
    left = a[:n*2]
    right = [-x for x in a[n:]][::-1]

    sum_left = optimize(left)
    sum_right = optimize(right)

    res = []
    for i in range(n+1):
        res.append(sum_left[i] + sum_right[n-i])
        
    ans = max(res)
    return ans

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq

def minus(n):
    return -n

def solve(N: int, a: "List[int]"):
    ## N+iまでのリストの大きい順のNコのわ  
    left_sum = [0]*(N+1)
    heap = a[:N]
    left_sum[0] = sum(heap)
    heapq.heapify(heap)
    for i in range(N,2*N):
        heapq.heappush(heap,a[i])
        min_value = heapq.heappop(heap)
        left_sum[i-(N-1)]=left_sum[i-N]+a[i]-min_value

    b = list(map(minus,reversed(a)))
    right_sum= [0]*(N+1)
    r_heap = b[:N]
    right_sum[0] = -sum(r_heap)
    heapq.heapify(r_heap)
    for i in range(N,2*N):
        heapq.heappush(r_heap,b[i])
        min_value = heapq.heappop(r_heap)
        right_sum[i-(N-1)]=right_sum[i-N]+(-b[i])-(-min_value)
    
    answer = -10**15
    for j in range(N+1):
        answer = max(answer,left_sum[j]-right_sum[N-j])
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(3 * N)]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

a1 = a[:n]
s1 = []
ts = sum(a1)
s1.append(ts)

heapq.heapify(a1)
for i in range(n,n*2):
    ts += a[i]
    heapq.heappush(a1,a[i])
    ts -= heapq.heappop(a1)
    s1.append(ts)

a2 = a[(n*2):]
a2 = list(map(lambda x: x*(-1), a2)) 
s2 = []
ts = sum(a2)
s2.append(ts)

heapq.heapify(a2)
for i in range(n*2-1,n-1,-1):
    ts -= a[i]
    heapq.heappush(a2,a[i] * -1)
    ts -= heapq.heappop(a2)
    s2.append(ts)

res = -10**20
for i in range(n+1):
    res = max(res,s1[i]+s2[n-i])
print(res)

Submission status: Accepted

Solution code:
import heapq

n = int(input())
num = [ int(v) for v in input().split() ]

left_list = num[:n]
right_list = [ -i for i in num[2*n:] ]
left_list.sort()
right_list.sort()
sl, sr = sum(left_list), sum(right_list)
sum_left_list = [sl]
sum_right_list = [sr]

for p in num[n:2*n]:
    q = heapq.heappop(left_list)
    if p > q:
        sl += (p-q)
        heapq.heappush(left_list, p)
    else:
        heapq.heappush(left_list, q)
    sum_left_list.append(sl)

for p in num[2*n-1:n-1:-1]:
    p *= -1
    q = heapq.heappop(right_list)
    if p > q:
        sr += (p-q)
        heapq.heappush(right_list, p)
    else:
        heapq.heappush(right_list, q)
    sum_right_list.append(sr)

sum_right_list.reverse()
ans_list = [ sum_left_list[i] + sum_right_list[i] for i in range(n+1) ]
print(max(ans_list))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heappushpop
N = int(input())
A = [int(a) for a in input().split()]

def calc(L):
    s = sum(L[:N])
    h = []
    X = [s]
    for i in range(N):
        heappush(h, L[i])
    for i in range(N, 2*N):
        s += L[i] - heappushpop(h, L[i])
        X.append(s)
    return X

B = calc(A)
C = calc([-a for a in A][::-1])[::-1]
print(max([B[i] + C[i] for i in range(N+1)]))

Submission status: Accepted

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

import heapq

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

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

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

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

print(max(res))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from heapq import heapify,heappop,heappush
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    P=[None]*(n+1); S=[None]*(n+1)

    # prefix
    Q=A[:n]
    P[0]=sum(Q)
    heapify(Q)
    for i in range(1,n+1):
        a=heappop(Q)
        b=A[n+i-1]
        P[i]=P[i-1]-a+max(a,b)
        heappush(Q,max(a,b))

    # suffix
    Q=[-a for a in A[2*n:]]
    S[-1]=sum(Q)
    heapify(Q)
    for i in range(n-1,-1,-1):
        a=heappop(Q)
        b=-A[n+i]
        S[i]=S[i+1]-a+max(a,b)
        heappush(Q,max(a,b))

    print(max(*(p+s for p,s in zip(P,S))))
resolve()

Submission status: Accepted

Solution code:
import heapq

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

L = A[:2*N]
L.sort()
s1 = 0
s2 = 0
h1 = []
h2 = []
dic = {}
dic_h = {}
for i in range(N):
    heapq.heappush(h1, -L[i])
    if L[i] in dic_h:
        dic_h[L[i]] += 1
    else:
        dic_h[L[i]] = 1
    s1 += L[i+N]
    if L[i+N] in dic:
        dic[L[i+N]] += 1
    else:
        dic[L[i+N]] = 1
    s2 += A[i+2*N]
    heapq.heappush(h2, -A[i+2*N])
    
ans = s1-s2
for i in range(2*N-1, N-1, -1):
    if A[i]+h2[0] < 0:
        s2 += heapq.heappop(h2)
        heapq.heappush(h2, -A[i])
        s2 += A[i]
    if A[i] in dic:
        if dic[A[i]] > 0:
            dic[A[i]] -= 1
            s1 -= A[i]
            t = -heapq.heappop(h1)
            while h1:
                if dic_h[t] > 0:
                    dic_h[t] -= 1
                    break
                else:
                    t = -heapq.heappop(h1)
            s1 += t
            if t in dic:
                dic[t] += 1
            else:
                dic[t] = 1
    else:
        dic_h[A[i]] -= 1
    ans = max(ans, s1-s2)
    
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, heapq,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0


ans = -inf
n = int(input())
A = list(map(int, input().split()))
AL, AR = A[:n], A[2*n:]
al,ar=copy.copy(AL),copy.copy(AR)
AN = A[n:2*n]
LS, RS = sum(AL), sum(AR)
AR = list(map(lambda ddd: -ddd, AR))
heapq.heapify(AL)
heapq.heapify(AR)
tmp=LS
ANSR=[0]*n
ANSL=[0]*n

for i in range(n):
    if AN[i]-AL[0] >0:
        LS = LS-heapq.heappop(AL)+AN[i]
        heapq.heappush(AL,AN[i])
    ANSL[i] = LS

LS=tmp
for j in range(n-1,-1,-1):
    if 0 < -AR[0]-AN[j]:
        RS = RS+heapq.heappop(AR)+AN[j]
        heapq.heappush(AR,-AN[j])
    ANSR[j] = RS
ANSR=ANSR+[sum(ar)]
ANSL=[sum(al)]+ANSL
for i in range(n+1):
    ans=max(ans,ANSL[i]-ANSR[i])
print(ans)
# print(ANSL,ANSR)

Submission status: Accepted

Solution code:
def examD():
    N = I()
    a = LI()
    a_b = list(map(lambda x: x*(-1), a))
    R = a[:N]; B = a_b[2*N:]
    heapq.heapify(R)
    heapq.heapify(B)
    ansC =[]
    curR = [sum(R)]; curB = [-sum(B)]
    for i in range(N):
        heapq.heappush(R, a[N+i])
        cur = curR[-1] - heapq.heappop(R) + a[N+i]
        curR.append(cur)
    for i in range(N):
        heapq.heappush(B, a_b[2*N-1-i])
        cur =curB[-1] - heapq.heappop(B)*(-1) - a_b[2*N-1-i]
        curB.append(cur)
    for i in range(N+1):
        ansC.append(curR[i]-curB[-1-i])
    ans = max(ansC)
    print(ans)
#    print(ansC)
#    print(curR,curB)


import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
from heapq import heappop,heappush,heapify
n=int(input())
a=list(map(int,input().split()))
left=[0]*n
lst=a[:n]
s=sum(lst)
heapify(lst)
for i in range(n):
    heappush(lst,a[n+i])
    x=heappop(lst)
    if i==0:
        left[0]=s+a[n]-x
    else:
        left[i]=left[i-1]+a[n+i]-x
left=[s]+left
right=[0]*n
lst=[]
for i in range(2*n,3*n):
    lst.append(-a[i])
s=-sum(lst)
heapify(lst)
for i in range(n):
    heappush(lst,-a[2*n-1-i])
    x=-heappop(lst)
    if i==0:
        right[n-1]=s+a[2*n-1]-x
    else:
        right[n-1-i]=right[n-i]+a[2*n-1-i]-x
right+=[s]
ans=-float("inf")
for i in range(n+1):
    ans=max(ans,left[i]-right[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

big_a = []  # 前半のデータをheapで収納 popで小さいものが出る
for i in range(n):
    heapq.heappush(big_a,a[i])

small_a = []  # 後半のデータをheapで収納
for i in range(n):
    heapq.heappush(small_a,-a[3*n-1-i])  # popで大きいものが出るようにマイナスをかけている

now_big = sum(big_a)
now_small = -sum(small_a)
big_data = [now_big]  # kを固定した時の値　最初はk=n
small_data = [now_small]  # kを固定した時の値　最初はk=2*n

for k in range(n):
    # 前半のデータの推移
    heapq.heappush(big_a, a[k+n])
    now_big += a[k+n] - heapq.heappop(big_a)  # [0,k+n]の上位n個の総和
    big_data.append(now_big)

    # 後半のデータの推移
    heapq.heappush(small_a, -a[2*n-1-k])
    now_small += a[2*n-1-k] + heapq.heappop(small_a)  # [2*n-1-k,3*n]の下位n個の総和
    small_data.append(now_small)



ans = -10**18
for k in range(n+1):
    ans = max(ans, big_data[k]-small_data[n-k])

print(ans)

Submission status: Accepted

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

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

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

now_big = sum(big_a)
now_small = -sum(small_a)
big_data = [now_big]
small_data = [now_small]

for k in range(n):
    now_big += a[k+n]
    heapq.heappush(big_a,a[k+n])
    now_big -= heapq.heappop(big_a)
    big_data.append(now_big)

    now_small += a[2*n-1-k]
    heapq.heappush(small_a,-a[2*n-1-k])
    now_small += heapq.heappop(small_a)
    small_data.append(now_small)
    
#print(big_data)
#print(small_data)

ans = -10**18
for k in range(n+1):
    ans = max(ans,big_data[k]-small_data[n-k])

print(ans)

Submission status: Accepted

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


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

heap_l = Heapq(A[:n])
heap_r = Heapq(A[2*n:],desc=True)

max_l = [0]*(n+1)
min_r = [0]*(n+1)
max_l[0] = sum(A[:n])
min_r[0] = sum(A[2*n:])

for i in range(n):
    p = heap_l.pop()
    heap_l.push(max(A[n+i],p))
    max_l[i+1] = max_l[i]+max(0,A[n+i]-p)

    q = heap_r.pop()
    heap_r.push(min(A[-1-i-n],q))
    min_r[i+1] = min_r[i]+min(0,A[-1-i-n]-q)

ans = -float('inf')

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

print(ans)

Submission status: Accepted

Solution code:
maxi=-10**99 
n=int(input())
import heapq 
l=[int(i) for i in input().split()]
k=n
sm=sum(l[0:n])
z1=[0]*(n+1)
z2=[0]*(n+1)
h=[]
z1[0]=sm 
j=1 
heapq.heapify(h)
for i in range(n):
    heapq.heappush(h,l[i])
for i in range(n,2*n):
    p=l[i]
    if p>h[0]: 
        sm+=p 
        sm-=h[0]
        heapq.heappop(h)
        heapq.heappush(h,p)
    else:
        pass 
    z1[j]=sm 
    j+=1 
sm=sum(l[2*n:3*n])
h=[]
heapq.heapify(h)
sm=0 
for i in range(2*n,3*n):
    heapq.heappush(h,-l[i])
    sm+=(l[i])
j=n 
z2[j]=sm  
j-=1 
#print(h[0])
#print(sm)
for i in range(2*n-1,n-1,-1): 
    p=-l[i]
    if p>h[0]:
        #print('jif')
        sm=sm+h[0]-p
        heapq.heappop(h)
        heapq.heappush(h,p)
        
    else:
        pass 
    z2[j]=sm 
    j-=1 
maxi=-(10**99)
#print(z1)
#print(z2)
for i in range(n+1):
    maxi=max(maxi,z1[i]-z2[i])
print(maxi)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
inf = float('inf')

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

l = []
res = 0
for i in range(N):
    heappush(l, A[i])
    res += A[i]
ls = []
ls.append(res)

for i in range(N, 2*N):
    heappush(l, A[i])
    res += A[i]
    res -= heappop(l)
    ls.append(res)

A.reverse()

s = []
res = 0
for i in range(N):
    heappush(s, -A[i])
    res += A[i]
ss = []
ss.append(res)

for i in range(N, 2*N):
    heappush(s, -A[i])
    res += A[i]
    res -= -heappop(s)
    ss.append(res)

ss.reverse()

ans = -inf

for i in range(N+1):
    score = ls[i] - ss[i]
    ans = max(ans, score)

print(ans)

Submission status: Accepted

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

import sys
from heapq import heapify, heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A1 = A[:N]
A2 = A[N:N*2]
A3 = [-a for a in A[N*2:]]
heapify(A1)
heapify(A3)

# 真ん中グループ(A2)をiまで左に取り込んだ時の左グループ(A1)の最大値
ansa = [0] * (N+1)
ansa[0] = sum(A1)
for i in range(N):
    heappush(A1, A2[i])    
    ansa[i+1] = ansa[i] + A2[i] - heappop(A1)

# 真ん中グループ(A2)を後ろからiまで右に取り込んだ時の右グループ(A1)の最小値
ansb = [0] * (N+1)
ansb[N] = -sum(A3)
for i in range(N-1, -1, -1):
    heappush(A3, -A2[i])
    ansb[i] = ansb[i+1] + A2[i] - (-heappop(A3))

# 各位置iから一番いい場所を得る
ans = -INF
for i in range(N+1):
    ans = max(ans, ansa[i]-ansb[i])
print(ans)

Submission status: Accepted

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

pre = sum(a[:n])
post = -sum(a[2*n:])
post2 = post
ans = - pre + post

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

S_pre = [pre]

for i in range(n,2*n):
    pre += a[i]
    heapq.heappush(Q,a[i])
    q = heapq.heappop(Q)
    pre -= q
    S_pre.append(pre)

Q2 = []
for i in range(2*n,3*n):
    heapq.heappush(Q2, -a[i])
S_post = [post]
for i in range(2*n - 1,n-1,-1):
    post -= a[i]
    heapq.heappush(Q2,-a[i])
    q = heapq.heappop(Q2)
    #print(q)
    post -= q
    S_post.append(post)

#print(S_pre)
#print(S_post)
for i in range(n+1):###+1
    ans = max(ans, S_pre[n-i]+S_post[i])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC62 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
frontheap,backheap = [],[]
front,back = [],[]
f,b = 0,0
for i in range(n):
    heappush(frontheap,a[i])
    f += a[i]
    heappush(backheap,-a[-i-1])
    b += a[-i-1]
front.append(f)
back.append(b)
for i in range(n):
    x = heappop(frontheap)
    heappush(frontheap,max(x,a[n+i]))
    front.append(front[-1] - x + max(x,a[i+n]))
    y = heappop(backheap)
    heappush(backheap,-min(-y,a[2*n-i-1]))
    back.append(back[-1] + y + min(-y,a[2*n-i-1]))
ans = -inf
for i in range(n+1):
    ans = max(ans,front[i] - back[-i-1])
print(ans)

Submission status: Accepted

Solution code:
import heapq


N = int(input())

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

lq = []
lsum = 0
rq = []
rsum = 0

for i in range(N):

    heapq.heappush(lq,a[i])
    lsum += a[i]

    heapq.heappush(rq,-1 * a[3 * N - 1 - i])
    rsum += a[3*N-1-i]

llis = []
rlis = []

for i in range(N+1):

    llis.append(lsum)
    rlis.append(rsum)

    heapq.heappush(lq,a[N+i])
    heapq.heappush(rq,-1 * a[2*N-1-i])
    lsum += a[N+i]
    rsum += a[2*N-1-i]

    lpop = heapq.heappop(lq)
    rpop = -1 * heapq.heappop(rq)
    lsum -= lpop
    rsum -= rpop

rlis.reverse()

ans = -1 * float("inf")

for i in range(N+1):

    ans = max(ans,llis[i]-rlis[i])

print (ans)

Submission status: Accepted

Solution code:
import sys
import queue

#+++++
		
def main():
	n = int(input())
	nnn = list(map(int, input().split()))
	
	ppp=nnn[:n]
	ccc=nnn[n:2*n]
	bbb=nnn[2*n:]
	
	pp_v=[0]*(n+1)
	ppq=queue.PriorityQueue()
	for v in ppp:
		ppq.put(v)
	
	pre=sum(ppp)
	pp_v[0]=pre
	for i,v in enumerate(ccc):
		ppq.put(v)
		t=ppq.get()
		pre=pre+v-t
		pp_v[i+1]=pre
		
		
	bb_v=[0]*(n+1)
	bbq=queue.PriorityQueue()
	for v in bbb:
		bbq.put(-v)
	
	pre=-1*sum(bbb)
	bb_v[0]=pre
	for i,v in enumerate(ccc[::-1]):
		bbq.put(-v)
		t=bbq.get()
		pre=pre+(-v)-(t)
		bb_v[i+1]=pre
		
	dd=[p+q for p,q in zip(pp_v,bb_v[::-1])]
	ans=max(dd)
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import heapq as hp
import sys
input = sys.stdin.readline

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

q1 = []
for i in range(N):
    hp.heappush(q1, A[i])

Psum = [0]*(N+1)
Psum[0] = sum(q1)

for i in range(N):
    a1 = hp.heappop(q1)
    p = max(a1, A[N+i])
    hp.heappush(q1, p)
    Psum[i+1] = Psum[i] + p - a1

q2 = []
for i in range(N):
    hp.heappush(q2, -A[i+2*N])

Qsum = [0]*(N+1)
Qsum[N] = sum(q2)

for i in range(N-1, -1, -1):
    a2 = hp.heappop(q2)
    p = max(a2, -A[N+i])
    hp.heappush(q2, p)
    Qsum[i] = Qsum[i+1] + p - a2


for i in range(N+1):
    if i == 0:
        ans = Psum[i]+Qsum[i]
    ans = max(Psum[i]+Qsum[i], ans)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n=int(input())
a=list(map(int,input().split()))
l=[0]*(n+1)
r=[0]*(n+1)
s=sum(a[:n])
t=sum(a[-n:])
l[0]=s
r[~0]=t
h=[]
H=[]
for i in range(n):
    heappush(h,a[i])
    heappush(H,-a[~i])
for i in range(n):
    s+=a[n+i]
    t+=a[~(n+i)]
    heappush(h,a[n+i])
    heappush(H,-a[~(n+i)])
    s-=heappop(h)
    t+=heappop(H)
    l[i+1]=s
    r[~(i+1)]=t
print(max(l[i]-r[i] for i in range(n+1)))

Submission status: Accepted

Solution code:
import heapq

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

Q0 = []
Q1 = []
Ana = [0] * (3*n)

M = [[A[n+i], n+i] for i in range(2*n)]
M.sort() 

msum = sum([M[i][0] for i in range(n)])
ans = sum(A[:n]) - msum
ans0 = ans
#print(ans0)

for i in range(n):
    heapq.heappush(Q0, A[i])
    heapq.heappush(Q1, [M[n+i][0], M[n+i][1]])
    Ana[M[n+i][1]] = 1

for i in range(n):
    #print("i",i, Q0,Q1,Ana)
    if Ana[n+i] == 0:
        heapq.heappush(Q0, A[n+i])
        ans0 += A[n+i] * 2
        ochi = heapq.heappop(Q0)
        ans0 -= ochi
        agari = heapq.heappop(Q1)
        while Ana[agari[1]] == 0:
            agari = heapq.heappop(Q1)
        Ana[agari[1]] = 0
        ans0 -= agari[0]
    else:
        Ana[n+i] = 0
        heapq.heappush(Q0, A[n+i])
        ans0 += A[n+i]
        ochi = heapq.heappop(Q0)
        ans0 -= ochi
    #print(ans0)
    ans = max(ans, ans0)


saigo = sum((sorted(A[:n*2]))[n:]) - sum(A[n*2:])
#print(saigo)

ans = max(ans, saigo)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
n = int(input())
a = list(map(int, input().split()))
max_sum_fh = [0] * (n + 1)
min_sum_lh = [0] * (n + 1)
 
hq_fh = []
hq_lh = []
 
for i in range(n):
    heappush(hq_fh, a[i])
    heappush(hq_lh, -a[-1 - i])

max_sum_fh[0] = sum(hq_fh)
min_sum_lh[n] = -sum(hq_lh)

for i in range(n):
    if a[i + n] > hq_fh[0]:
        value_in = a[i + n]
        value_out = heappop(hq_fh)
        heappush(hq_fh, value_in)
        max_sum_fh[i + 1] = max_sum_fh[i] - value_out + value_in
    else:
        max_sum_fh[i + 1] = max_sum_fh[i]
    if -a[-1 - i - n] > hq_lh[0]:
        value_in = -a[-1 - i - n]
        value_out = heappop(hq_lh)
        heappush(hq_lh, value_in)
        min_sum_lh[-2 - i] = min_sum_lh[-1 - i] + value_out - value_in
    else:
        min_sum_lh[-2 - i] = min_sum_lh[-1 - i]
    
print(max([max_sum_fh[i] - min_sum_lh[i] for i in range(n + 1)]))

Submission status: Accepted

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

def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  an = []
  a2n = a[n:2*n]
  a3n = []
  
  for i in range(n):
    heapq.heappush(an,a[i])
    heapq.heappush(a3n,-1*a[i+2*n])

  tmpsuman = sum(an)
  tmpsuma3n = -1*sum(a3n)
  
  suman = [tmpsuman]
  suma3n = [tmpsuma3n]
  
  for i in range(n):
    tmp = a2n[i]
    tmpsuman += tmp
    heapq.heappush(an,tmp)
    tmpsuman -= heapq.heappop(an)
    
    suman.append(tmpsuman)

    tmp = a2n[n-i-1]
    tmpsuma3n += tmp
    heapq.heappush(a3n,-1*tmp)
    tmpsuma3n -= -1*heapq.heappop(a3n)
    suma3n.append(tmpsuma3n)

  ans = -1*float("INF")
  for i in range(n+1):
    ans = max(ans,suman[i]-suma3n[n-i])
  print(ans)
solve()

Submission status: Accepted

Solution code:
import heapq
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  an = []
  a2n = a[n:2*n]
  a3n = []
  for i in range(n):
    heapq.heappush(an,a[i])
    heapq.heappush(a3n,-1*a[i+2*n])
  ta2n = a2n
  
  tmpsuman = sum(an)
  tmpsuma3n = -1*sum(a3n)
  
  suman = [tmpsuman]
  suma3n = [tmpsuma3n]
  
  for i in range(n):
    tmp = ta2n[i]
    tmpsuman += tmp
    heapq.heappush(an,tmp)
    tmpsuman -= heapq.heappop(an)
    
    suman.append(tmpsuman)
  for i in range(n):
    tmp = ta2n[n-i-1]
    tmpsuma3n += tmp
    heapq.heappush(a3n,-1*tmp)
    tmpsuma3n -= -1*heapq.heappop(a3n)
    suma3n.append(tmpsuma3n)

  ans = -10000000000000000
  for i in range(n+1):
    tmpans = suman[i]-suma3n[n-i]
    ans = max(ans,tmpans)
  print(ans)
solve()

Submission status: Accepted

Solution code:
class HeapQueue:
    """
    q = HeapQueue()
    q.append(p, v)
    v = q.pop()
    """
    from heapq import heappop, heappush, heappushpop, heapreplace

    def __init__(self, reverse=False):
        self.reverse = reverse
        self.heap = []

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

    def append(self, p, v):
        self.heappush(self.heap, (-p if self.reverse else p, v))

    def appendpop(self, p, v):
        return self.heappushpop(self.heap, (-p if self.reverse else p, v))[1]

    def popappend(self, p, v):
        return self.heapreplace(self.heap, (-p if self.reverse else p, v))[1]

    def pop(self):
        return self.heappop(self.heap)[1]

    def front(self):
        return self.heap[0][1]


N = int(input())
A = [int(s) for s in input().split()]
S = []
T = []

S.append(sum(A[:N]))
q = HeapQueue()
for a in A[:N]:
    q.append(a, a)
for a in A[N:2*N]:
    m = q.appendpop(a, a)
    S.append(S[-1] + a - m)

T.append(sum(A[-N:]))
q = HeapQueue(reverse=True)
for a in A[-N:]:
    q.append(a, a)
for a in A[-N-1:N-1:-1]:
    m = q.appendpop(a, a)
    T.append(T[-1] + a - m)
ans = max([S[i] - T[N - i] for i in range(N + 1)])
print(ans)