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

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

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

ans = []

d1 = []
d2 = []
for i in range(N):
    heapq.heappush(d1, d[i])
for i in range(2 * N, 3 * N):
    heapq.heappush(d2, -1 * d[i])
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))

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 = 0

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

    y = []
    for i in range(k, k+N):
        heapq.heappush(y, -1 * d[i])
    e = sum(y) * -1
    for j in range(k+N, 3 * N):
        e += d[j]
        e -= heapq.heappushpop(y, -1*d[j]) * -1

    ans = max(ans, c-e)

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 = []

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

    y = []
    for i in range(k, k+N):
        heapq.heappush(y, -1 * d[i])
    e = sum(y) * -1
    for j in range(k+N, 3 * N):
        e += d[j]
        e -= heapq.heappushpop(y, -1*d[j]) * -1

    ans.append(c - e)

print(max(ans))

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque
n=int(input())
left=[]
middle=deque([])
right=[]
A=list(map(int,input().split()))
for i in range(n):
  heapq.heappush(left,A[i])
for i in range(n):
  middle.append(A[n+i])
for i in range(n):
  heapq.heappush(right,A[2*n+i]*-1)
for i in range(n):
  a=middle[0]-left[0]
  b=right[0]*-1-middle[-1]
  if a>=b:
    heapq.heapreplace(left,middle[0])
    middle.popleft()
  else:
    heapq.heapreplace(right,middle[-1]*-1)
    middle.pop()
print(sum(left)+sum(right))

Submission status: Wrong Answer

Solution code:
import itertools
import math
import heapq

N = int(input())
nums = list(map(int,input().split(" ")))

half1 = nums[:N]
middle= nums[N:2 *N]
half2 = nums[2 *N:]
half2  = list(map(lambda x:-x ,half2) )

heapq.heapify(half1)
heapq.heapify(half2)
count = 0
l = 0
r = N - 1
for _ in range(N):

    if r < l:
        break
    h1 = half1[0]
    h2 = half2[0] # マイナスの値
    h2 *= -1
    middle_l = middle[l]
    middle_r = middle[r]
    if middle_l  < h1  and middle_r > h2: #入れ替えても意味のない場合 →中央のカウンタを進める
        c1 = h2 - middle_l
        c2 = middle_r - h1
        if c1 < c2:
            l += 1
        else:
            r -= 1
    else:
        if middle_l -  h1   >   h2 - middle_r: # 左と入れ替えた方が美味しい場合
            heapq.heappop(half1)
            heapq.heappush(half1,middle_l)
            l += 1
        else:
            heapq.heappop(half2)
            heapq.heappush(half2, middle_r)
            r -= 1
print(sum(half1) - sum(list(map(abs,(half2)))))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())

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

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

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

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

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


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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())

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

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

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

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())

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

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

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

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())

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

ans = -1*float("inf")
for k in range(N, 2*N):
    # 前半部分
    first_half = A[:k][:]
    heapq.heapify(first_half)
    # 長さがNになるまで小さい値を捨てる

    while len(first_half) != N:
        _ = heapq.heappop(first_half)

    total_f = sum(first_half)

    # 後半部分
    second_half = A[k:][:]
    heapq.heapify(second_half)

    # 小さいほうからN個取り出して合算
    total_s = 0
    for i in range(N):
        total_s += heapq.heappop(second_half)

    ans = max(ans, total_f - total_s)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from heapq import *

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

def main():
    first = a[:n]
    last = a[n*2:]
    cand = deque(a[n:n*2])

    heapify(first)
    for i in range(n):
        last[i] = -last[i]
    heapify(last)

    first_min = heappop(first)
    last_max = -heappop(last)

    for _ in range(n):
        if cand[0] - first_min >= last_max - cand[-1]:
            first_min = heappushpop(first, cand.popleft())
        else:
            last_max = -heappushpop(last, -cand.pop())

    heappush(first, first_min)
    heappush(last, -last_max)

    return sum(first) - (-sum(last))

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

Submission status: Wrong Answer

Solution code:
#3N numbers
n=int(input())
lists=list(map(int,input().split()))
second=lists.copy()
second=second[::-1]
for i in range(3*n):
    second[i]=-second[i]    
MAX=sum(lists[:n])
MIN=-sum(second[:n])
MAXlist=[0 for i in range(n+1)]
MINlist=[0 for i in range(n+1)]
MAXlist[0]=MAX
MINlist[0]=MIN
ANS=-10**100
import heapq
a=lists[:n]
b=second[:n]
heapq.heapify(a)  # リストを優先度付きキューへ
for j in range(n,2*n):
    heapq.heappush(a,lists[j])  # 要素の挿入    
    heapq.heappush(b,second[j])
    mini=heapq.heappop(a)  # 最小値の取り出し
    mini2=heapq.heappop(b)
    MAX-=mini
    MIN+=mini2
    MAX+=lists[j]
    MIN-=second[j]
    MAXlist[j+1-n]=MAX
    MINlist[j+1-n]=MIN
MINlist=MINlist[::-1]
for i in range(n+1):
    ANS=max(ANS,MAXlist[i]-MINlist[i])
print(ANS)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

Submission status: Wrong Answer

Solution code:
import heapq

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

h1 = []
h2 = []
for i in range(N):
    heapq.heappush(h1, A[i])
    heapq.heappush(h2, -A[-1-i])
    
i = N
j = 2*N-1
cnt = 0
while cnt < N:
    if A[i]-h1[0] < 0 and -h2[0]-A[j] < 0:
        if A[i]-h1[0] >= -h2[0]-A[j]:
            i += 1
        else:
            j -= 1
    elif A[i]-h1[0] >= -h2[0]-A[j]:
        heapq.heappop(h1)
        heapq.heappush(h1, A[i])
        i += 1
    else:
        heapq.heappop(h2)
        heapq.heappush(h2, -A[j])
        j -= 1
    cnt += 1
    
print(sum(h1)+sum(h2))

Submission status: Wrong Answer

Solution code:
import heapq

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

h1 = []
h2 = []
for i in range(N):
    heapq.heappush(h1, A[i])
    heapq.heappush(h2, -A[-1-i])
    
i = N
j = 2*N-1
cnt = 0
while cnt < N:
    if A[i]-h1[0] < 0 and -h2[0]-A[j] < 0:
        i += 1
    elif A[i]-h1[0] >= -h2[0]-A[j]:
        heapq.heappop(h1)
        heapq.heappush(h1, A[i])
        i += 1
    else:
        heapq.heappop(h2)
        heapq.heappush(h2, -A[j])
        j -= 1
    cnt += 1
    
print(sum(h1)+sum(h2))

Submission status: Wrong Answer

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


def input(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')


sys.setrecursionlimit(10**8)
inf = float('inf')
count = 0
ans = -inf
n = int(input())
A = list(map(int, input().split()))
AL = A[:n]
AR = A[2*n:]
AL.sort()
AR.sort(reverse=1)
i1 = i2 = j1 = j2 = 0
i = j = 0
ANL = A[n:2*n]
ANR = ANL[::-1]
LS = sum(AL)
RS = sum(AR)
heapq.heapify(AL)
AR = list(map(lambda ddd: -ddd, AR))

heapq.heapify(AR)
ans = max(ans, LS-RS)
# print(LS,RS)
for count in range(n):
    # print(AL,AR)
    # print(AL[i], AR[j], ANL[i], ANR[j], "test")
    if ANL[i]-AL[0] > -AR[0]-ANR[j]:
        LS = LS-heapq.heappop(AL)+ANL[i]
        heapq.heappush(AL,ANL[i])
        i += 1
    else:
        RS = RS+heapq.heappop(AR)+ANR[j]
        heapq.heappush(AR,-ANR[j])
        j += 1
    # print(LS, RS)
    ans = max(ans, LS-RS)
# print(AL,AR)

# Lm=min(AL)
# RM=max(AR)
print(ans)

Submission status: Wrong Answer

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


def input(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')


sys.setrecursionlimit(10**8)
inf = float('inf')
count = 0
ans = -inf
n = int(input())
A = list(map(int, input().split()))
AL = A[:n]
AR = A[2*n:]
AL.sort()
AR.sort(reverse=1)
i1 = i2 = j1 = j2 = 0
i = j = 0
ANL = A[n:2*n]
ANR = ANL[::-1]
LS = sum(AL)
RS = sum(AR)
heapq.heapify(AL)
AR = list(map(lambda ddd: -ddd, AR))

heapq.heapify(AR)
ans = max(ans, LS-RS)
# print(LS,RS)
for count in range(n):
    print(AL,AR)
    # print(AL[i], AR[j], ANL[i], ANR[j], "test")
    if ANL[i]-AL[0] > -AR[0]-ANR[j]:
        LS = LS-heapq.heappop(AL)+ANL[i]
        heapq.heappush(AL,ANL[i])
        i += 1
    else:
        RS = RS+heapq.heappop(AR)+ANR[j]
        heapq.heappush(AR,-ANR[j])
        j += 1
    # print(LS, RS)
    ans = max(ans, LS-RS)
print(AL,AR)

# Lm=min(AL)
# RM=max(AR)
print(ans)

Submission status: Wrong Answer

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


def input(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')


sys.setrecursionlimit(10**8)
inf = float('inf')
count = 0
ans = -inf
n = int(input())
A = list(map(int, input().split()))
AL = A[:n]
AR = A[2*n:]
AL.sort()
AR.sort(reverse=1)
i1 = i2 = j1 = j2 = 0
i = j = 0
ANL = A[n:2*n]
ANR = ANL[::-1]
LS = sum(AL)
RS = sum(AR)
heapq.heapify(AL)
AR = list(map(lambda ddd: -ddd, AR))

heapq.heapify(AR)
ans = max(ans, LS-RS)
# print(LS,RS)
for count in range(n):
    # print(AL[i], AR[j], ANL[i], ANR[j], "test")
    if ANL[i]-AL[0] > -AR[0]-ANR[j]:
        LS = LS-heapq.heappop(AL)+ANL[i]
        heapq.heappush(AL,ANL[i])
        i += 1
    else:
        RS = RS+heapq.heappop(AR)+ANR[j]
        heapq.heappush(AR,ANR[j])
        j += 1
    # print(LS, RS)
    ans = max(ans, LS-RS)

# Lm=min(AL)
# RM=max(AR)
print(ans)

Submission status: Wrong Answer

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


def input(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')


sys.setrecursionlimit(10**8)
inf = float('inf')
count = 0
ans = -inf
n = int(input())
A = list(map(int, input().split()))
AL = A[:n]
AR = A[2*n:]
AL.sort()
AR.sort(reverse=1)
i1 = i2 = j1 = j2 = 0
i = j = 0
ANL = A[n:2*n]
ANR = ANL[::-1]
LS = sum(AL)
RS = sum(AR)
heapq.heapify(AL)
AR = list(map(lambda ddd: -ddd, AR))

heapq.heapify(AR)
ans = max(ans, LS-RS)
# print(LS,RS)
for count in range(n):
    # print(AL[i], AR[j], ANL[i], ANR[j], "test")
    if ANL[i]-AL[0] > -AR[0]-ANR[j]:
        LS = LS-heapq.heappop(AL)+ANL[i]
        heapq.heappush(AL,ANL[i])
        i += 1

    else:
        RS = RS+heapq.heappop(AR)+ANR[j]
        j += 1
    # print(LS, RS)
    ans = max(ans, LS-RS)

# Lm=min(AL)
# RM=max(AR)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
count=0
ans=-inf
n=int(input())
A=list(map(int,input().split()))
AL=A[:n]
AR=A[2*n:]
AL.sort();AR.sort(reverse=1)
i1=i2=j1=j2=0
i=j=0
ANL=A[n:2*n]
ANR=ANL[::-1]
LS=sum(AL)
RS=sum(AR)
ans=max(ans,LS-RS)
# print(LS,RS)
for count in range(n):
    # print(AL[i],AR[j],"test")
    if ANL[i]-AL[i]>AR[j]-ANR[j]:
        LS=LS-AL[i]+ANL[i]
        i+=1
    else:
        RS=RS-AR[j]+ANR[j]
        j+=1
    # print(LS,RS)
    ans=max(ans,LS-RS)

# Lm=min(AL)
# RM=max(AR)
print(ans)

Submission status: Wrong Answer

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


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

examD()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ttl = a[0]
cst = 0

if a[0]>0:
    flg = 1
elif a[0] == 0:
    for i in range(1,n):
        if a[i]==0:
            continue
        elif a[i]>0:
            cst += 1
            ttl -= 1
            flg = -1
            break
        elif a[i]<0:
            cst += 1
            ttl += 1
            flg = 1
            break
else:
    flg = -1

for i in range(1,n):
    ttl += a[i]
    

    if ttl*flg < 0:
        flg *= -1
    else:
        if flg > 0:
            memo = abs(ttl)+abs(-1)
            ttl -= memo
            cst += memo
        elif flg < 0:
            memo = abs(ttl)+abs(-1)
            ttl += memo
            cst += memo
        flg *= -1
    

print(cst)

Submission status: Wrong Answer

Solution code:
maxi=-10**99 
n=int(input())
l=[int(i) for i in input().split()]
k=n
for i in range(n,2*n):
    z1=l[:i+1]
    z2=l[i+1:]
    z1.sort(reverse=1)
    z2.sort()
  #  print(i)
   # print(sum(z1[:k]))
   # print(sum(z2[:k]))
    maxi=max(maxi,sum(z1[:k])-sum(z2[:k]))
print(maxi)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = sorted(A[:N])
B1 = [0 for _ in range(N+1)]
for i in range(1,N+1):
    B1[i] = B1[i-1]+B[i-1]
C = A[N:2*N]
C1 = [0 for _ in range(N+1)]
for i in range(1,N+1):
    C1[i] = C1[i-1]+C[i-1]
D = sorted(A[2*N:],reverse=True)
D1 = [0 for _ in range(N+1)]
for i in range(1,N+1):
    D1[i] = D1[i-1]+D[i-1]
cnt = -10**14
for i in range(N+1):
    cnt = max(cnt,B1[-1]-B1[i]+C1[i]-(D1[-1]-D1[N-i]+C1[-1]-C1[i]))
print(cnt)

Submission status: Wrong Answer

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

for i in range(n):
  len_a = len(list_a)
  cut_place = len_a // 2
  if len_a % 2 == 0:
    med_a = (list_a[cut_place - 1] + list_a[cut_place]) / 2
    first_half = list_a[:cut_place]
    second_half = list_a[cut_place:]
  else:
    med_a = list_a[cut_place]
    first_half = list_a[:cut_place]
    second_half = list_a[(cut_place + 1):]

  diff_first = med_a - min(first_half)
  diff_second = max(second_half) - med_a
  if diff_first > diff_second:
    target_index = first_half.index(min(first_half))
    list_a.pop(target_index)
  else:
    if len_a % 2 == 0:
      target_index = cut_place + second_half.index(max(second_half))
    else:
      target_index = cut_place + 1 + second_half.index(max(second_half))
    list_a.pop(target_index)

cut_place = len(list_a) // 2
first_half = list_a[:cut_place]
second_half = list_a[cut_place:]
print(sum(first_half) - sum(second_half))

Submission status: Wrong Answer

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

import sys
from collections import deque
from heapq import heapify, heappush, heappop

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

N = INT()
A = LIST()

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

for i in range(N):
    # 左グループの最小を除いて真ん中グループの左端を追加する場合
    res1 = A2[0] - A1[0]
    # 右グループの最大を除いて真ん中グループの右端を追加する場合
    res2 = -A3[0] - A2[-1]
    # 得をする方の処理を行う
    if res1 >= res2:
        heappush(A1, A2.popleft())
        heappop(A1)
    else:
        heappush(A3, -A2.pop())
        heappop(A3)
print(sum(A1)-(-sum(A3)))

Submission status: Wrong Answer

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

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

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

S_pre = [pre]

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

large = A[:N]
small = A[-N:]
change = A[N:-N]
large.sort()
small.sort(reverse=True)

result = []
result.append(sum(large)-sum(small))
result.append(sum(large)-sum(change))
result.append(sum(change)-sum(small))

for i in range(1, N):
  a = large[i:] + change[:i]
  b = small[N-i:] + change[i:]
  result.append(sum(a)-sum(b))
print(max(result))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
n = int(input())
a = list(map(int, input().split()))
max_sum_fh = [0] * n
max_min_lh = [0] * n

hq_fh = []
hq_lh = []

for i in range(n):
    heappush(hq_fh, a[i])
    heappush(hq_lh, a[-1 - i])

print([heappop(hq_fh) for _ in range(n)])
print([heappop(hq_lh) for _ in range(n)])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, insort_left

def index(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

n = int(input())
a = list(map(int, input().split()))
fh = a[:n]
lh = a[n:]
sorted_lh = sorted(lh)
sorted_fh = sorted(fh)
min_fh_in_sum = min(fh)
max_lh_in_sum = sorted_lh[n - 1]
max_sum_fh = sum(sorted_fh)
min_sum_lh = sum(sorted_lh[:n])
#print(min_sum_lh)
score = -10 ** 14
cnt = 0
for i in range(n):
    x = lh[i]
    #print(x)
    insort_left(sorted_fh, x)
    #print(sorted_fh)
    if x > min_fh_in_sum:
        max_sum_fh = max_sum_fh + x - min_fh_in_sum   
        #print(max_sum_fh)
        cnt += 1
        min_fh_in_sum = sorted_fh[cnt]
    del sorted_lh[index(sorted_lh, x)]
    # print(sorted_lh)
    if x <= max_lh_in_sum:
        # print(min_sum_lh, x, sorted_lh[0])
        min_sum_lh = min_sum_lh - x + sorted_lh[n - 1]
        # print(min_sum_lh, x, sorted_lh[0])
        max_lh_in_sum = sorted_lh[n - 1]
    score = max(score, max_sum_fh - min_sum_lh)
print(score)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, y = LI()
    a = [1, 3, 5, 7, 8, 10, 12]
    b = [4, 6, 9, 11]
    c = [2]
    if x in a and y in a:
        print("Yes")
        return
    if x in b and y in b:
        print("Yes")
        return
    if x in c and y in c:
        print("Yes")
        return
    print("No")
    return

#B
def B():
    h, w = LI()
    print("#" * (w + 2))
    for _ in range(h):
        a = ["#"]
        for s in S():
            a.append(s)
        a.append("#")
        print("".join(a))
    print("#" * (w + 2))
    return

#C
def C():
    h, w = LI()
    ans = inf
    for i in range(1, h):
        ans = min(ans, max(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)) - min(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)))
        ans = min(ans, max(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w) - min(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w))
    h, w = w, h
    for i in range(1, h):
        ans = min(ans, max(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)) - min(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)))
        ans = min(ans, max(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w) - min(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w))
    print(ans)
    return

# D
# 解説AC
# ある点kにおいて2つに分けてa'の
# 前後半の要素を考える
# シンプルにわからなかった 
def D():
    n = II()
    a = LI()
    first_half_list = []
    final_half_list = []
    first_half_sum = deque([0])
    final_half_sum = deque([0])
    ans = -inf
    for i in range(n):
        heappush(first_half_list, a[i])
        first_half_sum[0] += a[i]
        heappush(final_half_list, -a[-i - 1])
        final_half_sum[0] -= a[-i - 1]
    for i in range(1, n + 1):
        q = heappop(first_half_list)
        heappush(first_half_list, max(q, a[i + n - 1]))
        first_half_sum.append(first_half_sum[-1] - q + max(q, a[i + n- 1]))
        q = heappop(final_half_list)
        heappush(final_half_list, max(q, -a[-n - i]))
        final_half_sum.appendleft(final_half_sum[-1] - q + max(q, -a[-n - i]))
    for i in range(n + 1):
        ans = max(ans, first_half_sum[i] + final_half_sum[i])
    print(ans)
    return


#Solve
if __name__ == '__main__':
    D()