Problem:


Score : 500 points

Problem Statement

Let N be a positive integer.

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

Find the maximum possible score of a'.

Constraints

1 ≤ N ≤ 10^5

a_i is an integer.

1 ≤ a_i ≤ 10^9

Partial Score

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

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{3N}

Output

Print the maximum possible score of a'.

Sample Input 1

2
3 1 4 1 5 9

Sample Output 1

1

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

Sample Input 2

1
1 2 3

Sample Output 2

-1

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

Sample Input 3

3
8 2 2 7 4 6 5 3 8

Sample Output 3

5

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



Sample input:
2
3 1 4 1 5 9


Sample output:
1

Submission status: Accepted

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

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

# (1).左からN + 1～2N個のデータについて、iがいくつあるかのdictionary
# (2).左から2N個のデータのうち、大きい順にN個のデータの和
# (3).左から2N個のデータのうち、小さい順にN個のデータを、大きい順にheapqに入れたもの
# (4).右からN個のデータの和
# (5).右からN個のデータを、大きい順にheapqに入れたもの

# 上記を用いて、iを2N～N+1までずらし、そのたびに
# A[i]の数を(1)から減らす
# 次の数を(3)から取り出す。その数が(1)に存在していなければ何もしない
# 取り出した数を(2)に足す
# (4)にA[i]を足す
# (5)から一つ取り出し、(4)から引く
# (2) - (4)の最大値を更新

from collections import defaultdict

sortA = sorted(A[:2 * N])
smallA = sortA[:N]
small_dic = defaultdict(int)
for i in range(len(smallA)):
  small_dic[smallA[i]] += 1
largeA = sortA[N:]
large_dic = defaultdict(int)
for i in range(len(largeA)):
  large_dic[largeA[i]] += 1

leftsum = sum(sortA[N:])

import heapq as hq
leftq = list(map(lambda x:-x,smallA))
hq.heapify(leftq)

rightq = A[2 * N:]
rightsum = sum(rightq)
rightq = list(map(lambda x:-x,rightq))
hq.heapify(rightq)

ans = leftsum - rightsum

#print("leftsum",leftsum,"rightsum",rightsum,"ans",ans)
for i in range(2 * N - 1, N - 1, -1):
  #print("i",i,"A[i]",A[i])
  if large_dic[A[i]] > 0: # 除外対象である場合
    large_dic[A[i]] -= 1
    leftsum -= A[i]
    while True:
      move = -hq.heappop(leftq)
      if small_dic[move] > 0:
        small_dic[move] -= 1
        break
    leftsum += move
    large_dic[move] += 1
    #print("leftsumから",A[i],"を除外",leftsum)
  else:
    small_dic[A[i]] -= 1
    
  hq.heappush(rightq, -A[i])
  rem = -hq.heappop(rightq)
  rightsum += A[i]
  rightsum -= rem
  
  if ans < leftsum - rightsum:
    ans = leftsum - rightsum
  #print("leftsum",leftsum,"rightsum",rightsum,"ans",ans)
    
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

fore = A[:N]
back = A[2 * N:]
back = [-i for i in back]
for_sum = sum(fore)
back_sum = sum(back)
heapq.heapify(fore)
heapq.heapify(back)

fore_list = []
back_list = []
for i in range(N):
    fore_list.append(for_sum)
    back_list.append(back_sum)
    in_fore = A[N + i]
    heapq.heappush(fore, in_fore)
    out_fore = heapq.heappop(fore)
    for_sum += in_fore - out_fore

    in_back = (-1) * A[-N - i - 1]
    heapq.heappush(back, in_back)
    out_back = heapq.heappop(back)
    back_sum += in_back - out_back

fore_list.append(for_sum)
back_list.append(back_sum)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=-10**18
a_minus=[-x for x in a]
af=a[:n]
ae=a_minus[2*n:]
f_sum=[sum(af)]
e_sum=[sum(ae)]
from heapq import heapify,heappop,heappush
heapify(af)
for aa in a[n:2*n]:
  heappush(af,aa)
  t=heappop(af)
  f_sum.append(f_sum[-1]+aa-t)
heapify(ae)
for aa in reversed(a[n:2*n]):
  heappush(ae,-aa)
  t=heappop(ae)
  e_sum.append(e_sum[-1]-aa-t)
for f,e in zip(f_sum,reversed(e_sum)):
  ans=max(ans,f+e)
print(ans)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = list(map(int, input().split()))
l, r = [], []
ll = 0
for i in range(3*N):
    if i < N:
        heapq.heappush(l, (A[i], i))
        ll += A[i]
    else:
        heapq.heappush(r, (A[i], i))
used = set()
rr = 0
for i in range(N):
    a, idx = heapq.heappop(r)
    used.add(idx)
    rr += a
ans = ll-rr
done = set()
for i in range(N,2*N):
    done.add(i)
    if A[i] > l[0][0]:
        ll -= l[0][0]
        heapq.heappop(l)
        heapq.heappush(l, (A[i], i))
        ll += A[i]
    if i in used:
        rr -= A[i]
        a, idx = heapq.heappop(r)
        while idx in done:
            a, idx = heapq.heappop(r)
        used.add(idx)
        rr += a
    #print(i, ll, rr, l, r)
    ans = max(ans, ll-rr)
print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""


n = onem()

a = l()

fl = a[:n]
ba = a[2*n:]



ba = list(map(lambda x:-x,ba))

po = cl.deque(a[n:2*n])

hq.heapify(fl)
fll = fl
hq.heapify(ba)
baa = ba
al = [sum(fll),sum(baa)]
best = [[0,0] for i in range(n+1)]
best[0] = [al[0],0]
best[-1] = [0,al[1]]
for i in range(n):
	aaa = hq.heappop(fll)
	bbb = po[i]
	if bbb >= aaa:
		hq.heappush(fll,bbb)
		best[i+1][0] = al[0] - aaa + bbb
		al[0] += -aaa + bbb
	else:
		hq.heappush(fll,aaa)
		best[i+1][0] = al[0]

for i in range(n-1,-1,-1):
	aaa = hq.heappop(baa)
	bbb = -po[i]
	if aaa <= bbb:
		hq.heappush(baa,bbb)
		best[i][1] = al[1] - aaa + bbb
		al[1] += -aaa + bbb
	else:
		hq.heappush(baa,aaa)
		best[i][1] = al[1]

ans = -Max

for i in range(n+1):
	ans = max(ans,best[i][0]+best[i][1])

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify


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

    left_sums = []
    left = A[:n]
    left_sum = sum(left)
    left_sums.append(left_sum)
    heapify(left)

    for a in A[n:2*n]:
        left_sum += a
        heappush(left, a)
        left_sum -= heappop(left)
        left_sums.append(left_sum)

    right_sums = []
    right = []
    for a in A[2*n:]:
        right.append(-a)
    right_sum = sum(right)
    right_sums.append(-right_sum)
    heapify(right)

    for a in A[2*n-1:n-1:-1]:
        right_sum += -a
        heappush(right, -a)
        right_sum -= heappop(right)
        right_sums.append(-right_sum)

    candidates = []
    for sum1, sum2 in zip(left_sums, right_sums[::-1]):
        candidates.append(sum1 - sum2)

    print(max(candidates))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

A = list(map(int,input().split()))
import heapq
L = A[:N]
heapq.heapify(L)
sum_L = sum(A[:N])
L_list = []
L_list.append(sum_L)
for i in range(N):
    sum_L += A[N+i]
    heapq.heappush(L,A[N+i])
    sum_L -= heapq.heappop(L)
    L_list.append(sum_L)

A = list(map(lambda x:-x, A[::-1]))
R = A[:N]
heapq.heapify(R)
sum_R = sum(A[:N])
R_list = []
R_list.append(sum_R)


for i in range(N):
    sum_R += A[N+i]
    heapq.heappush(R,A[N+i])
    sum_R -= heapq.heappop(R)
    R_list.append(sum_R)
maxi = -10000000000000000000000000000
R_list = R_list[::-1]
for i in range(N+1):
    maxi = max(maxi,L_list[i] + R_list[i])

print(maxi)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
left=[0]*(2*n+1)
right=[0]*(2*n+1)
now_a=a[:n]
left[n]=sum(now_a)
now_a.sort()
from heapq import heapify,heappop,heappush
heapify(now_a)
for i in range(n,2*n):
  if a[i]>now_a[0]:
    left[i+1]=left[i]+a[i]-now_a[0]
    heappop(now_a)
    heappush(now_a,a[i])
  else:
    left[i+1]=left[i]
b=[-x for x in a]
now_b=b[-n:]
right[n]=sum(now_b)
now_b.sort()
heapify(now_b)
for i in range(n,2*n):
  if b[-i-1]>now_b[0]:
    right[i+1]=right[i]+b[-i-1]-now_b[0]
    heappop(now_b)
    heappush(now_b,b[-i-1])
  else:
    right[i+1]=right[i]
ans=-pow(10,14)
for i in range(n+1):
  ans=max(ans,left[n+i]+right[2*n-i])
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

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


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

    first = a[:n]
    second = a[n:2 * n]
    third = a[2 * n:3 * n]

    first_max = [0] * (n + 1)
    third_min = [0] * (n + 1)

    first_max[0] = sum(first)
    third_min[0] = sum(third)

    pq_first = PriorityQueue(first)
    cur = first_max[0]
    for i, x in enumerate(second, 1):
        if pq_first.top() < x:
            cur -= pq_first.pop()
            cur += x
            pq_first.push(x)
        first_max[i] = cur

    pq_third = PriorityQueue(third, desc=True)
    cur = third_min[0]
    for i, x in enumerate(second[::-1], 1):
        if pq_third.top() > x:
            cur -= pq_third.pop()
            cur += x
            pq_third.push(x)
        third_min[i] = cur

    ans = -INF
    for i in range(n + 1):
        fi_idx = i
        th_idx = n - i
        ans = max(ans, first_max[fi_idx] - third_min[th_idx])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq


def solve(n):
  a = list(map(int,input().split()))
  # 左半分を計算して右端[n+idx]でメモ
  # 左半分は最大化したいので最小値が初めに出てくるようにする
  leftHsum = [0 for i in range(n+1)]
  leftH = a[0:n]
  heapq.heapify(leftH)
  leftHsum[0] = sum(leftH) # 
  for i in range(n):
    if leftH[0] < a[n+i]:
      leftHsum[i+1] = leftHsum[i] - leftH[0] + a[n+i]
      heapq.heappop(leftH)
      heapq.heappush(leftH, a[n+i])
    else:
      leftHsum[i+1] = leftHsum[i]
  # 右半分は負の値で保持する
  # もっとも大きい値から追い出していく
  rightHsum = [0 for i in range(n+1)]
  rightH = list(map(lambda x: -x,a[2*n:3*n]))
  heapq.heapify(rightH)
  rightHsum[0] = - sum(rightH)
  for i in range(n):
    if rightH[0] < -a[2*n-i-1]:
      rightHsum[i+1] = rightHsum[i] + rightH[0] + a[2*n-i-1]
      heapq.heappop(rightH)
      heapq.heappush(rightH, -a[2*n-i-1])
    else:
      rightHsum[i+1] = rightHsum[i]
  result = -1000000000000000000
  #print(leftHsum)
  #print(rightHsum)
  for i in range(n+1):
    result = max(result, leftHsum[0+i]-rightHsum[n-i])
  return result





n = int(input())
print(solve(n))

Submission status: Accepted

Solution code:
import heapq

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

R=sorted(A[:N])
SUM1=[sum(A[:N])]
for i in range(N,2*N):
    heapq.heappush(R,A[i])
    tmp=heapq.heappop(R)
    SUM1.append(SUM1[-1]+A[i]-tmp)

B=list(map(lambda x:x*(-1),A[2*N:3*N]))
B.sort()
SUM2=[-sum(B)]
for i in range(2*N-1,N-1,-1):
    heapq.heappush(B,-A[i])
    tmp=heapq.heappop(B)
    SUM2.append(SUM2[-1]+A[i]+tmp)

ans=-float("inf")
for i in range(N+1):
    ans=max(ans,SUM1[i]-SUM2[-(i+1)])
print(ans)

Submission status: Accepted

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

l_sum = [0 for _ in range(n+1)]
r_sum = [0 for _ in range(n+1)]

que = a[:n]
l_sum[0] = sum(que)
heapq.heapify(que)

for i in range(n):
    l_sum[i+1] = l_sum[i]

    if que[0] < a[n+i]:
        l_sum[i+1] += a[n+i] - que[0]
        heapq.heappop(que)
        heapq.heappush(que, a[n+i])


que = [-a[i] for i in range(2*n, 3*n)]
r_sum[0] = -sum(que)
heapq.heapify(que)

for i in range(n):
    r_sum[i+1] = r_sum[i]
    
    if -que[0] > a[2*n-1-i]:
        r_sum[i+1] += a[2*n-1-i] + que[0]
        heapq.heappop(que)
        heapq.heappush(que, -a[2*n-1-i])


ans = -1e15
for x in range(n+1):
    ans = max(ans, l_sum[x] - r_sum[n-x])

print(ans)

Submission status: Accepted

Solution code:
# 3 N numbers
import heapq
N = int(input())
a = list(map(int, input().split()))
S = sum(a[:N])
b = a[:N]
heapq.heapify(b)
dpmax = [S for i in range(N+1)]
# dpmax[x] = 前半　ｘ + N このうちmax N　このわを記録
for i in range(N, 2*N):
    heapq.heappush(b, a[i])
    d = heapq.heappop(b)
    S += a[i]-d
    dpmax[i-N+1] = S

c = a[-N:]
for i in range(N):
    c[i] = -c[i]
T = sum(c)
heapq.heapify(c)
dpmin = [-T for i in range(N+1)]

# dpmin[x]= 後半　x + N このうち　min Nこのわを記録する
for i in range(N, 2*N):
    heapq.heappush(c, -a[-1-i])
    d = heapq.heappop(c)
    T += -a[-1-i]-d
    dpmin[i+1-N] = -T

ans = -1000000000000000000000000000000
for i in range(N+1):
    ans = max(ans, dpmax[i]-dpmin[N-i])
print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    L = lmi()
    
    left = sum(L[:n])
    l_h = L[:n]    # 現在前半 n 要素で使っているやつらが入った min heap
    heapify(l_h)

    right = 0
    tmp = [[i, L[i]] for i in range(n, 3*n)]
    assert (len(tmp) == 2*n)
    tmp.sort(key=itemgetter(1))
    latter_min_nth = [False] * 3 * n    # 0...n-1 は意味なし, 後半 n 要素で使っている奴らがメモられたリスト
    sub_member_r_h = []    # 現在後半 n 要素の控えメンバーたちが入った min heap
    for ind in range(n):
        i, num = tmp[ind]
        right += num
        latter_min_nth[i] = True
    for ind in range(n, 2*n):
        i, num = tmp[ind]
        sub_member_r_h.append([num, i])
    heapify(sub_member_r_h)        
    

    max_score = left - right
    # print(max_score)
    for i in range(n, 2*n):
        # L[i] を前半で使える側へと移動する
        if l_h[0] < L[i]:
            # これを使った方が大きくできる
            left -= heappop(l_h)
            left += L[i]
            heappush(l_h, L[i])
        if latter_min_nth[i]:
            # 後半 n 要素で使われているものが失われた
            latter_min_nth[i] = False
            right -= L[i]
            while sub_member_r_h[0][1] <= i:
                heappop(sub_member_r_h)    # すでに使えないものは捨てる
            num, ind = heappop(sub_member_r_h)
            assert (ind > i)
            right += num
            latter_min_nth[ind] = True
        # print(f"{i} {left} {right}")
        max_score = max(max_score, left - right)
    
    print(max_score)


if __name__ == "__main__":
    main()



"""
15 
25 sub
"""

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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

L = [[a, i] for i, a in enumerate(A[:2*N])]
Sl = 0
heapify(L)
used = set()
for i in range(N):
  a, i = heappop(L)
  used.add(i)
  Sl -= a

R = A[2*N:].copy()
Sr = -sum(R)
heapify(R)

ans = Sl - Sr
for i in range(2*N-1, N-1, -1):
  a = - A[i]
  r =  - heappop(R)
  if a > r:
    heappush(R, -r)
  else:
    Sr += a - r
    heappush(R, -a)
  if i in used:
    while L:
      l, j = heappop(L)
      l *= -1
      if j < i:
        Sl += l - a
        used.add(j)
        break
  ans = max(ans, Sl - Sr)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    f=[0]*(N+1)
    s=[0]*(N+1)
    h=a[:N]
    heapify(h)
    f[0]=sum(a[:N])
    for i in range(N):
        heappush(h,a[N+i])
        f[i+1]=f[i]+a[N+i]-heappop(h)
    h=[-x for x in a[2*N:]]
    heapify(h)
    s[N]=sum(a[2*N:])
    for i in range(N):
        heappush(h,-a[2*N-i-1])
        s[N-i-1]=s[N-i]+a[2*N-i-1]+heappop(h)
    ans=-INF
    for x,y in zip(f,s):
        ans=max(ans,x-y)
    print(ans)
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

sa = 0
sb = 0
hf = []
hb = []
la = [[0]*2 for i in range(n+1)]
for i in range(n):
    sa += A[i]
    heapq.heappush(hf,A[i])
for i in range(2*n,3*n):
    sb += A[i]
    heapq.heappush(hb,-A[i])
la[0][0] = sa
la[-1][-1] = sb
for i in range(n,2*n):
    now = A[i]
    now2 = A[-1-i]
    heapq.heappush(hf,now)
    heapq.heappush(hb,-now2)
    h1 = heapq.heappop(hf)
    h2 = -heapq.heappop(hb)
    sa += now-h1
    sb += now2 -h2
    la[i-n+1][0] = sa
    la[-i+n-2][1] = sb

ans = -float("INF")
for i,j in la:
    ans = max(ans,i-j)
print(ans)

Submission status: Accepted

Solution code:
import heapq

n = int(input().strip())
a = list(map(int, input().split()))
pre = a[:n]
heapq.heapify(pre)
suf = list(map(lambda x: -x, a[(2 * n):]))
heapq.heapify(suf)
left = {}
right = {}
pre_sum = sum(pre)
suf_sum = -sum(suf)
left[n - 1] = pre_sum
right[2 * n] = suf_sum
for i in range(n, 2 * n):
    heapq.heappush(pre, a[i])
    pre_sum = pre_sum + a[i] - heapq.heappop(pre)
    left[i] = pre_sum
for i in range(2 * n - 1, n - 1, -1):
    heapq.heappush(suf, -a[i])
    suf_sum = suf_sum + a[i] + heapq.heappop(suf)
    right[i] = suf_sum
ans = -float('inf')
for i in range(n - 1, 2 * n):
    ans = max(ans, left[i] - right[i + 1])
print(ans)

Submission status: Accepted

Solution code:
import heapq
n= int(input())
a=list(map(int,input().split()))
pres = a[:n]
heapq.heapify(pres)
apresum = [0]*(n+1)
aps = sum(pres)
apresum[0]=aps
posts = list(map(lambda x: -1 * x, a[::-1][:n]))
heapq.heapify(posts)
apossum = [0]*(n+1)
aqs = sum(posts)
apossum[0]=aqs
for i in range(1,n+1):
    tempprea = a[n+i-1]
    tempposta = -1 * a[2*n-i]
    heapq.heappush(pres,tempprea)
    tempprepop=heapq.heappop(pres)
    aps += tempprea-tempprepop
    apresum[i]=aps
    heapq.heappush(posts,tempposta)
    temppostpop=heapq.heappop(posts)
    aqs += tempposta - temppostpop
    apossum[i]=aqs
print(max([x+y for x,y in zip(apresum,apossum[::-1])]))

Submission status: Accepted

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

sum1=0
hq1=[]
for i in range(N):
  sum1+=alist[i]
  heapq.heappush(hq1,alist[i])
sum1_list=[sum1]
for i in range(N,2*N):
  heapq.heappush(hq1,alist[i])
  min_s1=heapq.heappop(hq1)  
  sum1+=alist[i]-min_s1
  sum1_list.append(sum1)
#print(sum1_list)  
  
alist_rev=alist[::-1]  
sum2=0
hq2=[]
for i in range(N):
  sum2+=alist_rev[i]
  heapq.heappush(hq2,-alist_rev[i])
sum2_list=[sum2]
for i in range(N,2*N):
  heapq.heappush(hq2,-alist_rev[i])
  max_s2=-heapq.heappop(hq2)
  sum2+=alist_rev[i]-max_s2
  sum2_list.append(sum2)
sum2_list.reverse()
#print(sum2_list)  

answer=-float("inf")
for i in range(N+1):
  answer=max(answer,sum1_list[i]-sum2_list[i])

print(answer)

Submission status: Accepted

Solution code:
import heapq

def score(init, cand):
    
    score = [0] * (n+1)
    score[0] = sum(init)
    hp = init
    heapq.heapify(hp)
    
    for i,ai in enumerate(cand):
    
        if hp[0] < ai:
            min_a = heapq.heappop(hp)
            score[i+1] = score[i] + (ai - min_a)
            heapq.heappush(hp, ai)
        else:
            score[i+1] = score[i]
    
    return score
    
n = int(input())
a = list(map(int,input().split()))
minus_a = [-x for x in a[::-1]]

former_score = score(a[:n],a[n:2*n])
latter_score = score(minus_a[:n],minus_a[n:2*n])[::-1]

ans = max(x+y for x,y in zip(former_score,latter_score))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify, heappop, heappush
N = int(input())
tmp = list(map(int, input().split(' ')))
former_A = deque(tmp)
latter_A = deque(tmp.copy())
former_heap = list()
latter_heap = list()
for _ in range(N):
    former_heap.append(former_A.popleft())
    latter_heap.append(- latter_A.pop())
heapify(former_heap)
heapify(latter_heap)

former_sum = sum(former_heap)
former_sum_list = [former_sum]
for k in range(N):
    new_a = former_A.popleft()
    heappush(former_heap, new_a)
    min_a = heappop(former_heap)
    former_sum += new_a - min_a
    former_sum_list.append(former_sum)

latter_sum = sum(latter_heap)
latter_sum_list = [latter_sum]
for k in range(N):
    new_a = - latter_A.pop()
    heappush(latter_heap, new_a)
    min_a = heappop(latter_heap)
    latter_sum += new_a - min_a
    latter_sum_list.append(latter_sum)
latter_sum_list.reverse()

answer = max([former + latter for former, latter in zip(former_sum_list, latter_sum_list)])
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from heapq import heappop, heappush

n, *a = map(int, read().split())
a_rev = list(map(lambda x: int(x) * (-1), a[::-1]))


def get_sum_list(a):
    h = []
    res = []
    cnt = 0
    for i, aa in enumerate(a[:2 * n]):
        heappush(h, aa)
        cnt += aa
        if i >= n:
            cnt -= heappop(h)
        if i >= n - 1:
            res.append(cnt)
    return res


left = get_sum_list(a)
right = get_sum_list(a_rev)
ans = -float('inf')
for i in range(n + 1):
    memo = left[i] + right[n - i]
    if ans < memo:
        ans = memo
print(ans)

Submission status: Accepted

Solution code:
import heapq
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AH = sorted([(a, i) for i, a in enumerate(A[:2 * N])], reverse=True)
    AT = sorted(A[-N:])
    ATT = []
    for a in AT:
        heapq.heappush(ATT, -a)
    used = [False] * (2 * N)
    for _, i in AH[:N]:
        used[i] = True

    h = sum(a for a, _ in AH[:N])
    t = sum(AT)
    m = h - t
    hp = N
    for i in reversed(range(N, 2 * N)):
        t += A[i]
        t += heapq.heappushpop(ATT, -A[i])
        if used[i]:
            h -= A[i]
            while AH[hp][1] > i:
                hp += 1
            h += AH[hp][0]
            used[AH[hp][1]] = True
            hp += 1

        m = max(m, h - t)
    return m

print(main())

Submission status: Accepted

Solution code:
import heapq
def main():
    N = int(input())
    A = list(map(int, input().split()))
    fl = [i for i in A[:N]]
    f = [sum(A[:N])]
    heapq.heapify(fl)
    ll = [-i for i in A[2*N:]]
    l = [sum(A[2*N:])]
    heapq.heapify(ll)
    for i in range(N):
        s = f[-1]
        if A[N+i] > fl[0]:
            s = s - fl[0] + A[N+i]
            heapq.heappushpop(fl, A[N+i])
        f.append(s)
        s = l[-1]
        if - A[2*N-1-i] > ll[0]:
            s = s + ll[0] + A[2*N-1-i]
            heapq.heappushpop(ll, -A[2*N-1-i])
        l.append(s)
    r = f[0] - l[-1]
    for i in range(N+1):
        r = max(r, f[i] - l[-1-i])
    return r
print(main())

Submission status: Accepted

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

l, r = [], []
for i in range(N):
    heapq.heappush(l, a[i])
    heapq.heappush(r, -a[3*N-i-1])

lsum, rsum = [sum(l)], [sum(r)]
for i in range(N):
    heapq.heappush(l, a[i+N])
    lsum.append(lsum[-1] + a[i+N] - heapq.heappop(l))
    heapq.heappush(r, -a[3*N-i-N-1])
    rsum.append(rsum[-1] - a[3*N-i-N-1] - heapq.heappop(r))

ans = -float('inf')
for i in range(N+1):
    t = lsum[i]+rsum[N-i]
    if ans < t:
        ans = t
print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
left = [sum(A[:N])]
h1 = A[:N]
heapq.heapify(h1)
for i in range(N):
    heapq.heappush(h1, A[N+i])
    temp = heapq.heappop(h1)
    left.append(left[-1] + A[N+i] - temp)
right = [sum(A[2*N:])]
h2 = list(map(lambda x: -x, A[2*N:]))
heapq.heapify(h2)
for i in range(N):
    heapq.heappush(h2, -A[2*N-1-i])
    temp = -1 * heapq.heappop(h2)
    right.append(right[-1] + A[2*N-1-i] - temp)
ans = float('-inf')
for i in range(N+1):
    ans = max(ans, left[i] - right[-(i+1)])
print(ans)

Submission status: Accepted

Solution code:
import heapq

data = int(input())
array = [int(_) for _ in input().split()]

X = array[0:data]
B = array[data:2*data]
Y = [-_ for _ in array[2*data:3*data]]

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

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

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

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

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