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:
from heapq import heappop, heapify, heappush

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

a_front = a[0 : n]
a_back = list(map(lambda x: -1*x, a[2*n : 3*n]))
heapify(a_front)
heapify(a_back)

sum_f = [0]*(n+1)
sum_b = [0]*(n+1)
sum_f[0] = sum(a_front)
sum_b[n] = sum(a_back)*-1

for i in range(n, 2*n):
    # 前半の処理
    heappush(a_front, a[i])
    sum_f[i-n+1] = sum_f[i-n] + a[i] - heappop(a_front)
    # 後半の処理
    heappush(a_back, a[3*n - i-1])
    sum_b[2*n-i-1] = sum_b[2*n-i] + a[3*n - i-1] + heappop(a_back)

ans = sum_f[0] - sum_b[0]
for i in range(1, n+1):
    tmp = sum_f[i] - sum_b[i]
    if tmp > ans:
        ans = tmp
        
print(ans)

Submission status: Wrong Answer

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

ans = -10**15
for i in range(n, 2*n):
    a_front = a[0 : i]
    a_back = a[i : 3*n]
    a_front.sort(reverse=True)
    a_back.sort()
    tmp = sum(a_front[0:n]) - sum(a_back[0:n])
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
arr = list(map(int,input().split()))
hq_l = arr[:N]
hq_r = list(map(lambda x:x*(-1),arr[-N:]))
heapq.heapify(hq_l)
heapq.heapify(hq_r)

l_sum = [0]*(N+1)
l_sum[0] = sum(hq_l)
r_sum = [0]*(N+1)
r_sum[-1] = -sum(hq_r)

for i in range(1,N + 1):
    heapq.heappush(hq_l,arr[N+i])
    a = heapq.heappop(hq_l)
    l_sum[i] = l_sum[i-1] + arr[N-1+i] - a
    heapq.heappush(hq_r,-arr[2*N-i])
    a = -heapq.heappop(hq_r)
    r_sum[-1-i] = r_sum[-i] + arr[2*N-i] - a

ans = -float('inf')
for l,r in zip(l_sum,r_sum):
    ans = max((l-r),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.buffer.readline


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

    Dm = -10**10
    for i in range(N, 2*N+1):
        MM = sum((sorted(A[:i])[::-1])[:N])
        mm = sum((sorted(A[i:]))[:N])
        if Dm < (MM-mm):
            Dm = MM - mm
    print(Dm)


main()

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = np.array(list(map(int, readline().split())))

    Dm = -10**10
    for i in range(N, 2*N):
        MM = np.sum((np.sort(A[:i])[::-1])[:N])
        mm = np.sum((np.sort(A[i:]))[:N])
        if Dm < (MM-mm):
            Dm = MM - mm
    print(Dm)


main()

Submission status: Wrong Answer

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

ans = 1-10**10
for i in range(n, 2*n+1):
    ll = a[:i]
    heapq.heapify(ll)
    for j in range(i-n):
        heapq.heappop(ll)
    rl = a[i:]
    heapq.heapify(rl)
    rsum = sum([heapq.heappop(rl) for _ in range(n)])
    ans = max(ans, sum(ll)-rsum)
    #print(ll, rsum, sum(ll)-rsum)
print(ans)

Submission status: Wrong Answer

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

ans = 1-10**10
for i in range(n, 2*n+1):
    ll = a[:i]
    heapq.heapify(ll)
    for j in range(i-n):
        heapq.heappop(ll)
    rl = a[i:]
    heapq.heapify(rl)
    rsum = 0
    for j in range(n):
        rsum += heapq.heappop(rl)
    ans = max(ans, sum(ll)-rsum)
    #print(ll, rsum, sum(ll)-rsum)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    x = heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    y = heapq.heappop(Q)
    sp = sp + R[i-1] - x
    sq = sq - R[-i] - y
    p[i] = sp
    q[i] = sq
ans = -(10*100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    x = heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    y = heapq.heappop(Q)
    sp = sp + R[i-1] - x
    sq = sq - R[-i] - y
    p[i] = sp
    q[i] = sq
ans = -1000000000
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    heapq.heappop(P)
    sp = sum(P)
    p[i] = sum(Q)
for i in range(1,N+1):
    heapq.heappush(Q,-R[-i])
    heapq.heappop(Q)
    sq = sum(Q)
    q[i] = sq

ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    heapq.heappop(Q)
    sp = sum(P)
    sq = sum(Q)
    p[i] = sp
    q[i] = sq
ans = -1000000000
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
import heapq
for i in range(N+1):
    P = A[:(N+i)]
    Q = A[(N+i):]
    for l in range(len(Q)):
        Q[l] *= -1
    heapq.heapify(P)
    heapq.heapify(Q)
    j = 0
    k = 0
    while j < i:
        heapq.heappop(P)
        j += 1
    while k < N-i:
        heapq.heappop(Q)
        k += 1
    s = sum(P) + sum(Q)
    S.append(s)
ans = min(S)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N=int(input())
l=list(map(int,input().split()))
ans=-10**9
for i in range(N,2*N):
  total_a=sum(l[:i])
  total_b=sum(l[i:])
  c=i-N
  d=2*N-i
  l1=l[:i]
  l2=[-n for n in l[i:]]
  heapq.heapify(l1)
  heapq.heapify(l2)
  while c>0:
    n1=heapq.heappop(l1)
    total_a-=n1
    c-=1
  while d>0:
    n2=heapq.heappop(l2)
    total_b+=n2
    d-=1
  ans=max(ans,total_a-total_b)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from heapq import heappushpop, heapify
    N = int(input())
    a = [int(val) for val in input().split()]
    first_half_sums = [0]*(N+1)
    second_half_sums = [0]*(N+1)

    first_half = a[:N]
    heapify(first_half)
    first_sum = sum(first_half)
    first_half_sums[0] = first_sum

    second_half = [-val for val in a[2*N:]]
    heapify(second_half)
    second_sum = sum(second_half)
    second_half_sums[0] = -second_sum

    for i in range(N):
        first_sum += a[i + N]
        first_sum -= heappushpop(first_half, a[i + N])
        first_half_sums[i + 1] = first_sum

        second_sum += -1 * a[2*N - (i+1)]
        second_sum -= heappushpop(second_half, -1 * a[2*N - (i+1)])
        second_half_sums[i+1] = -second_sum

    ans = 0
    for i in range(N+1):
        ans = max(ans, first_half_sums[i] - second_half_sums[N-i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from heapq import heappush, heappop, heapify
    N = int(input())
    a = [[int(val), i] for i, val in enumerate(input().split())]
    # N <= i < 2*Nの要素は一回選ぶが、後からscoreに足しこむ
    selection_zone = []
    heapify(selection_zone)

    # 最初の2*N個の大きい数からN個取り出す
    def func(x):
        x[0] = x[0] * -1
        return x
    first_half = list(map(func, a[:N])) + list(map(func, a[N:2*N]))
    heapify(first_half)

    score_first = 0
    first_cnt = 0
    for _ in range(N):
        val, i = heappop(first_half)
        if N <= i:
            first_cnt += 1
            heappush(selection_zone, [i, -1 * val])
        else:
            score_first += -1 * val

    # 後ろから2*N個（a[N:2*N]個の中では前半に選ばれた数は除く）の小さい数からN個取り出す
    second_half = [[i[0]*-1, i[1]] for i in first_half if N <= i[1]]
    heapify(second_half)
    for val in a[2*N:]:
        heappush(second_half, val)

    second_cnt = 0
    score_second = 0
    for _ in range(N):
        val, i = heappop(second_half)
        if i < 2*N:
            second_cnt += 1
            heappush(selection_zone, [i, val])
        else:
            score_second += val

    for _ in range(first_cnt):
        score_first += heappop(selection_zone)[1]
    for i, val in selection_zone:
        score_second += val

    print(score_first - score_second)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
f=a[0:n]
l=a[2*n:3*n]
for i in range(n):
    l[i]*=-1


mx=[0]*(n+1)
mn=[0]*(n+1)

import heapq

heapq.heapify(f)
heapq.heapify(l)

mx[0]=sum(f)
for i in range(n):
    x=f[0]
    if x<a[n+i]:
        mx[i+1]=mx[i]-x+a[n+i]
        heapq.heappop(f)
        heapq.heappush(f,a[n+i])
    else:
        mx[i+1]=mx[i]
mn[n]=sum(l)*-1

for i in range(n-1,-1,-1):
    x=l[0]
    if x<a[n+i]*-1:
        mn[i]=mn[i+1]+x+a[n+i]
        heapq.heappop(l)
        heapq.heappush(l,a[n+i]*-1)
    else:
        mn[i]=mn[i+1]
#print(mx,mn)
buf=float('inf')
buf*=-1
for i in range(n):
    buf=max(buf,mx[i]-mn[i])
    
print(buf)

Submission status: Wrong Answer

Solution code:
import heapq
def minus(x):
  return -x
N = int(input())
a = list(map(int, input().split()))
dpl = [0] * (N + 1)
dpr = [0] * (N + 1)
l = a[: N]
m = a[N: 2 * N]
r = list(map(minus, a[2 * N: ]))
heapq.heapify(l)
heapq.heapify(r)
dpl[0] = sum(l)
dpr[0] = sum(r)
for i in range(N):
  dpl[i + 1] = dpl[i] - heapq.heappop(l) + m[i]
  heapq.heappush(l, m[i])
  dpr[i + 1] = dpr[i] - heapq.heappop(r) - m[-1 - i]
  heapq.heappush(r, -m[-1 - i])
res = -(10 ** 16)
for i in range(N + 1):
  j = N - i
  res = max(res, dpl[i] + dpr[j])
print(res)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input = sys.stdin.buffer.readline
def minus(x):
  return -x
N = int(input())
a = list(map(int, input().split()))
dpl = [0] * (N + 1)
dpr = [0] * (N + 1)
l = a[: N]
m = a[N: 2 * N]
r = list(map(minus, a[2 * N: ]))
heapq.heapify(l)
heapq.heapify(r)
dpl[0] = sum(l)
dpr[0] = sum(r)
for i in range(N):
  dpl[i + 1] = dpl[i] - heapq.heappop(l) + m[i]
  heapq.heappush(l, m[i])
  dpr[i + 1] = dpr[i] - heapq.heappop(r) - m[-1 - i]
  heapq.heappush(r, -m[-1 - i])
res = -float("inf")
for i in range(N + 1):
  j = N - i
  res = max(res, dpl[i] + dpr[j])
print(res)

Submission status: Wrong Answer

Solution code:
import heapq

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

def solve(pre_ite,epi_ite,n):
    heapq.heapify(pre_ite)
    heapq.heapify(epi_ite)
    
    for _ in range(n):
        heapq.heappop(pre_ite)
    for _ in range(N-n):
        heapq.heappop(epi_ite)
        
    return sum(pre_ite)+sum(epi_ite)
        
ans=float('inf')*(-1)
for i in range(N,2*N):
    pre=A[:i]
    epi=A[i:]
    epi=[epi[j]*(-1) for j in range(len(epi))]
    
    ans=max(ans,solve(pre,epi,i-N))
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
dp = [0] * (N + 1)
l = sorted(a[: N], reverse = True)
m = a[N : 2 * N]
r = sorted(a[2 * N: 3 * N])
csl = [0, l[0]]
csm = [0, m[0]]
csr = [0, r[0]]
for i in range(2, N + 1):
  csl.append(csl[i - 1] + l[i - 1])
  csm.append(csm[i - 1] + m[i - 1])
  csr.append(csr[i - 1] + r[i - 1])
for i in range(N + 1):
  dp[i] = csl[-1 - i] + csm[i] - csr[i] - (csm[-1] - csm[i])
  #print(csl[-1 - i] + csm[i], csr[i] + (csm[-1] - csm[i]))
print(max(dp))

Submission status: Wrong Answer

Solution code:
import heapq
import numpy as np
n=int(input())
a=[int(i) for i in input().split()]

ans=float('-inf')
for i in range(n):
    a_mae=sorted(a[:n+i])
    a_ushiro=sorted(a[n+i:],reverse=True)
    a_ushiro=np.array(a_ushiro)
    a_ushiro=list(a_ushiro*(-1))

    for j in range(i):
        heapq.heappop(a_mae)
    for k in range(n-i):
        heapq.heappop(a_ushiro)
    ans=max(ans,sum(a_mae)+sum(a_ushiro))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import numpy as np
n=int(input())
a=[int(i) for i in input().split()]

ans=float('-inf')
for i in range(n):
    a_mae=sorted(a[:n+i])
    a_ushiro=sorted(a[n+i:],reverse=True)
    a_ushiro=np.array(a_ushiro)
    a_ushiro=list(a_ushiro*(-1))
    print(a_mae,a_ushiro)

    for j in range(i):
        heapq.heappop(a_mae)
    for k in range(n-i):
        heapq.heappop(a_ushiro)
    ans=max(ans,sum(a_mae)+sum(a_ushiro))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import numpy as np
n=int(input())
a=[int(i) for i in input().split()]

ans=float('-inf')
for i in range(n):
    a_mae=sorted(a[:n+i])
    a_ushiro=sorted(a[n+i:],reverse=True)
    a_ushiro=np.array(a_ushiro)
    a_ushiro=list(a_ushiro*(-1))

    for j in range(i):
        heapq.heappop(a_mae)
    for k in range(n-i):
        heapq.heappop(a_ushiro)
        ans=max(ans,sum(a_mae)+sum(a_ushiro))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq as h
n = int(input())
l = list(map(int,input().split()))
ls = [0]*(n+1)
rs = [0]*(n+1)
ll = l[:n]
rl = list(map(lambda x:-x,l[2*n:]))
h.heapify(ll)
h.heapify(rl)
ls[0] = sum(ll)
rs[n] = sum(rl)
for i in range(n):
  c = h.heappushpop(ll,l[n+i])
  ls[i+1] = ls[i] + l[n+i] - c
  c = h.heappushpop(rl,-l[2*n-1-i])
  rs[-2-i] = rs[-1-i] - l[2*n-i-1] - c
ans = - 10**12
for i in range(n+1):
  if ans < ls[i]+rs[i]:
    ans = ls[i]+rs[i]
print(ans)
# print(ls)
# print(rs)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10*5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
a = LIST()

a1 = a[:2*n]
a2 = a[n:]
a2.reverse()
for i in range(2*n):
    a2[i] = a2[i]*-1

def searchmax(a):
    print(a)
    maxl = [0]*(n+1)
    left = a[:n]
    center = a[n:]
    heapq.heapify(left)
    maxl[0] = sum(left)
    for i in range(1,n+1):
        heapq.heappushpop(left, center[i-1])
        maxl[i] = sum(left)
    print(maxl)
    return maxl

maxll = searchmax(a1)
minrr = searchmax(a2)
minrr.reverse()

res = [INF *-1]*(n+1)
for i in range(n+1):
    res[i] = maxll[i] + minrr[i]

print(max(res))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10*5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
a = LIST()

a1 = a[:2*n]
a2 = a[n:]
a2.reverse()
for i in range(2*n):
    a2[i] = a2[i]*-1

def searchmax(a):
    maxl = [0]*(n+1)
    left = a[:n]
    center = a[n:]
    heapq.heapify(left)
    maxl[0] = sum(left)
    for i in range(1,n+1):
        heapq.heappushpop(left, center[i-1])
        maxl[i] = sum(left)
    return maxl

maxll = searchmax(a1)
minrr = searchmax(a2)
minrr.reverse()

res = [INF *-1]*n
for i in range(n):
    res[i] = maxll[i] + minrr[i]

print(max(res))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10*5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
a = LIST()

a1 = a[:2*n]
a2 = a[n:]
a2.reverse()
for i in range(2*n):
    a2[i] = a2[i]*-1

def searchmax(a):
    maxl = [0]*(n+1)
    left = a[:n]
    center = a[n:]
    heapq.heapify(left)
    maxl[0] = sum(left)
    for i in range(1,n+1):
        heapq.heapreplace(left, center[i-1])
        maxl[i] = max(sum(left),maxl[i-1])
    return maxl

maxll = searchmax(a1)
minrr = searchmax(a2)
minrr.reverse()

res = [INF *-1]*n
for i in range(n):
    res[i] = maxll[i] + minrr[i]

print(max(res))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
a = LIST()

l = a[:n]
r = a[2*n:]
m = a[n:2*n]
for i in range(len(r)):
    r[i] *= -1
heapq.heapify(l)
heapq.heapify(r)
m = deque(m)

res = sum(l) + sum(r)

for i in range(n):
    minl = heapq.heappop(l)
    minr = heapq.heappop(r)
    mfir = m.popleft()
    if i == n-1:
        mlas = mfir 
    else:
        mlas = m.pop()
    if mfir -minl >= -1 * (minr + mlas):
        res += mfir-minl
        heapq.heappush(l, mfir)
        heapq.heappush(r, minr)
        m.append(mlas)
    else:
        res += -1 * (minr + mlas)
        heapq.heappush(r, mlas*-1)
        heapq.heappush(l, minl)
        m.appendleft(mfir)

print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    L = A[:N]
    heapq.heapify(L)
    C = deque(A[N:2*N])
    R = list(map(lambda x: x*(-1), A[2*N:]))
    heapq.heapify(R)

    for _ in range(N):
        c_l = C[0]
        c_r = C[len(C)-1]
        l_min = heapq.heappop(L)
        r_max = heapq.heappop(R) * (-1)
        if c_l-l_min >= r_max-c_r:
            c_l = C.popleft()
            if c_l-l_min >= 0:
                heapq.heappush(L, c_l)
                heapq.heappush(R, r_max*(-1))
            else:
                heapq.heappush(L, l_min)
                heapq.heappush(R, r_max*(-1))
        else:
            c_r = C.pop()
            if r_max-c_r >= 0:
                heapq.heappush(L, l_min)
                heapq.heappush(R, c_r*(-1))
            else:
                heapq.heappush(L, l_min)
                heapq.heappush(R, r_max*(-1))
        # print(L)
        # print(C)
        # print(R)
    
    print(sum(L)+sum(R))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import heapq
n = int(input())
a = list(map(int, input().split()))
p = sum(a[:n])
m = sum(a[2*n:])
ansans=-10**9
plus = a[:n]
heapq.heapify(plus)
minus = list(map(lambda int: -int, a[2*n:]))
heapq.heapify(minus)
ans = [0]*(3*n)
ans[n-1]=p
for k in range(n, 2*n):
    p += a[k]
    heapq.heappush(plus, a[k])
    p -= heapq.heappop(plus)
    ans[k] = p

for k in range(2*n-1, n-1, -1):
    m += a[k]
    heapq.heappush(minus, -a[k])
    m -= -heapq.heappop(minus)
    ans[k-1]-=m
    ansans=max(ansans,ans[k-1])
print(ansans)

Submission status: Wrong Answer

Solution code:
import heapq

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

left = [0] * (N + 1)
right = [0] * (N + 1)
lq = a[:N]
rq = [0] * N
for i in range(N):
    rq[i] = -a[2 * N + i]
heapq.heapify(lq)
heapq.heapify(rq)
left[0] = sum(lq)
right[-1] = -sum(rq)
for i in range(N):
    new = a[N + i]
    heapq.heappush(lq, new)
    old = heapq.heappop(lq)
    left[i + 1] = left[i] - old + new
for i in range(N):
    new = -a[2 * N - i - 1]
    heapq.heappush(rq, new)
    old = heapq.heappop(rq)
    right[N - i - 1] = right[N - i] + old - new
ans = - 10 ** 10
for i in range(N + 1):
    ans = max(left[i] - right[i], ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
def main():

    N = int(input())
    A = list(map(int, input().split()))
    A1 = sorted(A[:N])
    A2 = A[N:2*N]
    A3 = sorted([-a for a in A[2*N:]])
    i, j = 0, N-1
    turn = 0
    while i <= j:
        if turn % 2 == 0:
            a = heapq.heappop(A1)
            heapq.heappush(A1, max(a, A2[i]))
            i += 1
        else:
            b = heapq.heappop(A3)
            b = -b
            heapq.heappush(A3, -min(b, A2[j]))
            j -= 1
        turn += 1
    # print(A1)
    # print(A3)
    return sum(A1) + sum(A3)

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

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()

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

a_max = a[:N]
a_min = a[2*N:]

a_max_sum = sum(a_max)
score = [a_max_sum]
heapq.heapify(a_max)
for i in range(N):
	heapq.heappush(a_max, a[N + i])
	a_max_sum += a[N + i]
	a_max_sum -= heapq.heappop(a_max)
	score.append(a_max_sum)
print(score)

a_min_sum = sum(a_min)
score[N] -= a_min_sum
for i in range(len(a_min)):
	a_min[i] *= -1
heapq.heapify(a_min)
for i in range(N):
	heapq.heappush(a_min, -a[2*N - 1 - i])
	a_min_sum += a[2*N - 1 - i]
	a_min_sum += heapq.heappop(a_min)
	score[N - i - 1] -=a_min_sum

print(max(score))

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()

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

a_max = a[:N]
a_min = a[2*N:]

a_max_sum = sum(a_max)
score = [a_max_sum]
heapq.heapify(a_max)
for i in range(N):
	heapq.heappush(a_max, a[N + i])
	a_max_sum += a[N + i]
	a_max_sum -= heapq.heappop(a_max)
	score.append(a_max_sum)
print(score)

a_min_sum = sum(a_min)
score[N] -= a_min_sum
for i in range(len(a_min)):
	a_min[i] *= -1
heapq.heapify(a_min)
for i in range(N):
	heapq.heappush(a_min, -a[2*N - 1 - i])
	a_min_sum += a[2*N - 1 - i]
	a_min_sum += heapq.heappop(a_min)
	score[N - i - 1] -=a_min_sum
print(score)

print(max(score))

Submission status: Wrong Answer

Solution code:
import heapq

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

plus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n, 2*n):
    plus[i-1] = s
    heapq.heappush(tmp, a[i])
    s += a[i]
    s -= tmp[0]
    heapq.heappop(tmp)
plus[2*n-1] = s

a = [-x for x in a][::-1]
minus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n, 2*n):
    minus[i-1] = s
    heapq.heappush(tmp, a[i])
    s += a[i]
    s -= tmp[0]
    heapq.heappop(tmp)
minus[2*n-1] = s
minus = minus[::-1]
ans = plus[n-1] + minus[n]
for i in range(n-1, 2*n-1):
    ans = max(ans, plus[i] + minus[i+1])

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

plus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n, 2*n):
    plus[i-1] = s
    heapq.heappush(tmp, a[i])
    s += a[i]
    s -= tmp[0]
    heapq.heappop(tmp)
plus[2*n-1] = s

a = [-x for x in a][::-1]
minus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n, 2*n):
    minus[i-1] = s
    heapq.heappush(tmp, a[i])
    s += a[i]
    s -= tmp[0]
    heapq.heappop(tmp)
minus[2*n-1] = s
minus = minus[::-1]
ans = -10**16
for i in range(n-1, 2*n-1):
    ans = max(ans, plus[i] + minus[i+1])

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

plus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n, 2*n+1):
    plus[i-1] = s
    heapq.heappush(tmp, a[i])
    s += a[i]
    s -= tmp[0]
    heapq.heappop(tmp)
plus[2*n] = s

a = [-x for x in a][::-1]
minus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n, 2*n+1):
    minus[i-1] = s
    heapq.heappush(tmp, a[i])
    s += a[i]
    s -= tmp[0]
    heapq.heappop(tmp)
minus[2*n] = s
minus = minus[::-1]
ans = -10**16
for i in range(n-1, 2*n-1):
    ans = max(ans, plus[i] + minus[i+1])

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

plus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n, 2*n+1):
    plus[i-1] = s
    heapq.heappush(tmp, a[i])
    s += a[i]
    s -= tmp[0]
    heapq.heappop(tmp)

a = [-x for x in a][::-1]
minus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n, 2*n+1):
    minus[i-1] = s
    heapq.heappush(tmp, a[i])
    s += a[i]
    s -= tmp[0]
    heapq.heappop(tmp)
minus = minus[::-1]
ans = -10**16
for i in range(n-1, 2*n-1):
    ans = max(ans, plus[i] + minus[i+1])

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

plus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n+1):
    plus[n+i-1] = s
    heapq.heappush(tmp, a[n+i])
    s += a[n+i]
    s -= tmp[0]
    heapq.heappop(tmp)

a = [-x for x in a][::-1]
minus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n+1):
    minus[n+i-1] = s
    heapq.heappush(tmp, a[n+i])
    s += a[n+i]
    s -= tmp[0]
    heapq.heappop(tmp)
minus = minus[::-1]
ans = -10**16
for i in range(n-1, 2*n-1):
    ans = max(ans, plus[i] + minus[i+1])

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

plus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n+1):
    plus[n+i-1] = s
    heapq.heappush(tmp, a[n+i])
    s += a[n+i]
    s -= tmp[0]
    heapq.heappop(tmp)

a = [-x for x in a][::-1]
minus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n+1):
    minus[n+i-1] = s
    heapq.heappush(tmp, a[n+i])
    s += a[n+i]
    s -= tmp[0]
    heapq.heappop(tmp)
minus = minus[::-1]
ans = -10**10
for i in range(n-1, 2*n-1):
    ans = max(ans, plus[i] + minus[i+1])

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

plus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n+1):
    plus[n+i-1] = s
    heapq.heappush(tmp, a[n+i])
    s += a[n+i]
    s -= tmp[0]
    heapq.heappop(tmp)

a = [-x for x in a][::-1]
minus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n+1):
    minus[n+i-1] = s
    heapq.heappush(tmp, a[n+i])
    s += a[n+i]
    s -= tmp[0]
    heapq.heappop(tmp)
minus = minus[::-1]
ans = -10**10
for i in range(n, 2*n):
    ans = max(ans, plus[i] + minus[i+1])

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq


def main():
    n = int(input())
    a = list(map(int, input().split()))
    firstList = []
    for i in a[:n]:
        heapq.heappush(firstList, i)
    secondList = []
    for i in a[n:]:
        heapq.heappush(secondList, i)
    firstSum = sum(firstList)
    secondSum = sum(secondList[:n])
    ans = firstSum - secondSum
    # print(ans, firstSum, secondSum, firstList, secondList)
    for x in [a[i] for i in range(n, 2 * n)]:
        heapq.heappush(firstList, x)
        firstList0 = heapq.heappop(firstList)
        secondListn = secondList[n]
        secondList.remove(x)
        firstSum += x - firstList0
        secondSum -= x - secondListn if x < secondListn else 0
        ans = max(ans, firstSum - secondSum)
        # print(ans, firstSum, secondSum, firstList, secondList)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect


def main():
    n = int(input())
    a = list(map(int, input().split()))
    firstList = sorted(a[:n])
    secondList = sorted(a[n:])
    ans = -float("inf")
    for i in range(n, 2 * n):
        bisect.insort_left(firstList, a[i])
        secondList.remove(a[i])
        firstSum = sum(firstList[-n:])
        secondSum = sum(secondList[:n])
        ans = max(ans, firstSum - secondSum)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/arc074/tasks/arc074_b

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

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

    # front
    front = []
    front_sum = 0
    for i in range(n):
        front_sum += al[i]
        heappush(front, al[i])

    front_sums = [front_sum]
    for i in range(n, n * 2):
        minimum = heappop(front)
        if minimum < al[i]:
            front_sum += al[i] - minimum
            heappush(front, al[i])
        else:
            heappush(front, minimum)
        front_sums.append(front_sum)

    # back
    back = []
    back_sum = 0
    for i in range(n * 2, n * 3):
        back_sum += al[i]
        heappush(back, -al[i])

    back_sums = [back_sum]
    for i in range(n * 2 - 1, n - 1, -1):
        maximum = -heappop(back)
        if maximum > al[i]:
            back_sum += al[i] - maximum
            heappush(back, -al[i])
        else:
            heappush(back, -maximum)
        back_sums.append(back_sum)

    back_sums.reverse()

    # print(front_sums)
    # print(back_sums)

    ans = -10**10
    for f, b in zip(front_sums, back_sums):
        ans = max(ans, f - b)

    print(ans)


if __name__ == '__main__':
    main()