Problem:


Score : 500 points

Problem Statement

Let N be a positive integer.

There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}).
Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements.
Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').

Find the maximum possible score of a'.

Constraints

1 ≤ N ≤ 10^5

a_i is an integer.

1 ≤ a_i ≤ 10^9

Partial Score

In the test set worth 300 points, N ≤ 1000.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{3N}

Output

Print the maximum possible score of a'.

Sample Input 1

2
3 1 4 1 5 9

Sample Output 1

1

When a_2 and a_6 are removed, a' will be (3, 4, 1, 5), which has a score of (3 + 4) - (1 + 5) = 1.

Sample Input 2

1
1 2 3

Sample Output 2

-1

For example, when a_1 are removed, a' will be (2, 3), which has a score of 2 - 3 = -1.

Sample Input 3

3
8 2 2 7 4 6 5 3 8

Sample Output 3

5

For example, when a_2, a_3 and a_9 are removed, a' will be (8, 7, 4, 6, 5, 3), which has a score of (8 + 7 + 4) - (6 + 5 + 3) = 5.



Sample input:
2
3 1 4 1 5 9


Sample output:
1

Submission status: Accepted

Solution code:
from heapq import heapify, heapreplace


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

qa = a[:n]
qb = [-x for x in a[2*n:]]
heapify(qa)
heapify(qb)

sa = [0] * (n + 1)
sb = [0] * (n + 1)
sa[0] = sum(qa)
sb[n] = -sum(qb)

for i in range(n):
    x = qa[0]
    sa[i+1] = sa[i]
    if x < a[n+i]:
        sa[i+1] += a[n+i] - x
        heapreplace(qa, a[n+i])

    x = -qb[0]
    sb[-i-2] = sb[-i-1]
    if x > a[-n-1-i]:
        sb[-i-2] += a[-n-1-i] - x
        heapreplace(qb, -a[-n-1-i])

max_val = sa[0] - sb[n]
for i in range(n+1):
    max_val = max(max_val, sa[i] - sb[i])
print(max_val)

Submission status: Accepted

Solution code:
from heapq import *
N=int(input())
A=list(map(int,input().split()))
Q=[]
heapify(Q)
for i in range(N):
  heappush(Q,A[i])
ML=[sum(Q)]
for i in range(N):
  if Q[0]<A[N+i]:
    ML.append(ML[i]+A[N+i]-Q[0])
    heappop(Q)
    heappush(Q,A[N+i])
  else:
    ML.append(ML[i])
for i in range(3*N):
  A[i]*=-1
A=A[::-1]
Q=[]
heapify(Q)
for i in range(N):
  heappush(Q,A[i])
MR=[sum(Q)]
for i in range(N):
  if Q[0]<A[N+i]:
    MR.append(MR[i]+A[N+i]-Q[0])
    heappop(Q)
    heappush(Q,A[N+i])
  else:
    MR.append(MR[i])
MR=MR[::-1]
print(max([ML[i]+MR[i] for i in range(N+1)]))

Submission status: Accepted

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

table1=[0]*(N+1)
table1[0]=sum(a[:N])
q1=a[:N].copy()
heapq.heapify(q1)

for i in range(N):
  table1[i+1]=table1[i]+a[N+i]
  heapq.heappush(q1, a[N+i])
  tmp=heapq.heappop(q1)
  table1[i+1]-=tmp

table2=[0]*(N+1)
table2[N]=sum(a[2*N:])
q2=[-x for x in a[2*N:]]
heapq.heapify(q2)

for i in range(N):
  table2[N-1-i]=table2[N-i]+a[2*N-1-i]
  heapq.heappush(q2, -a[2*N-1-i])
  tmp=-heapq.heappop(q2)
  table2[N-1-i]-=tmp
  
print(max([table1[i]-table2[i] for i in range(N+1)]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    #D - 3N Numbers
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    l=[0]*(N+1)
    q=[A[i] for i in range(N)]
    tot=sum(q)
    heapify(q)

    l[0]=tot
    for i in range(0,N):
        a=A[N+i]
        if a>q[0]:
            tot+=a-q[0]
            heappop(q)
            heappush(q,a)
        l[i+1]=tot

    l2=[0]*(N+1)
    q=[-A[i] for i in range(2*N,3*N)]
    tot=-sum(q)
    heapify(q)
    l2[0]=tot

    for i in range(0,N):
        a=A[-N-i-1]
        if a<-q[0]:
            tot+=a-(-q[0])
            heappop(q)
            heappush(q,-a)
        l2[i+1]=tot
    ans=-float('inf')

    for i in range(N+1):
        ans=max(l[i]-l2[-1-i],ans)
    print(ans)
    #printe(l,l2)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import *

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

# 0 <= i <= N
# left_Nth_max_sum[i] == sum( sorted(As[:N+i], reverse=True)[:N] )
# right_Nth_min_sum[i] == sum( sorted(As[N+i:])[:N] )

left_Nth_max_sum = [0] * (N+1)
lpq = As[:N] # left priority queue
heapify(lpq)
left_Nth_max_sum[0] = sum(lpq)
for i in range(N):
    popped_A = heappushpop(lpq, As[N+i])
    left_Nth_max_sum[i+1] = left_Nth_max_sum[i] + As[N+i] - popped_A

right_Nth_min_sum = [0] * (N+1)
rpq = [-A for A in As[2*N:]]
heapify(rpq)
right_Nth_min_sum[N] = -sum(rpq)
for i in range(N-1, -1, -1):
    popped_A = -heappushpop(rpq, -As[N+i])
    right_Nth_min_sum[i] = right_Nth_min_sum[i+1] + As[N+i] - popped_A

"""
for i in range(N+1):
    assert left_Nth_max_sum[i] == sum( sorted(As[:N+i], reverse=True)[:N] )
    assert right_Nth_min_sum[i] == sum( sorted(As[N+i:])[:N] )
"""

print(max( (left_Nth_max_sum[i] - right_Nth_min_sum[i] for i in range(N+1)) ))

Submission status: Accepted

Solution code:
import heapq

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

l_s = alst[:n]
r_s = [-1 * num for num in alst[2 * n:]]
heapq.heapify(l_s)
heapq.heapify(r_s)
l_total = [sum(l_s)]
r_total = [sum(r_s)]

for num in alst[n:2*n]:
    if l_s[0] > num:
        l_total.append(l_total[-1])
    else:
        minus = heapq.heappop(l_s)
        heapq.heappush(l_s, num)
        l_total.append(l_total[-1] + num - minus)
        
for num in alst[n:2*n][::-1]:
    if r_s[0] > num * -1:
        r_total.append(r_total[-1])
    else:
        minus = heapq.heappop(r_s)
        heapq.heappush(r_s, -1 * num)
        r_total.append(r_total[-1] - num - minus)

ans = -1 * 10 ** 20
for num, num2 in zip(l_total, r_total[::-1]):
    ans = max(ans, num + num2)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
n=int(input())
a=list(map(int,input().split()))
hl,hr=[],[]
for i in range(n):
  heappush(hl,a[i])
  heappush(hr,-a[i+2*n])
sl=[sum(hl)]
sr=[sum(hr)]
ans=0
for i in a[n:2*n]:
  sl+=[i+sl[-1]]
  heappush(hl,i)
  sl[-1]-=heappop(hl)
for i in a[n:2*n][::-1]:
  sr+=[-i+sr[-1]]
  heappush(hr,-i)
  sr[-1]-=heappop(hr)
print(max([i+j for i,j in zip(sl,sr[::-1])]))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
from heapq import heappush as hp, heappop as hpp
h = []
dp = [0]*n
for i in range(n):
    hp(h, a[i])
v = 0
for i in range(n, 2*n):
    hp(h, a[i])
    tmp = hpp(h)
    v += (a[i]-tmp)
    dp[i-n] = v
dp.insert(0,0)
h = []
dp2 = [0]*n
for i in range(2*n, 3*n):
    hp(h, -a[i])
v = 0
for i in range(2*n-1, n-1, -1):
    hp(h, -a[i])
    tmp = hpp(h)
    v += (a[i]+tmp)
    dp2[2*n-1-i] = v
dp2.insert(0,0)
ans = sum(a[:n]) - sum(a[2*n:]) + max((dp[i]-dp2[n-i]) for i in range(n+1))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
def solve():
  ans = -float('inf')
  N = int(input())
  A = list(map(int, input().split()))
  before = A[:N]
  after = list(map(lambda x:-x,A[-N:]))
  heapify(before)
  heapify(after)
  b = [sum(before)]*(3*N)
  a = [sum(after)]*(3*N)
  for i in range(N,2*N):
    p = heappop(before)
    if p<A[i]:
      b[i] = b[i-1]-p+A[i]
      heappush(before,A[i])
    else:
      b[i] = b[i-1]
      heappush(before,p)
  for i in range(2*N-1,N-1,-1):
    p = heappop(after)
    if p<-A[i]:
      a[i] = a[i+1]-p-A[i]
      heappush(after,-A[i])
    else:
      a[i] = a[i+1]
      heappush(after,p)
  for i in range(N,2*N+1):
    ans = max(ans,b[i-1]+a[i])
  return ans
print(solve())

Submission status: Accepted

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

left = [0]*(N+1)
l = a[:N]
left[0] = sum(l)

heapq.heapify(l)
for i in range(1, N+1):
    c = a[N+i-1]    
    lmin = heapq.heappop(l)
    if lmin < c:
        left[i] = left[i-1] + c - lmin
        heapq.heappush(l, c)
    else:
        left[i] = left[i-1]
        heapq.heappush(l, lmin)

a = [-x for x in a[::-1]]
right = [0]*(N+1)
r = a[:N]
right[0] = sum(r)

heapq.heapify(r)
for i in range(1, N+1):
    c = -a[N+i-1]    
    rmax = -heapq.heappop(r)
    if rmax > c:
        right[i] = right[i-1] - c + rmax
        heapq.heappush(r, -c)
    else:
        right[i] = right[i-1]
        heapq.heappush(r, -rmax)

ans = -10**20
for i in range(N+1):
    ans = max(ans, left[i] + right[N-i])

print(ans)

Submission status: Accepted

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

Q = []
R = []
sumQ = [0 for _ in range(N+1)]
sumR = [0 for _ in range(N+1)]
for i in range(N):
  heappush(Q, A[i])
  heappush(R, -A[3*N-1-i])

#sQ = sum(Q)
#sR = sum(R)
sumQ[0] = sum(Q)
sumR[N] = sum(R)

for i in range(N):
  heappush(Q, A[N+i])
  B = heappop(Q)
  #sQ += A[N+i] - B
  sumQ[i+1] = sumQ[i] + A[N+i] - B
  
  heappush(R, -A[2*N-1-i])
  B = heappop(R)
  #sR += -A[2*N-i] - B
  sumR[N-i-1] = sumR[N-i] -A[2*N-1-i] - B
  
  

ans = sumQ[0] + sumR[0]
#print(sumQ,sumR)
for i in range(1, N+1):
  ans = max(ans, sumQ[i] + sumR[i])
  
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(3*N-1,-1,-1):
    B.append(A[i]*-1)
"""
前半をできるだけおおきく、後半をできるだけ小さくする。
前半はpriority queにぶっこんでいって、最小値を除去していく
"""
import heapq
frontSum = sum(A[:N])
frontQue = A[:N]
heapq.heapify(frontQue)
front = [frontSum]
for i in range(N,2*N):
    frontSum += A[i]
    heapq.heappush(frontQue,A[i])
    frontSum -= heapq.heappop(frontQue)
    front.append(frontSum)

backSum = sum(B[:N])
backQue = B[:N]
heapq.heapify(backQue)
back = [backSum*-1]
for i in range(N,2*N):
    backSum += B[i]
    heapq.heappush(backQue,B[i])
    backSum -= heapq.heappop(backQue)
    back.append(backSum*-1)
back = back[::-1]

candi = []
for i in range(len(front)):
    candi.append(front[i]-back[i])
print(max(candi))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

from heapq import *

def get(q,a):
    v = sum(q)
    res = [v]
    for i in a[n:2*n]:
        x = heappushpop(q,i)
        v += i-x
        res.append(v)
    return res

q = a[:n]
heapify(q)
res1 = get(q,a)

a = [-i for i in a[::-1]]
q = a[:n]
heapify(q)
res2 = get(q,a)

#print(res1)
#print(res2)

print(max(i+j for i,j in zip(res1,res2[::-1])))

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
orlis=LI()
flis=orlis[:n]
smflis=[0 for i in range(n+1)]
x=sum(flis)
smflis[0]=x
heapify(flis)
for i in range(n):
    x+=orlis[n+i]
    heappush(flis,orlis[n+i])
    y=heappop(flis)
    x-=y
    smflis[i+1]=x
#print(smflis)
orlis=list(reversed(orlis))
llis=orlis[:n]
#print(llis)
for i in range(n):
    llis[i]*=(-1)
smllis=[0 for i in range(n+1)]
x=-sum(llis)
smllis[0]=x
#print(llis)
heapify(llis)
for i in range(n):
    x+=orlis[n+i]
    heappush(llis,-orlis[n+i])
    y=-heappop(llis)
    #print(-orlis[n+i])
    #print(y)
    x-=y
    smllis[i+1]=x
#print(smllis)
answers=[]
for i in range(n+1):
    j=n-i
    answers.append(smflis[i]-smllis[j])
print(max(answers))

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque
from heapq import *

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

	X=A[:n]
	Y=[-i for i in A[2*n:]]
	M=A[n:2*n]

	heapify(X)
	heapify(Y)

	xs=sum(X)
	ys=sum(Y)
	XX=[xs]
	YY=[ys]

	for i in M:
		heappush(X,i)
		a=heappop(X)
		xs+=+i-a
		XX.append(xs)

	for i in reversed(M):
		heappush(Y,-i)
		a=heappop(Y)
		ys+=-i-a
		YY.append(ys)

	ans=-10**18

	for i,j in zip(XX,YY[::-1]):
		ans=max(ans,i+j)

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

Submission status: Accepted

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

l = a[:n]
heapq.heapify(l)
memo_l = [0 for _ in range(n+1)]
memo_l[0] = sum(a[:n])

for i in range(1, n+1):
    memo_l[i] = memo_l[i-1]
    if l[0] < a[n+i-1]:
        x = heapq.heappop(l)
        heapq.heappush(l, a[n+i-1])
        memo_l[i] += a[n+i-1] - x


r = [-a[-i] for i in range(1, n+1)]
heapq.heapify(r)
memo_r = [0 for _ in range(n+1)]
memo_r[0] = sum(a[-n:])

for i in range(1, n+1):
    memo_r[i] = memo_r[i-1]
    if abs(r[0]) > a[-n-i]:
        x = heapq.heappop(r)
        heapq.heappush(r, -a[-n-i])
        memo_r[i] += x + a[-n-i]


ans = - 10 ** 20
for i in range(n+1):
    ans = max(ans, memo_l[i] - memo_r[n-i])

print(ans)

Submission status: Accepted

Solution code:
import heapq

n = int(input())
*arr, = map(int, input().split())


right = [0] * 3 * n


def build_prefix(arr):
    left = [0] * 3 * n
    h = []
    s = 0
    for i in range(len(arr)):
        if len(h) < n:
            heapq.heappush(h, arr[i])
            s += arr[i]
        else:
            heapq.heappush(h, arr[i])
            removed = heapq.heappop(h)
            s = s - removed + arr[i]
        left[i] = s
    return left

left = build_prefix(arr)
right = build_prefix([-v for v in arr][::-1])[::-1]

ans = -sum(arr)
for i in range(n - 1, 2 * n):
    ans = max(ans, left[i] + right[i + 1])
print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
B1 = []
for i in range(N):
    heapq.heappush(B1,(A[i],i))
C = []
for i in range(N,3*N):
    heapq.heappush(C,(A[i],i))
B2 = []
for _ in range(N):
    a,i = heapq.heappop(C)
    heapq.heappush(B2,(i,a))
dmax = 0
for i in range(N):
    dmax += B1[i][0]-B2[i][1]
d = dmax
for i in range(N,2*N):
    a = A[i]
    if B1[0][0]<a:
        d += a-B1[0][0]
        heapq.heappop(B1)
        heapq.heappush(B1,(a,i))
    while C and B2[0][0]<=i:
        _,b = heapq.heappop(B2)
        d += b
        a,j = heapq.heappop(C)
        heapq.heappush(B2,(j,a))
        d -= a
    dmax = max(dmax,d)
print(dmax)

Submission status: Accepted

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

n = int(input())
A = list(map(int, input().split()))
L = []
R = []
C = [0]*(n+1)
D = [0]*(n+1)
s = 0
t = 0
for i in range(n):
  a, b = A[i], -A[3*n-1-i]
  s += a
  t += b
  heapq.heappush(L, a)
  heapq.heappush(R, b)
C[0] = s
D[-1] = t
for i in range(n):
  a, b = A[n+i], -A[2*n-1-i]
  h = heapq.heappop(L)
  s -= h
  h = max(h, a)
  s += h
  heapq.heappush(L, h)
  C[i+1] = s
  g = heapq.heappop(R)
  t -= g
  g = max(g, b)
  t += g
  heapq.heappush(R, g)
  D[n-1-i] = t
ans = -float("inf")
for c, d in zip(C, D):
  ans = max(ans, c+d)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
h = []
ltable = [0] * (N + 1)
for i in range(N):
  ltable[0] += a[i]
  hpush(h, a[i])
for i in range(N):
  hpush(h, a[N + i])
  ltable[i + 1] = ltable[i] + a[N + i] - hpop(h)

a.reverse()
h = []
rtable = [0] * (N + 1)
for i in range(N):
  rtable[0] += a[i]
  hpush(h, -a[i])
for i in range(N):
  hpush(h, -a[N + i])
  rtable[i + 1] = rtable[i] + a[N + i] + hpop(h)
#print(ltable, rtable)
res = -10 ** 15
for i in range(N + 1): res = max(res, ltable[i] - rtable[N - i])
print(res)

Submission status: Accepted

Solution code:
import heapq

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

f = a[:N]
heapq.heapify(f)
red = [0] * (N + 1)
red[0] = sum(f)

l = [-i for i in a[2*N:]]
heapq.heapify(l)
blue = [0] * (N + 1)
blue[N] = -sum(l)

for i in range(N):
    num1 = a[N + i]
    pop1=heapq.heappushpop(f, num1)
    red[i+1] = red[i] + num1 - pop1

    num2 = a[2*N - i - 1]
    pop2=heapq.heappushpop(l, -num2)
    blue[N-i-1] = blue[N-i] + num2 + pop2

ans = red[0] - blue[0]

for k in range(N+1):
    ans = max(ans, red[k] - blue[k])

print(ans)

Submission status: Accepted

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

q = As[:N]
heapify(q)
S = sum(q)
firstHalfSum = [S]
for i in range(N, 2*N):
    a = As[i]
    S += a
    heappush(q, a)
    S -= heappop(q)
    firstHalfSum.append(S)

q = [-a for a in As[2*N:]]
heapify(q)
S = sum(q)
secondHalfSum = [S]
for i in range(2*N-1, N-1, -1):
    a = -As[i]
    S += a
    heappush(q, a)
    S -= heappop(q)
    secondHalfSum.append(S)
secondHalfSum.reverse()

ans = max([f + s for f, s in zip(firstHalfSum, secondHalfSum)])
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
n = int(input())
A = list(map(int,input().split()))
leftq = []
rightq = []
heapify(leftq)
heapify(rightq)
left = [0]*(3*n)
right= [0]*(3*n)

leftsum = 0
for i,a in enumerate(A):
    if i < n:
        leftsum += a
        heappush(leftq,a)
    else:
        if leftq[0] < a:
            leftsum += a
            leftsum -= heappushpop(leftq,a)
    if i >= n-1:
        left[i] = leftsum
rightsum = 0
for j,a in enumerate(A[::-1]):
    i = 3*n - 1 - j
    if i > 2*n-1:
        rightsum += a
        heappush(rightq,-a)
    else:
        if rightq[0] < -a:
            rightsum += a
            rightsum += heappushpop(rightq,-a)
    if i <= 2*n:
        right[i] = rightsum
ans = -float('inf')
for i in range(n-1,2*n):
    ans = max(ans,left[i]-right[i+1])
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


# # # # class Segtree end # # # #
import heapq
n = inn()
a = inl()

lmax = a[:n]
lsum = sum(lmax)
heapq.heapify(lmax)

r = a[n:]
r = [(r[i],i) for i in range(2*n)]
r.sort()
rsum = sum([x[0] for x in r[:n]])
rmax = [BIG]*(2*n)
h = {}
for v,i in r[n:]:
    if v not in h:
        h[v] = []
    h[v].append(i)
    rmax[i] = v
sgt = Segtree(2*n,BIG,lambda x,y: min(x,y))
sgt.setary(rmax)

if False:
    ddprint(a)
    #ddprint(f"{n=} {lsum=} {rsum=}")
    ddprint(lmax)
    ddprint(rmax)
    ddprint(h)

mx = lsum - rsum
for i in range(n):
    v = a[n+i]
    v2 = heapq.heappushpop(lmax,v)
    lsum += v-v2
    if sgt.get(i)==BIG:
        vnew = sgt.query(i+1,2*n)
        rsum += vnew-v
        suf = h[vnew].pop()
        sgt.set(suf,BIG)
        #ddprint(f"{i=} {v=} {v2=} {vnew=} {suf=} {lsum=} {rsum=}")
    mx = max(mx,lsum-rsum)

print(mx)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
import heapq

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

    one_third = a[0:n]
    three_third = [-x for x in a[2*n:3*n]]
    heapq.heapify(one_third)
    heapq.heapify(three_third)

    one_sum = [0]*(n+1)
    one_sum[0] = sum(one_third)
    three_sum = [0]*(n+2)
    three_sum[n+1] = -sum(three_third)
    for i in range(n, 2*n):
        two_num_for_one = a[i]
        min_num = heapq.heappushpop(one_third, two_num_for_one)
        one_sum[i-n+1] = one_sum[i-n] - min_num + two_num_for_one

        two_num_for_three = -a[3*n-i-1]
        max_num = -heapq.heappushpop(three_third, two_num_for_three)
        three_sum[2*n-i] = three_sum[2*n-i+1] - max_num - two_num_for_three

    score = -float('inf')
    for i in range(n+1):
        score = max(score, one_sum[i]-three_sum[i+1])

    print(score)        
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Accepted

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

#前半部分の最適化辞書作成
SUM = sum(A[:N])
firstDic = {N-1:SUM}
que = A[:N]
heapq.heapify(que)
for i in range(N,2*N):
    SUM += A[i]
    heapq.heappush(que,A[i])
    SUM -= heapq.heappop(que)
    firstDic[i] = SUM


#後半部分の最適化辞書作成
SUM = sum(A[2*N:])*-1
latterDic = {2*N-1:SUM*-1}
que = [A[i]*-1 for i in range(2*N,3*N)]
heapq.heapify(que)
for i in range(2*N-1,N-1,-1):
    SUM += A[i]*-1
    heapq.heappush(que,A[i]*-1)
    SUM -= heapq.heappop(que)
    latterDic[i-1] = SUM*-1
ans = -1*float("INF")
for k,v in firstDic.items():
    ans = max(ans,v-latterDic[k])

print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = list(map(int, input().split()))
R = [a for a in A[:N]]
M = [a for a in A[N:2*N]]
B = [-a for a in A[2*N:3*N]]
res_R = [0] * (N + 1)
res_B = [0] * (N + 1)
res_R[0] = sum(R)
res_B[N] = -sum(B)
heapq.heapify(R)
heapq.heapify(B)
for i in range(N):
    heapq.heappush(R, M[i])
    a = heapq.heappop(R)
    res_R[i+1] = res_R[i] + M[i] - a
    heapq.heappush(B, -M[N-i-1])
    a = heapq.heappop(B)
    res_B[N-i-1] = res_B[N-i] + M[N-i-1] + a
print(max(r - b for r, b in zip(res_R, res_B)))

Submission status: Accepted

Solution code:
import heapq

def solve(n,a):
    a1 = a[:n]
    a2 = [-a[i] for i in range(2*n,3*n)]

    l = [[0,0] for i in range(n+1)]

    heapq.heapify(a1)
    heapq.heapify(a2)

    l[0][0] = sum(a1)
    l[n][1] = sum(a2)
    
    for k in range(n,2*n):

        heapq.heappush(a1,a[k])
        tmp = heapq.heappop(a1)
        l[k-n+1][0] = l[k-n][0] + a[k] - tmp

        heapq.heappush(a2,-a[3*n-k-1])
        tmp = heapq.heappop(a2)
        l[2*n-k-1][1] = l[2*n-k][1] - a[3*n-k-1] - tmp

    res = -float('inf')

    for ans in l:
        res = max(res,ans[0]+ans[1])

    return res

if __name__ == '__main__':
    n = int(input())
    a = list(map(int,input().split()))
    print(solve(n,a))

Submission status: Accepted

Solution code:
import heapq

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

sum_a = sum(A[:N])
sum_b = sum(A[2*N:])

a_heap = A[:N]
b_heap = list(map(lambda x: x*-1, A[2*N:]))

heapq.heapify(a_heap)
heapq.heapify(b_heap)

SUM_A = [0] * (N + 1)
SUM_B = [0] * (N + 1)

SUM_A[0] = sum_a
SUM_B[0] = sum_b

# x = -1 * heapq.heappop(A) # 最大値の取り出し
# heapq.heappush(A, -1*x)  # 要素の挿入

for k in range(1, N + 1):
    heapq.heappush(a_heap, A[(N - 1) + k])
    heapq.heappush(b_heap, -A[(2 * N) - k])

    a1 = heapq.heappop(a_heap)
    b1 = -1 * heapq.heappop(b_heap)

    SUM_A[k] = SUM_A[k - 1] + A[(N - 1) + k] - a1
    SUM_B[k] = SUM_B[k - 1] + A[(2 * N) - k] - b1


print(max(map(lambda x: x[0]-x[1], zip(SUM_A, SUM_B[::-1]))))

Submission status: Accepted

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

C = A[0:N]
S = sum(C)
prefix = [S]
heapq.heapify(C)
for i in range(N, 2*N):
  heapq.heappush(C,A[i])
  popped = heapq.heappop(C)
  S = S + A[i] - popped
  prefix.append(S)

C = [-e for e in A[2*N:]]
S = -sum(C)
suffix = [S]
heapq.heapify(C)
for i in range(2*N-1, N-1, -1):
  heapq.heappush(C,-A[i])
  popped = heapq.heappop(C)
  S = S + A[i] - (-popped)
  suffix.append(S)

res = -10**15 
j = len(suffix)-1
for i in range(len(prefix)):
  res = max(res, prefix[i] - suffix[j])
  j -= 1

print(res)

Submission status: Accepted

Solution code:
"""
配列Aの中で仕切りを設けて、前半候補と後半候補に分ける。
仕切りを設ける位置は、N番目の要素の後ろから、2N-1番目の要素の後ろまで。
仕切りから左側が前半候補で仕切りから右側が後半候補。
最初、仕切りがN番目の要素の後ろにある状態から始める。
この次点では前半候補の数はN個なので、前半候補すべてが正規の前半メンバー(?)となる。
仕切りがこの初期位置からどんどん右側にずれていっても、前半の総和がこの初期値より小さくなることはない。
なぜなら、仕切りの移動に伴って増えていく前半候補の値が、もとの前半メンバーのどの値よりも小さければ、
そいつを正規メンバーに入れなければいい話だからだ。
逆に、新しく増えた前半候補の値が、もとの前半メンバーのどれかよりも大きければ、もとの前半メンバーの中で最も小さい要素を取り除き、
新しく増えた前半候補を正規メンバーに取り込む。
これはheapqを使うことで効率的に実装できる。

次に後半部分について考えてみよう。基本的な考え方は前半部分と同じ。
違うのは、前半部分はできるだけ大きくしなくては行けなかったのに対し、後半部分はできるだけ小さくしなくては行けないということ。
最初は仕切りを2N-1の後ろに設けておく。このとき、仕切りより右側にある要素が初期の後半メンバーである。
仕切りをどんどん左側にずらしていって、新しく増えた要素が元のどの後半メンバーよりも大きければ後半メンバーとして採用しない。
後半メンバーのどれかより小さければ、もとの後半メンバーの中で最も大きい要素を取り除き、新しく増えた後半候補を後半メンバーに加えればいい。
これは通常のheapqでは実装できないので、後半の値に-1を乗じることで、heapqに対応できるようにする。
"""
import heapq
N = int(input())
A = list(map(int,input().split()))
firstMember = A[:N]
firstSum = sum(firstMember)
memo1 = [firstSum]
heapq.heapify(firstMember)
for i in range(N,2*N):
    heapq.heappush(firstMember,A[i])
    firstSum += A[i] - heapq.heappop(firstMember)
    memo1.append(firstSum)

A = A[::-1]
for i in range(3*N):
    A[i] = -1*A[i]
latterMember = A[:N]
latterSum = sum(latterMember)
memo2 = [latterSum*-1]
heapq.heapify(latterMember)
for i in range(N,2*N):
    heapq.heappush(latterMember,A[i])
    latterSum += A[i] - heapq.heappop(latterMember)
    memo2.append(latterSum*-1)

memo2 = memo2[::-1]

ans = -1*float("INF")
for i in range(N+1):
    ans = max(ans,memo1[i]-memo2[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
a = list(map(int, input().split()))
m = len(a) // 2

cumsumA = []
prefix = [x for x in a[:N]]
heapq.heapify(prefix)
cumsumA.append(sum(prefix))
cursum = sum(prefix)
for k in range(N, 2*N):
  heapq.heappush(prefix, a[k])
  ele = heapq.heappop(prefix)
  cursum = cursum + a[k] - ele
  cumsumA.append(cursum)
  # cumsumA.append(sum(prefix))

cumsumB = []
suffix = [-x for x in a[2*N:]]
heapq.heapify(suffix)
cumsumB.append(-sum(suffix))
cursum = -sum(suffix)
for k in range(2*N-1, N-1, -1):
  heapq.heappush(suffix, -a[k])
  ele = heapq.heappop(suffix)
  cursum = cursum + a[k] + ele
  cumsumB.append(cursum)

res = -float('inf')
for i in range(0, len(cumsumA)):
  res = max(res, cumsumA[i] - cumsumB[len(cumsumA)-i-1])

print(res)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) #左側にAの左側からN個を追加
  heapq.heappush(R,-A[-1-i]) #右側数列にAの右側からN個を追加。多いほうから取り出すので-1倍

#左側の総和を求める。
ansL = [sum(L)]
for i in range(N):
  heapq.heappush(L,C[i])
  rmv = heapq.heappop(L)
  temp = ansL[i] + C[i] - rmv #一つ前の答え＋今新しく加えた数－最小値
  ansL.append(temp)
  #ansL.append(sum(L)) #sum(L)がO(N)かかっている？

ansR = [sum(R)]
for i in range(N):
  heapq.heappush(R,-C[-1-i])
  rmv = heapq.heappop(R)
  temp = ansR[i] - C[-1-i] - rmv
  ansR.append(temp)
  #ansR.append(sum(R)) #sum(R)がO(N)かかっている？

ans = -float('inf')
for i in range(N+1):
  temp = ansL[i]+ansR[-1-i]
  ans = max(ans,temp)
#print(ansL,ansR)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N,*A = map(int, open(0).read().split())
F = []
fs = 0
ss = 0
P = []
state = [0]*(3*N)
for i in range(N):
  heappush(F,A[i])
  fs += A[i]
ls = sorted(range(N,3*N),key=lambda x:A[x])
for i in range(N):
  state[ls[i]] = 1
  ss += A[ls[i]]
for i in range(N,2*N):
  state[ls[i]] = 2
  heappush(P,(A[ls[i]],ls[i]))
ans = fs-ss
for i in range(N,2*N):
  n = heappop(F)
  fs = fs-n+A[i]
  heappush(F,A[i])
  if state[i]==1:
    while state[P[0][1]]==0:
      heappop(P)
    p,j = heappop(P)
    ss += -A[i]+p
    state[j] = 1
  state[i] = 0
  ans = max(ans,fs-ss)
print(ans)