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: Wrong Answer

Solution code:
import heapq

n=int(input())
arr=list(map(int,input().split()))
q1=[]
tmp=0
for val in arr[:n]:
  heapq.heappush(q1,val)
  tmp+=val
sum1=[tmp]
for val in arr[n:2*n]:
  tmp=heapq.heappop(q1)
  if val>tmp:
    heapq.heappush(q1,val)
    sum1.append(sum1[-1]+(val-tmp))
  else:
    heapq.heappush(q1,tmp)
    sum1.append(sum1[-1])
print(sum1)
q2=[]
tmp=0
for val in arr[2*n:]:
  heapq.heappush(q2,-val)
  tmp+=val
sum2=[tmp]
for val in arr[2*n-1:n-1:-1]:
  tmp=-heapq.heappop(q2)
  if val<tmp:
    heapq.heappush(q2,-val)
    sum2.append(sum2[-1]+(val-tmp))
  else:
    heapq.heappush(q2,-tmp)
    sum2.append(sum2[-1])
sum2=sum2[::-1]
print(sum2)
ans=-10**18
for i in range(n+1):
  tmp=sum1[i]-sum2[i]
  ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n=int(input())
arr=list(map(int,input().split()))
q1=[]
tmp=0
for val in arr[:n]:
  heapq.heappush(q1,val)
  tmp+=val
sum1=[tmp]
for val in arr[n:2*n]:
  tmp=heapq.heappop(q1)
  heapq.heappush(q1,val)
  if val>tmp:
    sum1.append(sum1[-1]+(val-tmp))
  else:
    sum1.append(sum1[-1])
q2=[]
tmp=0
for val in arr[2*n:]:
  heapq.heappush(q2,-val)
  tmp+=val
sum2=[tmp]
for val in arr[2*n-1:n-1:-1]:
  tmp=-heapq.heappop(q2)
  heapq.heappush(q2,-val)
  if val<tmp:
    sum2.append(sum2[-1]+(val-tmp))
  else:
    sum2.append(sum2[-1])
sum2=sum2[::-1]
ans=-10**18
for i in range(n+1):
  tmp=sum1[i]-sum2[i]
  ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n=int(input())
arr=list(map(int,input().split()))
arr1=arr[:n]
arr2=arr[n:2*n]
arr3=arr[2*n:]
ans=sum(arr1)-sum(arr3)
q1=[]
q2=[]
for val in arr1:
  heapq.heappush(q1,val)
for val in arr3:
  heapq.heappush(q2,-val)
pos1=0
pos2=n-1
for _ in range(n):
  val1=heapq.heappop(q1)
  val2=-heapq.heappop(q2)
  d1=arr2[pos1]-val1
  d2=val2-arr2[pos2]
  if d1>0 and d1>=d2:
    heapq.heappush(q2,-val2)
    heapq.heappush(q1,arr2[pos1])
    ans+=d1
    pos1+=1
  elif d2>0 and d2>=d1:
    heapq.heappush(q1,val1)
    heapq.heappush(q2,-arr2[pos2])
    ans+=d2
    pos2-=1
  else:
    if d1<=d2:
      pos1+=1
    else:
      pos2-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

ans = -10**20

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

L = sorted(a[:N])
r = a[N:]
R = sorted(r, reverse=True)

for i in range(N):
    l_sum = sum(L[i:])
    r_sum = sum(R[N-i:])

    ans = max(ans, l_sum-r_sum)
    r_ = r.pop(0)
    R.remove(r_)
    bisect.insort_left(L, r_)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    num = int(input())
    data = list(map(int, input().split()))

    left_data = data[:num]
    left_data.sort()
    left_sum = sum(left_data)

    dp_left = [0 for i in range(num + 1)]
    dp_left[0] = left_sum

    for i in range(num):
        now_num = data[num + i]
        pop_data = left_data[0]
        left_data.pop(0)
        bisect.insort_left(left_data, now_num)
        left_sum += now_num - pop_data
        dp_left[i + 1] = left_sum

    right_data = data[2 * num :]
    right_sum = sum(right_data)

    dp_right = [0 for i in range(num + 1)]
    dp_right[0] = right_sum

    for i in range(num):
        now_num = data[2 * num - 1 - i]
        pop_data = right_data[-1]
        right_data.pop(-1)
        bisect.insort_left(right_data, now_num)
        right_sum += now_num - pop_data
        dp_right[i + 1] = right_sum
    dp_right = dp_right[::-1]

    ans = dp_left[-1] - dp_right[-1]
    for i in range(num):
        ans = max(ans, dp_left[i] - dp_right[i])

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    num = int(input())
    data = list(map(int, input().split()))

    left_heap = []
    left_sum = 0
    for i in range(num):
        left_sum += data[i]
        heapq.heappush(left_heap, data[i])

    dp_left = [0 for i in range(num + 1)]
    dp_left[0] = left_sum

    for i in range(num):
        now_num = data[num + i]
        pop_data = heapq.heappushpop(left_heap, now_num)
        left_sum += now_num - pop_data
        dp_left[i + 1] = left_sum

    right_heap = []
    right_sum = 0
    for i in range(num):
        right_sum += data[3 * num - 1 - i]
        heapq.heappush(right_heap, -data[3 * num - 1 - i])

    dp_right = [0 for i in range(num + 1)]
    dp_right[0] = right_sum

    for i in range(num):
        now_num = data[2 * num - 1 - i]
        pop_data = heapq.heappushpop(right_heap, -now_num)
        right_sum += now_num + pop_data
        dp_right[i + 1] = right_sum
    dp_right = dp_right[::-1]

    ans = -2 * 10 ** 10
    for i in range(num + 1):
        ans = max(ans, dp_left[i] - dp_right[i])

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
from copy import deepcopy

def main():
    num = int(input())
    data = list(map(int, input().split()))

    ans = -1 * 10 ** 10
    left_data = data[:num - 1]
    righ_data = data[num - 1:]
    righ_data.sort()
    left_data.sort()

    for i in range(num - 1, 2 * num):
        now_num = data[i]
        right_ind = bisect.bisect_left(righ_data, now_num)
        righ_data.pop(right_ind)

        bisect.insort_left(left_data, now_num)
        left_sum = sum(left_data[i - num + 1:])
        righ_sum = sum(righ_data[:num])
        ans = max(ans, left_sum - righ_sum)
        # print(left_sum, righ_sum)
        # print(left_data, righ_data)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
    num = int(input())
    data = list(map(int, input().split()))

    ans = -1 * 10 ** 10
    for i in range(num, 2 * num):
        left_data = data[:i]
        righ_data = data[i:]
        left_data.sort()
        righ_data.sort()
        left_sum = sum(left_data[i - num:])
        righ_sum = sum(righ_data[:num])
        ans = max(ans, left_sum - righ_sum)
        # print(left_sum, left_data)
        # print(righ_sum, righ_data)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
al=a[0:n]
am=a[n:2*n]
ar=a[n:3*n]

import bisect
al.sort()
ls=sum(al)
ar.sort()
rs=sum(ar[0:n])
ans=ls-rs
for i in range(n):
    p=am[i]
    l=bisect.bisect_left(al,p)
    if l==len(al):
        ls=ls-al[i]+p
        al.insert(l,p)
    elif l>=i:
        ls=ls-al[i]+p
        al.insert(l,p)
    else:
        al.insert(l,p)
    r=bisect.bisect_left(ar,p)
    if r>n:
        del ar[r]
    elif r<=n:
        rs=rs-p+ar[n]
        del ar[r]
    ans=max(ans,ls-rs)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
al=a[0:n]
am=a[n:2*n]
ar=a[n:3*n]

import bisect
al.sort()
ls=sum(al)
ar.sort()
rs=sum(ar[0:n])
ans=ls-rs
for i in range(n):
    p=am[i]
    l=bisect.bisect_left(al,p)
    if l==len(al):
        ls=ls-al[i]+p
        al=al[1:len(al)]+[p]
    elif l>i:
        ls=ls-al[i]+p
        al.insert(l,p)
    r=bisect.bisect_left(ar,p)
    if r>n:
        del ar[r]
    elif r<=n:
        rs=rs-p+ar[n]
        del ar[r]
    ans=max(ans,ls-rs)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=-10**20
for i in range(n):
    left=a[:n+i]
    left=sorted(left,reverse=True)
    right=a[n+i:]
    right.sort()
    ans=max(ans,sum(left[:n])-sum(right[:n]))
print(ans)

Submission status: Wrong Answer

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

heap = []
for i in range((3 * N+1)//2):
    heapq.heappush(heap, -1 * a[i])

ans = 0
for _ in range(N):
    ans -= heapq.heappop(heap)

heap = []
for i in range((3 * N+1)//2, 3 * N):
    heapq.heappush(heap, a[i])

for _ in range(N):
    ans -= heapq.heappop(heap)

print (ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
ans = -float('inf')
for i in range(N):
    L = a[:i+N]
    R = a[i+N:]
    L.sort()
    R.sort()
    ans = max(ans,sum(L[-N:]) - sum(R[:N]))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
L = a[:N]
R = a[2*N:]
l,r = N,2*N-1
for i in range(N):
    if a[l] - min(L) > max(R) - a[r]:
        L[L.index(min(L))] = a[l]
        l += 1
    else:
        R[R.index(max(R))] = a[r]
        r -= 1
print(sum(L)-sum(R))

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N = ii()
As = list(mi())
minusAs = [-a for a in As]

if N == 1:
  print(max(As[0:2]) + max(minusAs[1:3]))
  exit()

#下準備。左側0～N-1, 右側2N～3N-1のN要素のheapqを作っておく
#leftQは大きいのを残したい（最小値を取り除く）、rightQは小さいのを残したい（最大値を取り除く）ので、leftQはそのままの配列、rightQは符号反転したminusAsを使用する
leftQ = As[:N]
rightQ = minusAs[-N:]
heapq.heapify(leftQ)
heapq.heapify(rightQ)

#この配列のidxは、右端（左端）から何番目(0スタート)の区切りを採用するかを表す。あとで突き合わせる時に添字でバグらせないよう注意
leftsum = [0]*(N+1)
rightsum = [0]*(N+1) #どうせ最後に引くんだから、マイナスのまま入れちゃう
#つまり、最後に最小値を求める時は、逆に「最も大きい＝マイナス幅が小さいsum」を求めることになるので注意

#初期値はもう入れておく
leftsum[0] = sum(leftQ)
rightsum[0] = sum(rightQ)

for i in range(N, 2*N): #左端（右端）から最低N個（N-1まで）は済んでいる。残りはNまで～2N-1まで)
  #iがNのとき、左側は[:N], 右側は[-N:]
  #iが2Nのとき、左側は[0:2N], 右側は[-2N:]
  if leftQ[0] < As[i]: #大きいのを残したいので、最小値のが小さければ入れ替える
    #入れ替える
    nowmin = heapq.heappop(leftQ)
    leftsum[i-N+1] = leftsum[i-N] - nowmin + As[i]
    heapq.heappush(leftQ,As[i])
  else: leftsum[i-N+1] = leftsum[i-N] #そうでなければ入れ替えない
  if rightQ[0] < minusAs[-1-i]: #小さいのを残したいので、マイナス幅が大きければ入れ替える
    nowmax = heapq.heappop(rightQ)
    rightsum[i-N+1] = rightsum[i-N] - nowmax + minusAs[-1-i]
    heapq.heappush(rightQ,minusAs[-1-i])
  else: rightsum[i-N+1] = rightsum[i-N] #そうでなければ入れ替えない

ans = -INF
for lsum, rsum in zip(leftsum, rightsum[::-1]):
#  print(ans, lsum, rsum)
  ans = max(ans, lsum+rsum)

print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N = ii()
As = list(mi())
minusAs = [-a for a in As]

#下準備。左側0～N-1, 右側2N～3N-1のN要素のheapqを作っておく
#leftQは大きいのを残したい（最小値を取り除く）、rightQは小さいのを残したい（最大値を取り除く）ので、leftQはそのままの配列、rightQは符号反転したminusAsを使用する
leftQ = As[:N]
rightQ = minusAs[-N:]
heapq.heapify(leftQ)
heapq.heapify(rightQ)

#この配列のidxは、右端（左端）から何番目(0スタート)の区切りを採用するかを表す。あとで突き合わせる時に添字でバグらせないよう注意
leftsum = [0]*(N+1)
rightsum = [0]*(N+1) #どうせ最後に引くんだから、マイナスのまま入れちゃう
#つまり、最後に最小値を求める時は、逆に「最も大きい＝マイナス幅が小さいsum」を求めることになるので注意

#初期値はもう入れておく
leftsum[0] = sum(leftQ)
rightsum[0] = sum(rightQ)

for i in range(N, 2*N): #左端（右端）から最低N個（N-1まで）は済んでいる。残りはNまで～2N-1まで)
  #iがNのとき、左側は[:N], 右側は[-N:]
  #iが2Nのとき、左側は[0:2N], 右側は[-2N:]
  if leftQ[0] < As[i]: #大きいのを残したいので、最小値のが小さければ入れ替える
    #入れ替える
    nowmin = heapq.heappop(leftQ)
    leftsum[i-N+1] = leftsum[i-N] - nowmin + As[i]
    heapq.heappush(leftQ,As[i])
  else: leftsum[i-N+1] = leftsum[i-N] #そうでなければ入れ替えない
  if rightQ[0] < minusAs[-1-i]: #小さいのを残したいので、マイナス幅が大きければ入れ替える
    nowmax = heapq.heappop(rightQ)
    rightsum[i-N+1] = rightsum[i-N] - nowmax + minusAs[-1-i]
    heapq.heappush(rightQ,minusAs[-1-i])
  else: rightsum[i-N+1] = rightsum[i-N] #そうでなければ入れ替えない

ans = -100000000
for lsum, rsum in zip(leftsum, rightsum[::-1]):
#  print(ans, lsum, rsum)
  ans = max(ans, lsum+rsum)

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n=int(input())
A=[int(i) for i in input().split()]
AL=A[:n]
AR=[0]*n
for i in range(2*n,3*n):
  AR[i-2*n]-=A[i]
ALS,ARS=[0]*(n+1),[0]*(n+1)
ALS[0],ARS[0]=sum(AL),-sum(AR)
heapq.heapify(AL)
heapq.heapify(AR)
for i in range(n):
  l,r=A[n+i],-A[2*n-i-1]
  heapq.heappush(AL,l)
  ALS[i+1]=ALS[i]+l-heapq.heappop(AL)
  heapq.heappush(AR,r)
  ARS[i+1]=ARS[i]+r-heapq.heappop(AR)
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]-ARS[n-i])
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
A = list(map(int, input().split()))
 
L = A[:N]
heapq.heapify(L) 

sum_L = [0] * (N+1)
sum_L[0] = sum(L)

for i in range(N):
    min_L = heapq.heappushpop(L, A[N+i])
    sum_L[i+1] = sum_L[i] + A[N+i] - min_L
    #print(L, i, A[N+i], min_L, sum_L)

R = A[N*2:]
rev_R = list(map(lambda x: x*(-1), R))
heapq.heapify(rev_R) 

sum_R = [0] * (N+1)
sum_R[N] = sum(R)

for i in range(N-1, -1, -1):
    max_R = heapq.heappushpop( rev_R, A[N+i]*(-1) ) * (-1)
    sum_R[i] = sum_R[i+1] + A[N+i] - max_R
    # print(rev_R, i, A[N+i], max_R, sum_R)

ans = -10**14

for i in range(N):
    ans = max(ans, sum_L[i] - sum_R[i])

print(ans)

Submission status: Wrong Answer

Solution code:
def f(x):
    y=x[:n];heapify(y);z=sum(y);s=t=z
    for i in x[n:n*2]:z+=i-heappushpop(y,i);s,t=min(s,z),max(t,z);
    return s,t
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f([-i for i in a[n:][::-1]]),f(a)[::-1]))))

Submission status: Wrong Answer

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


front = A[:N]
back = list(map(lambda a: -a, A[2 * N:]))
heapq.heapify(front)
heapq.heapify(back)

X = deque(A[N: 2 * N])
for i in range(N):
    front_diff = X[0] - front[0]
    back_diff = - back[0] - X[-1]
    if front_diff >= back_diff:
        heapq.heapreplace(front, X.popleft())
    else:
        heapq.heapreplace(back, -X.pop())

print(sum(front) + sum(back))

Submission status: Wrong Answer

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

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

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

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

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

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

    ans = -10**10
    for i in range(N+1):
        ans = max(ans, F[i] - B[i])

    return ans


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

Submission status: Wrong Answer

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

answer=0

for i in range(N):
  a=sum(sorted(A[:N+i], reverse=True)[:N]) - sum(sorted(A[N+i:])[:N])
  answer=max(a,answer)
  
print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

l = []

for i in range(n,2*n):
    first = a[0:i]
    second = a[i:3*n]
    first.sort(reverse = True)
    second.sort()
    sum1 = sum(first[0:n])
    sum2 = sum(second[0:n])
    l.append(sum1-sum2)

print(max(l))

Submission status: Wrong Answer

Solution code:
import heapq

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

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

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

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import deque
x,y,z=[],[],[]
for i in range(3*N):
    if 0<=i<N:x.append(A[i])
    elif N<=i<2*N:y.append(A[i])
    elif 2*N<=i<3*N:z.append(A[i])
x.sort()
z.sort()
now=sum(x)-sum(y)
ans=now
for i in range(N):
    nex=now-x[i]-z[i]+2*y[i]
    ans=max(now,nex)
    now=nex
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

left_seq = sorted(a[0:n])
right_seq =  sorted(a[2*n:3*n])
left_sum = [0]*(n+1)
right_sum = [0]*(n+1)
left_sum[0] =  sum(left_seq) 
right_sum[n] =  sum(right_seq) 

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

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

Submission status: Wrong Answer

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

left_seq = sorted(a[0:n])
right_seq =  sorted(a[2*n:3*n])
left_sum = [0]*(n+1)
right_sum = [0]*(n+1)
left_sum[0] =  sum(left_seq) 
right_sum[n] =  sum(right_seq) 

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

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

Submission status: Wrong Answer

Solution code:
import heapq

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

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

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


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

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

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

    ans = max(ans, sum1 - sum2)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque
#import copy as cp
n = int(input())
a = input().split()
a = [int(m) for m in a]
#t1 = []
altt1 = []
t2 = deque()
mt2 = deque()
#t3 = []
mt3 = []
for i in range(3 * n):
    if i < (3 * n) // 3:
        altt1.append(a[i])
        #t1.append(a[i])
    elif (3 * n) // 3 <= i < (3 * n) // 3 * 2:
        t2.append(a[i])
        mt2.append(-a[i])
    else:
        #t3.append(a[i])
        mt3.append(-a[i])
altt1.sort()
#t1.sort()
#t2.sort()
#mt2.sort()
#t3.sort()
mt3.sort()
#t3.sort(reverse=True)

for _ in range(n):
    pp = heappop(altt1)
    qq = (-heappop(mt3))
    heappush(altt1, pp)
    heappush(mt3, -qq)
    if t2 != []:
        if (t2[0]) - pp >= qq - t2[-1] and (t2[0]) - pp > 0:
            #heappush(t1, t2[0])
            heappush(altt1, t2[0])
            t2.popleft()
            mt2.popleft()
            #heappop(t1)
            heappop(altt1)
        elif (t2[0]) - pp <= qq - t2[-1] and qq - t2[-1] > 0:
            #heappush(t3, t2[-1])
            heappush(mt3, -t2[-1])
            t2.pop()
            mt2.pop()
            #heappop(t3)
            heappop(mt3)
        elif (t2[0]) - pp >= qq - t2[-1] and (t2[0]) - pp <= 0:
            #heappush(t1, t2[0])
            #heappush(altt1, t2[0])
            t2.popleft()
            mt2.popleft()
            #heappop(t1)
        elif (t2[0]) - pp <= qq - t2[-1] and qq - t2[-1] <= 0:
            #heappush(t3, t2[-1])
            #heappush(mt3, t2[-1])
            t2.pop()
            mt2.pop()
            #heappop(t1)
print(sum(altt1) - (-sum(mt3)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
#notfirst =[]
#heappush(notfirst, f[i][1])
#donyoku -= heappop(notfirst)
import copy as cp
n = int(input())
a = input().split()
a = [int(m) for m in a]
t1 = []
altt1 = []
t2 = []
mt2 = []
t3 = []
mt3 = []
for i in range(3 * n):
    if i < (3 * n) // 3:
        altt1.append(a[i])
        t1.append(a[i])
    elif (3 * n) // 3 <= i < (3 * n) // 3 * 2:
        t2.append(a[i])
        mt2.append(-a[i])
    else:
        t3.append(a[i])
        mt3.append(-a[i])
altt1.sort()
t1.sort()
#t2.sort()
#mt2.sort()
t3.sort()
mt3.sort()
#t3.sort(reverse=True)

for _ in range(n):
    pp = heappop(altt1)
    qq = (-heappop(mt3))
    heappush(altt1, pp)
    heappush(mt3, -qq)
    #if (-heappop(t2)) - heappop(t1) > (-heappop(mt3)) - heappop(t2):
    if (t2[0]) - pp >= qq - t2[-1] and (t2[0]) - pp > 0:
        #heappush(t1, t2[0])
        heappush(altt1, t2[0])
        del t2[0]
        del mt2[0]
        #heappop(t1)
        heappop(altt1)
    elif (t2[0]) - pp <= qq - t2[-1] and qq - t2[-1] > 0:
        #heappush(t3, t2[-1])
        heappush(mt3, -t2[-1])
        del t2[-1]
        del mt2[-1]
        #heappop(t3)
        heappop(mt3)
    elif (t2[0]) - pp >= qq - t2[-1] and (t2[0]) - pp <= 0:
        #heappush(t1, t2[0])
        #heappush(altt1, t2[0])
        del t2[0]
        del mt2[0]
        #heappop(t1)
    elif (t2[0]) - pp <= qq - t2[-1] and qq - t2[-1] <= 0:
        #heappush(t3, t2[-1])
        #heappush(mt3, t2[-1])
        del t2[-1]
        del mt2[-1]
        #heappop(t1)
print(sum(altt1) - (-sum(mt3)))

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

al = A[:N]
ar = [-a for a in A[2*N:]]
ac = deque(A[N:2*N])
heapq.heapify(al)
heapq.heapify(ar)
while ac:
    gl = ac[0] - al[0]
    gr = -ar[0] - ac[-1]
    if gl < 0 and gr < 0:
        ac.pop()
        if ac:
            ac.popleft()
    elif gl > gr:
        heapq.heappop(al)
        tmp = ac.popleft()
        heapq.heappush(al, tmp)
    else:
        heapq.heappop(ar)
        tmp = ac.pop()
        heapq.heappush(ar, -tmp)
print(sum(al)+sum(ar))

Submission status: Wrong Answer

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

al = A[:N]
ar = [-a for a in A[2*N:]]
ac = deque(A[N:2*N])
heapq.heapify(al)
heapq.heapify(ar)
for i in range(N):
    gl = ac[0] - al[0]
    gr = -ar[0] - ac[-1]
    if gl < 0 and gr < 0:
        ac.pop()
    elif gl > gr:
        heapq.heappop(al)
        tmp = ac.popleft()
        heapq.heappush(al, tmp)
    else:
        heapq.heappop(ar)
        tmp = ac.pop()
        heapq.heappush(ar, -tmp)
print(sum(al)+sum(ar))

Submission status: Wrong Answer

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

al = A[:N]
ar = [-a for a in A[2*N:]]
ac = deque(A[N:2*N])
heapq.heapify(al)
heapq.heapify(ar)
for i in range(N):
    if ac[0]-al[0] > -ar[0]-ac[-1]:
        heapq.heappop(al)
        tmp = ac.popleft()
        heapq.heappush(al, tmp)
    else:
        heapq.heappop(ar)
        tmp = ac.pop()
        heapq.heappush(ar, -tmp)
print(sum(al)+sum(ar))

Submission status: Wrong Answer

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

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

from bisect import insort, bisect_left

N = int(input())
aN = list(map(int, input().split()))
mids = aN[N:N*2]
L = sorted(aN[:N])
R = sorted(aN[N:])

l = sum(L)
r = sum(R[:N])
ans = l - r
for i in range(N):
    insort(L, mids[i])
    l += mids[i]
    l -= L[i]
    if mids[i] >= R[N]:
        R.pop(bisect_left(R, mids[i]))
    else:
        R.pop(bisect_left(R, mids[i]))
        r -= mids[i]
        r += R[-(N-i)]
    ans = max(l - r, ans)
print(ans)