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:
#!/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

    right = 0
    tmp = [[i, L[i]] for i in range(n, 3*n)]
    tmp.sort()
    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])
    
    max_score = left - right
    heapify(l_h)
    heapify(sub_member_r_h)
    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 要素で使われているものが失われた
            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
        max_score = max(max_score, left - right)
    
    print(max_score)






if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ala = sorted(al[:n*2])
temp = sum(ala[n:n*2])-sum(al[n*2:])
score = temp

alb = sorted(ala[:n],reverse = True)
alc = list(reversed(al[:n*2]))
ald = sorted(al[n*2:],reverse =True)

for i in range(n):
    temp = temp + (alb[i] -alc[i]) -( alc[i]- ald[i])
    score = max(score,temp)
print(score)

Submission status: Wrong Answer

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)
      if j in used or j >= i:
        continue
      Sl += l - a
      used.add(j)
      break
  ans = max(ans, Sl - Sr)

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

sa = 0
sb = 0
hf = []
hb = []
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])

ans = sa-sb
for i in range(n,2*n):
    now = A[i]
    
    l = -heapq.heappop(hb)
    
    if now < l:
        ans = max(ans,sa-sb+l-now)
    heapq.heappush(hb,-l)
    h = heapq.heappop(hf)
    
    if now > h:
        sa += now-h
        heapq.heappush(hf,now)
        ans = max(ans,sa-sb)
    else:
        heapq.heappush(hf,h)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

sa = 0
sb = 0
hf = []
hb = []
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])

ans = sa-sb
for i in range(n,2*n):
    now = A[i]
    
    l = -heapq.heappop(hb)
    
    if now < l:
        ans = sa-sb+l-now
    heapq.heappush(hb,-l)
    h = heapq.heappop(hf)
    
    if now > h:
        sa += now-h
        heapq.heappush(hf,now)
        ans = max(ans,sa-sb)
    else:
        heapq.heappush(hf,h)
    
ans = max(ans,sa-sb)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

sa = 0
sb = 0
hf = []
hb = []
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])

ans = sa-sb
for i in range(n,2*n):
    now = A[i]
    
    l = -heapq.heappop(hb)
    
    if now < l:
        ans = sa-sb+l-now
        heapq.heappush(hb,-l)
    h = heapq.heappop(hf)
    
    if now > h:
        sa += now-h
        heapq.heappush(hf,now)
        ans = max(ans,sa-sb)
    else:
        heapq.heappush(hf,h)
    
ans = max(ans,sa-sb)
print(ans)

Submission status: Wrong Answer

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 - 1):
    ans = max(ans, left[i] - right[i + 1])
print(ans)

Submission status: Wrong Answer

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')
print(left)
print(right)
for i in range(n - 1, 2 * n - 1):
    ans = max(ans, left[i] - right[i + 1])
print(ans)

Submission status: Wrong Answer

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 + heapq.heappop(suf) + a[i]
    right[i] = suf_sum
ans = - (10 ** 50)
for i in range(n - 1, 2 * n - 1):
    ans = max(ans, left[i] - right[i + 1])
print(ans)

Submission status: Wrong Answer

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 = {}
left[n] = sum(pre)
right[2 * n] = -sum(suf)
for i in range(n - 1, 2 * n):
    heapq.heappush(pre, a[i])
    heapq.heappop(pre)
    left[i] = sum(pre)
for i in range(2 * n - 1, n - 1, -1):
    heapq.heappush(suf, -a[i])
    heapq.heappop(suf)
    right[i] = -sum(suf)
ans = - (10 ** 50)
for i in range(n - 1, 2 * n - 1):
    ans = max(ans, left[i] - right[i + 1])
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import insort

n = int(input().strip())
a = list(map(int, input().split()))
pre = a[:n]
suf = a[2 * n:]
pre.sort()
suf.sort()
i = n
j = 2 * n - 1
while True:
    if j < i:
        break
    ad_pre = a[i] - pre[0]
    ad_suf = suf[-1] - a[j]
    if ad_pre < ad_suf:
        suf = suf[:-1]
        insort(suf, a[j])
        j -= 1
    else:
        pre = pre[1:]
        insort(pre, a[i])
        i += 1
print(sum(pre) - sum(suf))

Submission status: Wrong Answer

Solution code:
from bisect import insort

n = int(input().strip())
a = list(map(int, input().split()))
pre = a[:n]
suf = a[2 * n:]
pre.sort()
suf.sort()
i = n
j = 2 * n - 1
while True:
    if j < i:
        break
    ad_pre = a[i] - min(pre)
    ad_suf = max(suf) - a[j]
    if ad_pre < ad_suf:
        suf = suf[:-1]
        insort(suf, a[j])
        j -= 1
    else:
        pre = pre[1:]
        insort(pre, a[i])
        i += 1
print(sum(pre) - sum(suf))

Submission status: Wrong Answer

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

hb=heapq.heapify(before)
after=a[n+1:]
after.sort()
af=sum(after[:n])
ans=sum(before)-af

for i in range(n,2*n+1):
    heapq.heappush(before,a[i])
    heapq.heappop(before)
    after=a[i+1:]
    if len(after)>=n:
        after.sort()
        tmp=sum(after[:n])
        ans=max(ans,sum(before)-tmp)

print(ans)

Submission status: Wrong Answer

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):
  min_s1=heapq.heappop(hq1)
  heapq.heappush(hq1,alist[i])
  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):
  max_s2=-heapq.heappop(hq2)
  heapq.heappush(hq2,-alist_rev[i])
  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: Wrong Answer

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):
        r = max(r, f[i] - l[-1-i])
    return r
print(main())

Submission status: Wrong Answer

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 = -pow(10, 100)
    for i in range(N):
        r = max(r, f[i] - l[-1-i])
    return r
print(main())

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0-sum(a)

for k in range(n):
    maxi=a[0:n+k]
    maxi.sort()
    maxi.reverse()
    p=sum(maxi[0:n])
    mini=a[2*n-k:3*n]
    mini.sort()
    q=sum(mini[0:n])
    if ans<p-q:
        ans=p-q

print(ans)

Submission status: Wrong Answer

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

dp = [[-float('inf')] * (N + 1) for _ in range(2 * N + 1)]
for i in range(2 * N + 1):
    dp[i][0] = 0
for i in range(2 * N):
    for j in range(1, N + 1):
        dp[i + 1][j] = max(dp[i][j], dp[i][j - 1] + A[i])

dp2 = [0] * N
for i in range(N):
    B = A[i + N:]
    B.sort()
    dp2[i] = sum(B[:N])

ans = - 10 ** 10
for i in range(N):
    S1 = dp[i + N][N]
    S2 = dp2[i]
    ans = max(ans, S1 - S2)

print(ans)

Submission status: Wrong Answer

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

dp = [[-float('inf')] * (N + 1) for _ in range(2 * N + 1)]
for i in range(2 * N + 1):
    dp[i][0] = 0
for i in range(2 * N):
    for j in range(1, N + 1):
        dp[i + 1][j] = max(dp[i][j], dp[i][j - 1] + A[i])

dp2 = [0] * N
for i in range(N):
    B = A[i + N:]
    B.sort()
    dp2[i] = sum(B[:N])

ans = 0
for i in range(N):
    S1 = dp[i + N][N]
    S2 = dp2[i]
    ans = max(ans, S1 - S2)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


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

q1 = []
S1 = 0
for i in range(N):
    heappush(q1, A[i])
    S1 += A[i]

q2 = []
S2 = 0
for i in range(2 * N, 3 * N):
    heappush(q2, -A[i])
    S2 += A[i]
    

cur1 = N
cur2 = 2 * N - 1
cnt = 0
while cnt < N:
    d1 = A[cur1] - q1[0]
    d2 = -A[cur2] + (-q2[0])
    if d1 >= d2:
        S1 -= heappop(q1)
        S1 += A[cur1]
        cur1 += 1
        cnt += 1
    else:
        S2 -= -heappop(q2)
        S2 += A[cur2]
        cur2 -= 1
        cnt += 1

print(S1 - S2)

Submission status: Wrong Answer

Solution code:
import sys
import heapq

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

	left = a[0 : N]
	right = a[N*2 : N*3]

	for i in range(N):
		right[i] *= -1

	left_sum = 0
	right_sum = 0

	heap_left = []
	heap_right = []

	for i in range(N):
		left_sum += left[i]
		heapq.heappush(heap_left, left[i])
		right_sum += right[i]
		heapq.heappush(heap_right, right[i])

	temp1 = [0] * (N + 1)
	temp2 = [0] * (N + 1)

	temp1[0] = left_sum
	temp2[N] = right_sum

	for i in range(0, N):
		left_sum += a[N+i]
		heapq.heappush(heap_left, a[N+i])
		left_sum -= heapq.heappop(heap_left)
		temp1[i+1] = left_sum

	for i in range(0, N):
		right_sum -= a[N*2-1-i]
		heapq.heappush(heap_right, -a[N*2-1-i])
		right_sum -= heapq.heappop(heap_right)
		temp2[N - 1 - i] = right_sum

	ans = -1000000000
	for i in range(0, N + 1):
		x = temp1[i] + temp2[i]
		if(ans < x):
			ans = x
	print(ans)
main()

Submission status: Wrong Answer

Solution code:
import heapq
n=int(input())
a=list(map(int,input().split()))
s1=sum(a[:n])
hq1=a[:n]
heapq.heapify(hq1)
A=[s1]
for i in range(n,2*n):
  s1+=a[i]
  heapq.heappush(hq1,a[i])
  x=heapq.heappop(hq1)
  s1-=x
  A.append(s1)
a=a[::-1]
s2=sum(a[:n])
hq2=a[:n]
heapq.heapify(hq2)
B=[s2]
for i in range(n,2*n):
  s2+=a[i]
  heapq.heappush(hq2,a[i])
  x=heapq.heappop(hq2)
  s2-=x
  B.append(s2)
B=B[::-1]
ans=-10**18
for i in range(len(A)):
  ans=max(ans,A[i]-B[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

pre = [0]*(n+1)
pre_list = [e for e in A[:n]]
heapq.heapify(pre_list)
pre_sum = sum(pre_list)
pre[0] = pre_sum
for i in range(n, 2*n):
    small = heapq.heappushpop(pre_list, A[i])
    pre_sum += A[i] - small
    pre[i-n+1] = pre_sum

suf = [0]*(n+1)
suf_list = [-e for e in A[2*n:]]
heapq.heapify(suf_list)
suf_sum = -sum(suf_list)
suf[-1] = suf_sum
for i in range(2*n-1, n-1, -1):
    large = -heapq.heappushpop(suf_list, A[i])
    suf_sum += A[i] - large
    suf[i-n] = suf_sum

# print(pre)
# print(suf)

print(max([pre[i] - suf[i] for i in range(n+1)]))

Submission status: Wrong Answer

Solution code:
import copy
n=int(input())
a=list(map(int,input().split()))
import heapq as hq
f1=[0]*(3*n)
f1[n-1]=sum(a[:n])
h=copy.deepcopy(a[:n])
hq.heapify(h)
su=f1[n-1]
for i in range(n,2*n):
    cur=a[i]
    x=hq.heappop(h)
    if cur>x:
        su-=x
        su+=cur
        hq.heappush(h,cur)
    else:
        hq.heappush(h,x)
    f1[i]=su
f2=[0]*(3*n)
f2[2*n]=sum(a[2*n:])
su=f2[2*n]
h2=[]
for i in a[2*n:]:
    h2.append(-i)
hq.heapify(h2)
for i in range(2*n-1,n-1,-1):
    cur=a[i]
    x=-1*hq.heappop(h2)
    if cur<x:
        su-=x
        su+=cur
        hq.heappush(h2,cur)
    else:
        hq.heappush(h2,-x)
    f2[i]=su
ans=-float('inf')
for i in range(n-1,2*n):
    ans=max(ans,f1[i]-f2[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
import heapq as hq
f1=[0]*(3*n)
f1[n-1]=sum(a[:n])
h=a[:n]
hq.heapify(h)
su=f1[n-1]
for i in range(n,3*n):
    cur=a[i]
    x=hq.heappop(h)
    if cur>x:
        su-=x
        su+=cur
        hq.heappush(h,cur)
    else:
        hq.heappush(h,x)
    f1[i]=su
f2=[0]*(3*n)
f2[2*n]=sum(a[2*n:])
su=f2[2*n]
h2=[]
hq.heapify(h2)
for i in a[2*n:]:
    hq.heappush(h2,-i) #maxheap 
for i in range(2*n-1,-1,-1):
    cur=a[i]
    x=-1*hq.heappop(h2)
    if cur<x:
        su-=x
        su+=cur
        hq.heappush(h2,cur)
    else:
        hq.heappush(h2,-x)
    f2[i]=su
ans=-float('inf')
for i in range(n-1,2*n):
    ans=max(ans,f1[i]-f2[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq 
n = int(input())
An = list(map(int, input().split()))
former = An[:n]
latter = An[2*n:]
latter = list(map(lambda x:-x, latter))
heapq.heapify(former)
heapq.heapify(latter)

sum_former = sum(former)
sum_latter = sum(latter)

former_list = [0]*(n+1) 
latter_list = [0]*(n+1) 
former_list[0] = sum_former 
latter_list[0] = sum_latter 

for i in range(n, 2*n):
  heapq.heappush(former, An[i])
  m = heapq.heappop(former)
  former_list[i-n+1] = former_list[i-n] + An[i] - m 

for i in range(2*n-1, n-1, -1):
  heapq.heappush(latter, -An[i])
  m = heapq.heappop(latter)
  latter_list[2*n-i] = latter_list[2*n-i-1] - An[i] - m

latter_list.reverse()
ans = -float('inf')
for i in range(n):
  ans = max(ans, former_list[i]+latter_list[i])
print(ans)

Submission status: Wrong Answer

Solution code:

import heapq 
n = int(input())
An = list(map(int, input().split()))
former = An[:n]
latter = An[2*n:]
latter = list(map(lambda x:-x, latter))
heapq.heapify(former)
heapq.heapify(latter)

sum_former = sum(former)
sum_latter = sum(latter)

former_list = [0]*(n+1) 
latter_list = [0]*(n+1) 
former_list[0] = sum_former 
latter_list[0] = sum_latter 

for i in range(n, 2*n):
  heapq.heappush(former, An[i])
  m = heapq.heappop(former)
  former_list[i-n+1] = former_list[i-n] + An[i] - m 

for i in range(2*n-1, n-1, -1):
  heapq.heappush(latter, -An[i])
  m = heapq.heappop(latter)
  latter_list[2*n-i] = latter_list[2*n-i-1] - An[i] - m

ans = 0
for i in range(n):
  ans = max(ans, former_list[i]+latter_list[n-i])
print(ans)

Submission status: Wrong Answer

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

b = list(enumerate(a))

l = sorted(b[:2*n], key=lambda x: x[1], reverse=True)
r = sorted(b[n:], key=lambda x: x[1])

big = [0] * (3*n)
small = [0] * (3*n)

for i, (pos, z) in enumerate(l):
    big[pos] = i
for i, (pos, z) in enumerate(r):
    small[pos] = i

first = sum(a[:n])
second = 0
for pos, z in r[:n]:
    second += z
left = sorted(big[:n], reverse=True)
i = 0
j = n-1
ans = first - second
for split in range(n, 2*n):
    if big[split] < left[i]:
        first += a[split]
        first -= l[left[i]][1]
        i += 1
    if small[split] <= j:
        second -= a[split]
        j += 1
        while r[j][0] < split:
            j += 1
        second += r[j][1]
    ans = max(ans, first - second)
print(ans)

Submission status: Wrong Answer

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

b = list(enumerate(a))

l = sorted(b[:2*n], key=lambda x: x[1], reverse=True)
r = sorted(b[n:], key=lambda x: x[1])

big = [0] * (3*n)
small = [0] * (3*n)

for i, (pos, z) in enumerate(l):
    big[pos] = i
for i, (pos, z) in enumerate(r):
    small[pos] = i

first = sum(a[:n])
second = 0
for pos, z in r[:n]:
    second += z
left = sorted(big[:n], reverse=True)
i = 0
right = n-1
ans = first - second
for split in range(n, 2*n):
    if big[split] < left[i]:
        first += a[split]
        first -= l[left[i]][1]
        i += 1
    if small[split] <= right:
        second -= a[split]
        right += 1
        while r[right][0] < split:
            right += 1
        second += r[right][1]
    ans = max(ans, first - second)
print(ans)

Submission status: Wrong Answer

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

import  heapq
cnt=[]
gg=[]
for i in range(n):
    cnt.append(a[i])
for i in range(2*n,3*n):
    gg.append(-a[i])

front=sum(cnt)
heapq.heapify(cnt)
after=-sum(gg)
heapq.heapify(gg)
ans=0
for i in range(n,2*n-1):
    heapq.heappush(cnt,a[i])
    tmp=heapq.heappop(cnt)
    front+=a[i]-tmp

    heapq.heappush(gg,(-1)*a[i+1])
    q=heapq.heappop(gg)
    after+=-a[i+1]+q
    anstmp=front-after
    print(front,after)
    ans=max(ans,anstmp)

print(ans)

Submission status: Wrong Answer

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

import  heapq
cnt=[]
gg=[]
for i in range(n):
    cnt.append(a[i])
for i in range(2*n,3*n):
    gg.append(-a[i])

front=sum(cnt)
heapq.heapify(cnt)
after=sum(gg)
heapq.heapify(gg)
ans=0
for i in range(n,2*n):
    heapq.heappush(cnt,a[i])
    heapq.heappop(cnt)
    front=max(front,sum(cnt))

    heapq.heappush(gg,(-1)*a[3*n-i-1])
    heapq.heappop(gg)
    after=max(after,sum(gg))
    ans=max(ans,front+after)

print(ans)

Submission status: Wrong Answer

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

import  heapq
cnt=[]
gg=[]
for i in range(n):
    cnt.append(a[i])
    gg.append((-1)*a[i])
front=sum(cnt)
heapq.heapify(cnt)
after=sum(gg)
heapq.heapify(gg)
ans=0
for i in range(n,2*n):
    heapq.heappush(cnt,a[i])
    heapq.heappop(cnt)
    front=max(front,sum(cnt))

    heapq.heappush(gg,(-1)*a[i])
    heapq.heappop(gg)
    after=max(after,sum(gg))
    ans=max(ans,front+after)

print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    wakeme = N
    Aleftsum = [0 for _ in range(3*N+1)]
    leftA = [x for x in A[:N]]
    heapq.heapify(leftA)
    subsum = sum(leftA)
    Aleftsum[wakeme] = subsum
    for i in range(N):
        heapq.heappush(leftA, A[wakeme + i])
        subsum += A[wakeme + i]
        subsum -= heapq.heappop(leftA)
        Aleftsum[wakeme+i+1] = subsum

    Arightsum = [0 for _ in range(3*N+1)]
    rightA = [-x for x in A[-N:]]
    heapq.heapify(rightA)
    subsum = sum(rightA)
    wakeme = 2*N
    Arightsum[wakeme] = -subsum
    for i in range(1, N+1):
        heapq.heappush(rightA, -A[wakeme-i])
        subsum -= A[wakeme - i]
        subsum -= heapq.heappop(rightA)
        Arightsum[wakeme - i] = -subsum
    ans = -inf
    for i in range(N, 2*N):
        ans = max(ans, Aleftsum[i] - Arightsum[i])
    print(ans)
main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import heapq

def main():
    mod=10**9+7
    N=I()
    a=LI()
    q1=a[:N]
    s1=[0]*(N+1)#境界を決めたときの，a'前半部分の最大値
    s1[0]=sum(q1)
    heapq.heapify(q1)
        
    q2=[]
    heapq.heapify(q2)
    s2=[0]*(N+1)
    for i in range(N):
        b=a[-1-i]*(-1)
        s2[0]+=b
        heapq.heappush(q2,b)
    
    
    for i in range(N):
        b=heapq.heappop(q1)
        s1[i+1]=s1[i]+a[i+N]-b
        
        c=heapq.heappop(q2)
        s2[i+1]=s2[i]+a[-1-N-i]*(-1)-c
        
    L=[0]*(N+1)
    ans=-1*10**16
    for i in range(N+1):
        temp=s1[i]+s2[-1-i]
        if ans<temp:
            ans=temp
    print(ans)
        
        
    

main()

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
Af = A[:N]
Ab = [-i for i in A[2*N:]]
asum = sum(Af)
bsum = -sum(Ab)
bsum2 = -sum(Ab)
heapq.heapify(Af)
heapq.heapify(Ab)
flist = [sum(Af)]
blist = []
for i in range(N,2*N):
    mina = heapq.heappop(Af)
    if A[i] > mina:
        asum = asum -mina + A[i]
        flist.append(asum)
        heapq.heappush(Af,A[i])        
    else:
        flist.append(asum)
        heapq.heappush(Af,mina)
    
for i in range(2*N-1,N-1,-1):
    maxa = heapq.heappop(Ab)
    if -A[i] > maxa:
        bsum2 = bsum2 + maxa +A[i]
        blist.append(bsum2)
        heapq.heappush(Ab,-A[i])
    else:
        blist.append(bsum2)
        heapq.heappush(Ab,maxa)    
blist = blist[::-1]
ans = -10**10
blist.append(bsum)
for i in range(N+1):
    ans = max(ans,flist[i]-blist[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
Af = A[:N]
Ab = [-i for i in A[2*N:]]
bsum = -sum(Ab)
heapq.heapify(Af)
heapq.heapify(Ab)
flist = [sum(Af)]
blist = []
for i in range(N,2*N):
    mina = heapq.heappop(Af)
    if A[i] > mina:
        flist.append(sum(Af)+A[i])
        heapq.heappush(Af,A[i])        
    else:
        flist.append(sum(Af)+mina)
        heapq.heappush(Af,mina)
    
for i in range(2*N-1,N-1,-1):
    maxa = heapq.heappop(Ab)
    if -A[i] > maxa:
        blist.append(-sum(Ab)+A[i])
        heapq.heappush(Ab,-A[i])
    else:
        blist.append(-sum(Ab)-maxa)
        heapq.heappush(Ab,maxa)    
blist = blist[::-1]
ans = -10**10
blist.append(bsum)
for i in range(N+1):
    ans = max(ans,flist[i]-blist[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

# d = [8, 2, 2, 7, 4, 6, 5, 3, 8]

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

ans = []

d1 = d[:N]
heapq.heapify(d[:N])
d2 = [-d[i] for i in range(2*N, 3*N)]
heapq.heapify(d2)
sum_d1 = sum(d1)
sum_d2 = sum(d2)

for k in range(N, 2 * N):
    x = d1[:]
    c = sum_d1
    c += d[k]
    n = heapq.heappushpop(x, d[k])
    c -= n

    y = d2[:]
    e = sum_d2
    e += -d[k]
    n = heapq.heappushpop(y, -1 * d[k])
    c -= n

    ans.append(c + e)

print(max(ans))

Submission status: Wrong Answer

Solution code:
import heapq

# d = [8, 2, 2, 7, 4, 6, 5, 3, 8]

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

ans = []

d1 = d[:N]
heapq.heapify(d[:N])
d2 = [-d[i] for i in range(2*N, 3*N)]
heapq.heapify(d2)
sum_d1 = sum(d1)
sum_d2 = sum(d2)

for k in range(N, 2 * N):
    x = d1[:]
    c = sum_d1
    c += d[k]
    c -= heapq.heappushpop(x, d[k])

    y = d2[:]
    e = sum_d2
    e += -d[k]
    e -= heapq.heappushpop(y, -1 * d[k])

    ans.append(c + e)

print(ans)
print(max(ans))

Submission status: Wrong Answer

Solution code:
import heapq

# d = [8, 2, 2, 7, 4, 6, 5, 3, 8]

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

ans = []

d1 = d[:N]
heapq.heapify(d[:N])
d2 = [-v for v in range(2*N, 3*N)]
heapq.heapify(d2)
sum_d1 = sum(d1)
sum_d2 = sum(d2)

for k in range(N, 2 * N):
    x = d1[:]
    c = sum_d1
    for j in range(N, k):
        c += d[j]
        c -= heapq.heappushpop(x, d[j])

    y = d2[:]
    e = -1 * sum_d2
    for j in range(k, 2 * N):
        e += d[j]
        e -= heapq.heappushpop(y, -1 * d[j]) * -1

    ans.append(c - e)

print(max(ans))