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 sys
input = sys.stdin.readline
import heapq
n = int(input())
a = [int(i) for i in input().split()]
a_l = [];a_r = []
sum_a_l = 0
sum_a_r = 0
a = tuple(a)
import heapq
heapq.heapify(a_l);heapq.heapify(a_r)

for i in range(n):
  heapq.heappush(a_l,a[i])
  heapq.heappush(a_r,-a[3*n-1-i])
  sum_a_l += a[i]
  sum_a_r += a[3*n-1-i]
chk_1 = [sum_a_l]
chk_2 = [sum_a_r]
import collections
chk_1 = collections.deque(chk_1)
chk_2 = collections.deque(chk_2)
ans = -10**15
for i in range(n):
  #print(a_l,a_r)
  heapq.heappush(a_l,a[n+i])
  heapq.heappush(a_r,-a[2*n-1-i])
  x = heapq.heappop(a_l)
  y = heapq.heappop(a_r)
  chk_1_append=chk_1.append
  chk_2_append=chk_2.append
  sum_a_l += a[n+i]-x
  sum_a_r += y+a[2*n-1-i]
  chk_1_append(sum_a_l)
  chk_2_append(sum_a_r)

#print(chk_1,chk_2)
for i in range(n):
  ans = max(chk_1.pop()-chk_2.popleft(),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
a_l = a[:n]
a_r = a[2*n:]
a = tuple(a)
import heapq
heapq.heapify(a_l)
a_r = [-1*int(i) for i in a_r]
heapq.heapify(a_r)
chk_1 = [sum(a_l)]
chk_2 = [sum(a_r)]
ans = -10**15
for i in range(n):
  #print(a_l,a_r)
  heapq.heappush(a_l,a[n+i])
  heapq.heappush(a_r,-a[2*n-1-i])
  heapq.heappop(a_l)
  heapq.heappop(a_r)
  chk_1_append=chk_1.append
  chk_2_append=chk_2.append
  chk_1_append(sum(a_l))
  chk_2_append(sum(a_r))

import collections
chk_1 = collections.deque(chk_1)
chk_2 = collections.deque(chk_2)
#print(chk_1,chk_2)
for i in range(n):
  ans = max(chk_1.pop()+chk_2.popleft(),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a_l = a[:n]
a_r = a[2*n:]
a = tuple(a)
import heapq
heapq.heapify(a_l)
a_r = [-1*int(i) for i in a_r]
heapq.heapify(a_r)
chk_1 = [sum(a_l)]
chk_2 = [sum(a_r)]
ans = -10**15
for i in range(n):
  #print(a_l,a_r)
  heapq.heappush(a_l,a[n+i])
  heapq.heappush(a_r,-a[2*n-1-i])
  heapq.heappop(a_l)
  heapq.heappop(a_r)
  chk_1_append=chk_1.append
  chk_2_append=chk_2.append
  chk_1_append(sum(a_l))
  chk_2_append(sum(a_r))

chk_1 = tuple(chk_1)
chk_2 = tuple(chk_2)
#print(chk_1,chk_2)
for i in range(n):
  ans = max(chk_1[i]+chk_2[n-i],ans)
print(ans)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def main():
    n=II()
    aa=LI()

    l=[0]*3*n
    s=sum(aa[:n])
    hp=aa[:n]
    heapify(hp)
    for i,a in enumerate(aa[n:2*n+1],n):
        l[i]=s
        s+=a
        a=heappushpop(hp,a)
        s-=a

    r=[0]*3*n
    s=0
    hp=[]
    for a in aa[2*n:]:
        s+=a
        heappush(hp,-a)
    for i in range(2*n-1,n-2,-1):
        a=aa[i]
        r[i+1]=s
        s+=a
        a=-heappushpop(hp,-a)
        s-=a
    ans=max(l[i]-r[i] for i in range(n,2*n))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
a_l = a[:n]
a_r = a[2*n:]
a = tuple(a)
import heapq
heapq.heapify(a_l)
a_r = [-1*int(i) for i in a_r]
heapq.heapify(a_r)
chk_1 = [sum(a_l)]
chk_2 = [sum(a_r)]
ans = -float('inf')
for i in range(n):
  heapq.heappush(a_l,a[n+i])
  heapq.heappush(a_r,-a[2*n-1-i])
  heapq.heappop(a_l)
  heapq.heappop(a_r)
  chk_1_append=chk_1.append
  chk_2_append=chk_2.append
  chk_1_append(sum(a_l))
  chk_2_append(sum(a_r))
  #print(a_l,a_r)
chk_2 = chk_2[::-1]
chk_1 = tuple(chk_1)
chk_2 = tuple(chk_2)
#print(chk_1,chk_2)
for i in range(n):
  ans = max(chk_1[i]+chk_2[i],ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, _heapify_max, heappushpop, _heappushpop_max

N = int(input())

numbers = [int(x) for x in input().split()]

left = numbers[:N]
heapify(left)

right = numbers[2 * N:]
_heapify_max(right)

for x in numbers[N:2 * N]:
  if left[0] < x < right[0]:
    if abs(left[0] - x) > abs(left[0] - x):
      heappushpop(left, x)
    else:
      _heappushpop_max(right, x)
  elif x > left[0]:
    heappushpop(left, x)
  elif x < right[0]:
    _heappushpop_max(right, x)
    
print(sum(left) - sum(right))

Submission status: Wrong Answer

Solution code:
from heapq import heapify, _heapify_max, heappushpop, _heappushpop_max

N = int(input())

numbers = [int(x) for x in input().split()]

left = numbers[:N]
heapify(left)

right = numbers[2 * N:]
_heapify_max(right)

for x in numbers[N:2 * N]:
  if left[0] < x < right[0]:
    if abs(left[0] - x) > abs(left[0] - x):
      heappushpop(left, x)
    else:
      _heappushpop_max(right, x)
  elif x > left[0]:
    heappushpop(left, x)
  elif -x > right[0]:
    heappushpop(right, -x)
    
print(sum(left) - sum(right))

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappushpop

N = int(input())

numbers = [int(x) for x in input().split()]

left = numbers[:N]
heapify(left)

right = [-x for x in numbers[2 * N:]]
heapify(right)

for x in numbers[N:2 * N]:
  if x > left[0]:
    heappushpop(left, x)
  elif -x > right[0]:
    heappushpop(right, -x)
    
print(sum(left) + sum(right))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappushpop

INF = sys.maxsize

N = int(input())

numbers = [int(x) for x in input().split()]

left = numbers[:N]
heapify(left)

right = [-x for x in numbers[2 * N:]]
heapify(right)

max_score = -INF

for x in numbers[N:2 * N]:
  if x > left[0]:
    heappushpop(left, x)
  elif -x > right[0]:
    heappushpop(right, -x)
    
  max_score = max(max_score, sum(left) + sum(right))
  
print(max_score)

Submission status: Wrong Answer

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

from heapq import heappush, heappop,heappushpop,heapify
hq1 = a[:n]
now=sum(hq1)
heapify(hq1)
lis1=[now]
for k in range(n,2*n):
    now+=a[k]
    p=heappushpop(hq1,a[k])
    now-=p
    lis1.append(now)

a.reverse()
hq2=[]
for i in range(n):
    hq2.append(-a[i])
now=sum(hq2)
heapify(hq2)
lis2=[now]
for k in range(n,2*n):
    now-=a[k]
    p=heappushpop(hq2,-a[k])
    now-=p
    lis2.append(now)
lis2.reverse()

ans=-float("inf")
if n==1:
    n=2
for i in range(n):
    num = lis1[i]+lis2[i]
    ans=max(ans,num)
print(ans)

Submission status: Wrong Answer

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

from heapq import heappush, heappop,heappushpop,heapify
hq1 = a[:n]
now=sum(hq1)
heapify(hq1)
lis1=[now]
for k in range(n,2*n):
    now+=a[k]
    p=heappushpop(hq1,a[k])
    now-=p
    lis1.append(now)

a.reverse()
hq2=[]
for i in range(n):
    hq2.append(-a[i])
now=sum(hq2)
heapify(hq2)
lis2=[now]
for k in range(n,2*n):
    now-=a[k]
    p=heappushpop(hq2,-a[k])
    now-=p
    lis2.append(now)
lis2.reverse()

ans=-float("inf")
for i in range(n):
    num = lis1[i]+lis2[i]
    ans=max(ans,num)
print(ans)

Submission status: Wrong Answer

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

from heapq import heappush, heappop,heappushpop,heapify
hq1 = a[:n]
now=sum(hq1)
heapify(hq1)
lis1=[now]
for k in range(n,2*n):
    now+=a[k]
    p=heappushpop(hq1,a[k])
    now-=p
    lis1.append(now)

a.reverse()
hq2=[]
for i in range(n):
    hq2.append(-a[i])
now=sum(hq2)
heapify(hq2)
lis2=[now]
for k in range(n,2*n):
    now-=a[k]
    p=heappushpop(hq2,a[k])
    now-=p
    lis2.append(now)
lis2.reverse()

ans=-float("inf")
for i in range(n):
    num = lis1[i]+lis2[i]
    ans=max(ans,num)
print(ans)

Submission status: Wrong Answer

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


class PriorityQueue:
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

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


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

    first_half = PriorityQueue(a[:N])
    second_half = PriorityQueue(list(map(lambda x: -x, a[2 * N:])))
    f_max, s_min = [0] * (N + 1), [0] * (N + 1)
    f_max[0], s_min[-1] = sum(a[:N]), sum(a[2 * N:])

    for k in range(N):
        first_half.push(a[k + N])
        f_max[k + 1] = f_max[k] + a[k + N] - first_half.pop()
        second_half.push(-a[-N - 1 - k])
        s_min[N - 1 - k] = s_min[N - k] + a[-N - 1 - k] + second_half.pop()

    ans = -float('inf')
    for k in range(N):
        if ans < f_max[k] - s_min[k]:
            ans = f_max[k] - s_min[k]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappushpop

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

ans = -1000000000
for k in range(N, 2*N+1):
    b = a[:k]
    c = a[k:]
    b_max = sorted(b)[-N:]
    c_min = sorted(c)[:N]
    ans = max(sum(b_max)-sum(c_min), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappushpop

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

ans = -100
for k in range(N, 2*N+1):
    b = a[:k]
    c = a[k:]
    b_max = sorted(b)[-N:]
    c_min = sorted(c)[:N]
    ans = max(sum(b_max)-sum(c_min), ans)
print(ans)

Submission status: Wrong Answer

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


class PriorityQueue:
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

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


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

    first, second = sum(a[:N]), sum(a[2 * N:])
    first_half = PriorityQueue(a[:N])
    second_half = PriorityQueue(list(map(lambda x: -x, a[2 * N:])))
    f_max, s_min = [0] * (N + 1), [0] * (N + 1)
    f_max[0], s_min[-1] = first, second

    for k in range(N):
        first_half.push(a[k + N])
        first = first + a[k + N] - first_half.pop()
        second_half.push(-a[-N - 1 - k])
        second = second + a[-N - 1 - k] + second_half.pop()
        f_max[k + 1] = first
        s_min[N - 1 - k] = second

    ans = -float('inf')
    for k in range(N):
        if ans < f_max[k] - s_min[k]:
            ans = f_max[k] - s_min[k]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop
from copy import deepcopy
import sys
input = sys.stdin.readline

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

heapify(B)
C = []
for a in A:
    heappush(C, -a)

Min_lst = []
Max_lst = []
Min_lst_append = Min_lst.append
Max_lst_append = Max_lst.append
for i in range(n):
    if i%2:
        Max_lst_append(-heappop(C))
    else:
        Min_lst_append(heappop(B))

A_remove = A.remove
for i in Min_lst:
    A_remove(i)
for i in Max_lst:
    A_remove(i)
fst = sum(A[:n])
scd = sum(A[n:])
print(fst-scd)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
a = LIST()
ans = -inf
for i in range(n, 2 * n):
    b = deepcopy(a[:i + 1])
    c = deepcopy(a[i + 1:])
    b.sort(reverse=True)
    c.sort()
    ans = max(ans, sum(b[:n]) - sum(c[:n]))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque
import sys
def main():
    N = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    ans = 0
    f_end = N-1
    b_start = N
    front = A[:f_end+1]
    back = A[b_start:]
    tmp = deque(list(back))
    heapq.heapify(front)
    heapq.heapify(back)
    ans = sum(front)
    ans -= sum(back[:N])
    for _ in range(N+10):
        b_start += 1
        if 3*N-b_start < N:break
        a = tmp.popleft()
        back = list(tmp)
        heapq.heapify(back)
        heapq.heappush(front,a)
        heapq.heappop(front)
        s1 = sum(front)
        s2 = sum(back[:N])
        ans = max(ans,s1-s2)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def main():
    N = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    ans = 0
    f_end = N-1
    b_start = N
    front = A[:f_end+1]
    back = A[b_start:]
    heapq.heapify(front)
    heapq.heapify(back)
    ans = sum(front)
    ans -= sum(back[:N])
    for _ in range(N):
        b_start += 1
        back = A[b_start:]
        heapq.heapify(back)
        a = A[b_start-1]
        heapq.heappush(front,a)
        heapq.heappop(front)
        s1 = sum(front)
        s2 = sum(back[:N])
        ans = max(ans,s1-s2)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def main():
    N = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    front = []
    back = []
    heapq.heapify(front)
    heapq.heapify(back)
    ans = 0
    L = 3*N
    f_end = 0
    b_start = L-1
    for i in range(L):
        a = A[i]
        b = A[3*N-1-i]
        if i == 3*N-1-i:
            s1 = a-front[0]
            s2 = -b-back[0]
            if f_end > b_start:break
            if s1 >= s2 >= 0:
                heapq.heappop(front)
                heapq.heappush(front,a)
                break
            elif 0 <= s1 < s2:
                heapq.heappop(back)
                heapq.heappush(back,-b)
                break
        if len(front) == N:
            if front[0] < a:
                if i < b_start:
                    heapq.heappop(front)
                    heapq.heappush(front,a)
                    f_end = i
        else:
            heapq.heappush(front,a)
            f_end = i
        if len(back) == N:
            if back[0] < -b:
                if f_end < 3*N-1-i:
                    heapq.heappop(back)
                    heapq.heappush(back,-b)
                    b_start = 3*N-1-i
        else:
            heapq.heappush(back,-b)
            b_start = 3*N-1-i
    ans = sum(front)+sum(back)
    print(ans)
    #print(front)
    #print(back)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def main():
    N = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    front = []
    back = []
    heapq.heapify(front)
    heapq.heapify(back)
    ans = 0
    L = 3*N
    f_end = 0
    b_start = L-1
    for i in range(L):
        a = A[i]
        b = A[3*N-1-i]
        if i == 3*N-1-i:
            s1 = a-front[0]
            s2 = -b-back[0]
            if f_end > b_start:break
            if s1 >= s2 >= 0:
                heapq.heappop(front)
                heapq.heappush(front,a)
                break
            elif 0 <= s1 < s2:
                heapq.heappop(back)
                heapq.heappush(back,-b)
                break
        if len(front) == N:
            if front[0] < a:
                if i < b_start:
                    heapq.heappop(front)
                    heapq.heappush(front,a)
                    f_end = i
        else:
            heapq.heappush(front,a)
            f_end = i
        if len(back) == N:
            if back[0] < -b:
                if f_end < 3*N-1-i:
                    heapq.heappop(back)
                    heapq.heappush(back,-b)
                    b_start = 3*N-1-i
        else:
            heapq.heappush(back,-b)
            b_start = 3*N-1-i
    ans = sum(front)+sum(back)
    print(ans)
    print(front)
    print(back)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def main():
    N = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    front = []
    back = []
    heapq.heapify(front)
    heapq.heapify(back)
    ans = 0
    L = (3*N)//2
    if 3*N%2 == 1:
        L += 1
    for i in range(L):
        a = A[i]
        b = A[3*N-1-i]
        if i == 3*N-1-i:
            s1 = a-front[0]
            s2 = -b-back[0]
            if s1 >= s2 >= 0:
                heapq.heappop(front)
                heapq.heappush(front,a)
                break
            elif 0 <= s1 < s2:
                heapq.heappop(back)
                heapq.heappush(back,-b)
                break
        if len(front) == N:
            if front[0] < a:
                heapq.heappop(front)
                heapq.heappush(front,a)
        else:
            heapq.heappush(front,a)
        if len(back) == N:
            if back[0] < -b:
                heapq.heappop(back)
                heapq.heappush(back,-b)
        else:
            heapq.heappush(back,-b)
    ans = sum(front)+sum(back)
    print(ans)
    #print(front)
    #print(back)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys
import heapq

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())
A = lmi()

lq = []  # normal
hq = []  # * -1
for a in A[:N]:
    heapq.heappush(lq, a)
for a in A[2 * N:]:
    heapq.heappush(hq, - a)

dpl = [0 for _ in range(N + 1)]  # middle をNまで消費したときの (a′の前半N要素の総和)
dph = [0 for _ in range(N + 1)]  # middle をNまで消費したときの (a′の後半N要素の総和)

middle = A[N:2 * N]
dpl[0] = sum(A[:N])
last_val = dpl[0]
for count in range(1, N + 1):
    heapq.heappush(lq, middle[count - 1])
    v = heapq.heappop(lq)
    dpl[count] = dpl[count - 1] - v + middle[count - 1]

dph[N] = sum(A[2 * N:])
for count in reversed(range(N)):
    heapq.heappush(hq, -middle[count])
    v = -  heapq.heappop(hq)  # bigger value
    dph[count] = dph[count + 1] - v + middle[count]


print(max(dpl[i] - dph[i] for i in range(N)))

Submission status: Wrong Answer

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

import heapq
que1 = []
heapq.heapify(que1)
S = [0] * (2*N + 1)
for i in range(N):
    S[i + 1] = S[i] + a[i]
    #que1.append(a[i])
    heapq.heappush(que1, a[i])
que2 = []
heapq.heapify(que2)
T = [0] * (2*N + 1)
for i in range(N):
    T[i + 1] = T[i] + a[3*N - i - 1]
    #que2.append(-a[3*N - i - 1])
    heapq.heappush(que2, -a[3*N - i - 1])

for i in range(N, 2*N):
    mi = heapq.heappop(que1)
    #print(mi)
    if a[i] > mi:
        S[i + 1] = S[i] - mi + a[i]
        #heapq.heappop(que1)
        heapq.heappush(que1, a[i])
    else:
        S[i + 1] = S[i]
        heapq.heappush(que1, mi)
for i in range(N, 2*N):
    ma = heapq.heappop(que2) * -1
    #print(ma)
    if a[3*N - i - 1] < ma:
        T[i + 1] = T[i] - ma + a[3*N - i - 1]
        #heapq.heappop(que2)
        #que2.append(-a[3*N - i - 1])
        heapq.heappush(que2, -a[3*N - i - 1])
    else:
        T[i + 1] = T[i]
        heapq.heappush(que2, -ma)

res = -float('Inf')
for i in range(N, 2*N):
    res = max(res, S[i] - T[3*N - i])
print(res)

Submission status: Wrong Answer

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

import heapq
que1 = []
heapq.heapify(que1)
S = [0] * (2*N + 1)
for i in range(N):
    S[i + 1] = S[i] + a[i]
    #que1.append(a[i])
    heapq.heappush(que1, a[i])
que2 = []
heapq.heapify(que2)
T = [0] * (2*N + 1)
for i in range(N):
    T[i + 1] = T[i] + a[3*N - i - 1]
    #que2.append(-a[3*N - i - 1])
    heapq.heappush(que2, -a[3*N - i - 1])

for i in range(N, 2*N):
    mi = heapq.heappop(que1)
    print(mi)
    if a[i] > mi:
        S[i + 1] = S[i] - mi + a[i]
        #heapq.heappop(que1)
        heapq.heappush(que1, a[i])
    else:
        S[i + 1] = S[i]
        heapq.heappush(que1, mi)
for i in range(N, 2*N):
    ma = heapq.heappop(que2) * -1
    print(ma)
    if a[3*N - i - 1] < ma:
        T[i + 1] = T[i] - ma + a[3*N - i - 1]
        #heapq.heappop(que2)
        #que2.append(-a[3*N - i - 1])
        heapq.heappush(que2, -a[3*N - i - 1])
    else:
        T[i + 1] = T[i]
        heapq.heappush(que2, -ma)

res = -float('Inf')
for i in range(N, 2*N + 1):
    res = max(res, S[i] - T[3*N - i])
print(res)

Submission status: Wrong Answer

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

import heapq
que1 = []
heapq.heapify(que1)
S = [0] * (2*N + 1)
for i in range(N):
    S[i + 1] = S[i] + a[i]
    #que1.append(a[i])
    heapq.heappush(que1, a[i])
que2 = []
heapq.heapify(que2)
T = [0] * (2*N + 1)
for i in range(N):
    T[i + 1] = T[i] + a[3*N - i - 1]
    #que2.append(-a[3*N - i - 1])
    heapq.heappush(que2, -a[3*N - i - 1])

for i in range(N, 2*N):
    mi = heapq.heappop(que1)
    print(mi)
    if a[i] > mi:
        S[i + 1] = S[i] - mi + a[i]
        #heapq.heappop(que1)
        heapq.heappush(que1, a[i])
    else:
        S[i + 1] = S[i]
        heapq.heappush(que1, mi)
for i in range(N, 2*N):
    ma = heapq.heappop(que2) * -1
    print(ma)
    if a[3*N - i - 1] < ma:
        T[i + 1] = T[i] - ma + a[3*N - i - 1]
        #heapq.heappop(que2)
        #que2.append(-a[3*N - i - 1])
        heapq.heappush(que2, -a[3*N - i - 1])
    else:
        T[i + 1] = T[i]
        heapq.heappush(que2, -ma)

res = -float('Inf')
for i in range(N, 2*N):
    res = max(res, S[i] - T[3*N - i])
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappop, heappush
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 1/3ごとに分けてヒープ構造を使う
N = ir()
A = lr()
left = A[:N]
right = A[-N:]
heapify(left)
right = [-x for x in right]
heapify(right)
center = deque(A[N:-N])
remove = 0
l = heappop(left)
r = heappop(right)
while remove < N:
    x = center[0] - l
    y = -r - center[-1]
    if x < 0 and y < 0:
        #centerから数字を取り除く
        if abs(x) >= abs(y):
            center.popleft()
        else:
            center.pop()
    else:
        # 差が大きい方から取り除く
        if x >= y:
            heappush(left, center.popleft())
            l = heappop(left)
        else:
            heappush(right, -center.pop())
            r = heappop(right)
    remove += 1

heappush(left, l); heappush(right, r)
answer = sum(left) + sum(right)
print(answer)
# 05

Submission status: Wrong Answer

Solution code:
import heapq

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

bound = N # 前後の境
h_pre = []
h_post = []
for i in range(N):
    heapq.heappush(h_pre,a_list[i])
    heapq.heappush(h_post,-1*a_list[-(i+1)])
pre_sum = [sum(h_pre)]
post_sum = [sum(h_post)]

for i in range(N):
    a = a_list[N+i]
    heapq.heappushpop(h_pre,a)
    pre_sum.append(sum(h_pre))
    
    b = -1 * a_list[-(i+N+1)]
    heapq.heappushpop(h_post,b)
    post_sum.append(sum(h_post))

ans = -1000000000000000000
for i in range(N):
    s = pre_sum[i] + post_sum[-(i+1)]
    if s > ans:
        ans = s

print(ans)

Submission status: Wrong Answer

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

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

    l = a[:N]
    heapq.heapify(l)
    ls = sum(l)
    use = [ls]
    for i in range(N):
        num = a[N+i]
        ln = heapq.heappop(l)
        if ln > num:
            heapq.heappush(l,ln)
            use.append(ls)
        else:
            heapq.heappush(l,num)
            ls += num-ln
            use.append(ls)
            
    b = []
    for num in a[::-1]:
        b.append(-1*num)
        
    r = b[:N]
    heapq.heapify(r)
    rs = sum(r)
    use[-1] += rs
    for i in range(N):
        num = b[N+i]
        rn = heapq.heappop(r)
        if rn < num:
            heapq.heappush(l,rn)
            rs += (num-rn)
        else:
            heapq.heappush(l,rn)
        use[-i-2] += rs
    
    print(max(use))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A1=A[:N]
A2=A[N:2*N]
A3=A[2*N:3*N]

heapq.heapify(A1)
A1_sum=sum(A1)
A1_li=[A1_sum]
for a in A2:
  p=heapq.heappushpop(A1,a)
  A1_sum+=a-p
  A1_li.append(A1_sum)
  
heapq.heapify(A3)
A3_sum=sum(A3)
A3_li=[A3_sum]
for a in A3[::-1]:
  p=heapq.heappushpop(A3,a)
  A3_sum+=a-p
  A3_li.append(A3_sum)
  
A3_li=A3_li[::-1]  
ans=False
for a1, a3 in zip(A1_li, A3_li):
  if not ans:
    ans=a1-a3
  else:
    ans=max(ans, a1-a3)
print(ans)

Submission status: Wrong Answer

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

A1=A[:N]
A2=A[N:2*N]
A3=A[2*N:3*N]

heapq.heapify(A1)
A1_sum=sum(A1)
A1_li=[A1_sum]
for a in A2:
  p=heapq.heappushpop(A1,a)
  A1_sum+=a-p
  A1_li.append(A1_sum)
  
heapq.heapify(A3)
A3_sum=sum(A3)
A3_li=[A3_sum]
for a in A3[::-1]:
  p=heapq.heappushpop(A3,a)
  A3_sum+=a-p
  A3_li.append(A3_sum)
  
ans=False
for a1, a3 in zip(A1_li, A3_li):
  if not ans:
    ans=a1-a3
  else:
    ans=max(ans, a1-a3)
print(ans)

Submission status: Wrong Answer

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

left = A[:N]
right = [-a for a in A[-N:]]
rest = A[N:-N]

heapq.heapify(left)
heapq.heapify(right)

isRight = True
while rest:
    v = rest.pop()
    if isRight:
        if v <= left[0] and -v <= right[0]:
            continue
        dif_left = abs(left[0] - v)
        dif_right = abs(right[0] + v)
        if dif_right >= dif_left:
            heapq.heappushpop(right, -v)
        else:
            heapq.heappushpop(left, v)
            isRight = False
    else:
        if v > left[0]:
            heapq.heappushpop(left, v)

ans = sum(left) + sum(right)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import accumulate
    N = int(input())
    A = [int(i) for i in input().split()]
    h1 = A[:N]
    h2 = A[N:2*N]
    h3 = A[2*N:]
    h1.sort()
    h3.sort()
    S1 = list(accumulate([0] + h1))
    S2 = list(accumulate([0] + h2))
    S3 = list(accumulate([0] + h3))
    ans = (S1[N] - S1[0]) - (S3[N] - S3[0])
    for i in range(N):
        cur = (S1[N] - S1[i]) - (S3[i] - S3[0])
        cur += (S2[i] - S2[0])
        cur -= (S2[N] - S2[i])
        ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
import heapq
B=sorted(A[:N])
C=A[2*N:]
C=sorted(list(map(lambda x: x*(-1),C)))
b=sum(A[:N])
c=(-1)*sum(A[2*N:])
ans=b+c
for j in range(N):
  b=sum(A[:N])
  x=b
  c=(-1)*sum(A[2*N:])
  y=c
  B=sorted(A[:N])
  C=A[2*N:]
  C=sorted(list(map(lambda x: x*(-1),C)))
  for i in range(j):
    heapq.heappush(B,A[i+N])
    b+=A[i+N]
    a=heapq.heappop(B)
    b-=a
    x=max(b,x)
        
  for i in range(N-j):
    heapq.heappush(C,(-1)*A[2*N-i-1])
    c-=A[2*N-i-1]
    d=heapq.heappop(C)
    c-=d
    y=max(c,y)
  ans=max(ans,x+y)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_minus = list(map(lambda x: -x, a))
    a_bef, a_aft = a[:n], a_minus[-n:]
    a_bef_sum, a_aft_sum = {n: sum(a_bef)}, {2 * n: -sum(a_aft)}

    heapq.heapify(a_bef)
    heapq.heapify(a_aft)
    for i in range(n):
        bef_key = n + i
        heapq.heappush(a_bef, a[bef_key])
        a_bef_sum[bef_key+1] = a_bef_sum[bef_key] - heapq.heappop(a_bef) + a[bef_key]

        aft_key = n * 2 - i - 1
        heapq.heappush(a_aft, a_minus[aft_key])
        a_aft_sum[aft_key] = a_aft_sum[aft_key+1] + heapq.heappop(a_aft) + a[aft_key]

    ans = - pow(10, 15)
    for i in range(n):
        diff = a_bef_sum[n+i] - a_aft_sum[n+i]
        if diff > ans:
            ans = diff
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_bef, a_aft = a[:n], list(map(lambda x: -x, a))[-n:]
    a_bef_sum, a_aft_sum = {n: sum(a_bef)}, {2 * n: -sum(a_aft)}

    heapq.heapify(a_bef)
    heapq.heapify(a_aft)
    for i in range(n):
        bef_key = n + i
        heapq.heappush(a_bef, a[bef_key])
        a_bef_sum[bef_key+1] = a_bef_sum[bef_key] - heapq.heappop(a_bef) + a[bef_key]

        aft_key = n * 2 - i - 1
        heapq.heappush(a_aft, a[aft_key])
        a_aft_sum[aft_key] = a_aft_sum[aft_key+1] + heapq.heappop(a_aft) + a[aft_key]

    ans = - pow(10, 15)
    for i in range(n):
        diff = a_bef_sum[n+i] - a_aft_sum[n+i]
        if diff > ans:
            ans = diff
    print(ans)

if __name__ == '__main__':
    main()