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 heapify, heappop, heappush

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

s = [0] * (2*N+1)
q1 = []
q2 = []
heapify(q1)
heapify(q2)

for i in range(N):
    s[i+1] = s[i] + a[i]
    heappush(q1, a[i])

for i in range(N, 2*N):
    mi = q1[0]
    if a[i] > mi:
        s[i+1] = s[i] - mi + a[i]
        heappop(q1)
        heappush(q1, a[i])
    else:
        s[i+1] = s[i]

t = [0] * (2*N+1)

for i in range(N):
    t[i+1] = t[i] + a[3*N-1-i]
    heappush(q2, -a[3*N-1-i])

for i in range(N, 2*N):
    ma = -q2[0]
    if a[3*N-1-i] < ma:
        t[i+1] = t[i] - ma + a[3*N-1-i]
        heappop(q2)
        heappush(q2, -a[3*N-1-i])
    else:
        t[i+1] = t[i]

res = -10 ** 10
for i in range(N, N*2+1):
    res = max(res, s[i] - t[N*3-i])

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
ans = -10**10
for k in range(0, N + 1):
    l1 = sorted(a[:N + k])[k:]
    l2 = sorted(a[N + k:], reverse=True)[N - k:]
    ans = max(ans, sum(l1) - sum(l2))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

if N % 2 == 0:
    l1 = sorted(a[:3 * N // 2])[N//2:]
    l2 = sorted(a[3 * N // 2:], reverse=True)[N // 2:]
    print(sum(l1) - sum(l2))
else:
    l1 = sorted(a[:3 * N // 2 + 1])[N // 2 + 1:]
    l2 = sorted(a[3 * N // 2 + 1:], reverse=True)[N // 2:]
    ans1 = sum(l1) - sum(l2)

    l3 = sorted(a[:3 * N // 2])[N // 2:]
    l4 = sorted(a[3 * N // 2:], reverse=True)[N // 2 + 1:]
    ans2 = sum(l3) - sum(l4)
    print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n = int(input())
a = [int(i) for i in input().split()]

from heapq import *

pq1 = a[:n]
heapify(pq1)
s = sum(pq1)
score1 = [s]
for i in range(n):
    c=heappushpop(pq1, a[n+i])
    s += a[n+i] - c
    score1.append(s)

pq2 = [-i for i in a[2*n:]]
heapify(pq2)
s = sum(pq2)
score2 = [s]
for i in range(1,n+1):
    c=heappushpop(pq2, -a[2*n-i])
    s += -a[2*n-i] - c
    score2.append(s)

print(score1)
print(score2)
ans = -10**17
for i,j in zip(score1,reversed(score2)):
    ans = max(ans, i+j)

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!


n = int(input())
a = [int(i) for i in input().split()]

from heapq import *


pq1 = a[:n]
heapify(pq1)
s = sum(pq1)
score1 = [s]
for i in range(n):
    c=heappushpop(pq1, a[n+i])
    s += a[n+i] - c
    score1.append(s)

pq2 = [-i for i in a[2*n:]]
heapify(pq2)
s = sum(pq2)
score2 = [s]
for i in range(1,n+1):
    c=heappushpop(pq2, -a[2*n-i])
    s += -a[2*n-i] - c
    score2.append(s)

#print(score1)
#print(score2)
ans = -(1<<17)
for i,j in zip(score1,reversed(score2)):
    ans = max(ans, i+j)

print(ans)

Submission status: Wrong Answer

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

pq1 = a[:N]
pq2 = [-x for x in a[2 * N:]]

heapify(pq1)
heapify(pq2)

s1 = sum(pq1)
s2 = sum(pq2)

ans1 = [s1]
ans2 = [s2]

for k in range(N, 2 * N):
    heappush(pq1, a[k])
    x = heappop(pq1)
    s1 += a[k] - x
    ans1.append(s1)
    
    heappush(pq2, -a[3 * N - k - 1])
    x = heappop(pq2)
    s2 += -a[3 * N - k - 1] - x
    ans2.append(s2)
    
print(max(ans1[i] + ans2[-i - 1] for i in range(N)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import deque


def solve(N: int, a: "List[int]"):
    L = a[:N]
    R = [-x for x in a[2*N:]]
    heapq.heapify(L)
    heapq.heapify(R)
    M = deque(a[N:2*N], maxlen=N)
    while len(M) > 0:
        if len(M) == 1:
            ml = M.popleft()
            mr = -ml
            l = heapq.heappop(L)
            r = heapq.heappop(R)
            if ml - l > 0 and ml - l >= mr - r:
                heapq.heappush(L, ml)
                heapq.heappush(R, r)
            elif mr - r > 0 and mr - r >= ml - l:
                heapq.heappush(L, l)
                heapq.heappush(R, mr)
            else:
                heapq.heappush(L, l)
                heapq.heappush(R, r)
        else:
            mr = -M.pop()
            ml = M.popleft()
            l = heapq.heappop(L)
            r = heapq.heappop(R)            
            if ml - l > 0 and ml - l >= mr - r:
                heapq.heappush(L, ml)
                heapq.heappush(R, r)
                M.append(-mr)
            elif mr - r > 0 and mr - r >= ml - l:
                heapq.heappush(L, l)
                heapq.heappush(R, mr)
                M.appendleft(ml)
            else:
                heapq.heappush(L, l)
                heapq.heappush(R, r)
    print(sum(L) + sum(R))                
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(3*N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
a = [int(i) for i in input().split()]
k = 0
a_front = []
a_center = []
a_back = []
front_sum = 0
back_sum = 0

for i in a:
    k += 1
    if k <= n:
        a_front += [i]
        front_sum += i
    elif k <= 2 * n:
        a_center += [i]
    else:
        a_back += [-i]
        back_sum += i

heapq.heapify(a_front)
heapq.heapify(a_back)

front_sums = [front_sum]
back_sums = [back_sum]

for i in range(n):
        front_sum += a_center[i] - heapq.heappushpop(a_front, a_center[i])
        front_sums += [front_sum]
        back_sum += a_center[-i-1] + heapq.heappushpop(a_back, a_center[-i-1])
        back_sums += [back_sum]

print(max([front_sums[i] - back_sums[-i-1] for i in range(n+1)]))
#print(front_sums, back_sums)

Submission status: Wrong Answer

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

N = int(input())
*A, = map(int, input().split())
INF = 10**12
first = A[:N]
heapify(first)
second = [-a for a in A[2*N:]]
heapify(second)
f = [0]*(N+1)
s = [INF]*(N+1)
f[0] = sum(first)
s[N] = - sum(second)
for k in range(1, N+1):
    heappushpop(first, A[N-1+k])
    f[k] = sum(first)
for k in range(N-1, -1, -1):
    heappushpop(second, -A[N+k])
    s[k] = - sum(second)
ans = 0
for k in range(N+1):
    ans = max(ans, f[k] - s[k])
print(ans)

Submission status: Wrong Answer

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

n=int(input())
s=list(map(int,input().split()))
l=(s[:n])
heapify(l)
r=[-i for i in s[2*n:]]
heapify(r)
c=deque(s[n:2*n])
x=l[0]
y=r[0]
while len(c)>0:
    a,b=c[0],-c[-1]
    if a-x==b-y and len(c)>1:
        heappop(l)
        heappush(l,c.popleft())
        x=l[0]
        heappop(r)
        heappush(r,-c.pop())
        y=r[0]
    elif a-x>b-y:
        heappop(l)
        heappush(l,c.popleft())
        x=l[0]
    else:
        heappop(r)
        heappush(r,-c.pop())
        y=r[0]
print(sum(l)+sum(r))

Submission status: Wrong Answer

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

n=int(input())
s=list(map(int,input().split()))
l=(s[:n])
heapify(l)
r=[-i for i in s[2*n:]]
heapify(r)
c=deque(s[n:2*n])
x=l[0]
y=r[0]
while len(c)>0:
    a,b=c[0],-c[-1]
    if a-x>b-y:
        heappop(l)
        heappush(l,c.popleft())
        x=l[0]
    else:
        heappop(r)
        heappush(r,-c.pop())
        y=r[0]
print(sum(l)+sum(r))

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
A = list(map(int, input().split()))
n1 = A[:N]
s1 = [sum(n1)]
heapq.heapify(n1)
for i in range(N):
    heapq.heappush(n1,A[N+i])
    p = heapq.heappop(n1)
    s1.append(s1[-1]-p+A[N+i])

s3 = [-(sum(A[-N:]))]
n3 = [-a for a in A[-N:]]
heapq.heapify(n3)
for i in range(N):
    heapq.heappush(n3,-A[-N-i-1])
    p = heapq.heappop(n3)
    s3.append(s3[-1]-p-A[-N-i-1])
M = -10**10
# print(s3)
for i,j in zip(s1,s3[::-1]):
    # print(i,j)
    M = max(M,i+j)

print(M)

Submission status: Wrong Answer

Solution code:

import heapq

N = int(input())
A = list(map(int, input().split()))
n1 = A[:N]
s1 = [sum(n1)]
heapq.heapify(n1)
for i in range(N):
    heapq.heappush(n1,A[N+i])
    p = heapq.heappop(n1)
    s1.append(s1[-1]-p+A[N+i])

n3 = [-a for a in A[-N:]]
s3 = [(sum(n3))]
heapq.heapify(n3)
for i in range(N):
    heapq.heappush(n3,-A[-N-i-1])
    p = heapq.heappop(n3)
    s3.append(s3[-1]-p-A[-N-i-1])
M = -10**10
# print(s3)
for i,j in zip(s1,s3[::-1]):
    # print(i,j)
    M = max(M,i+j)

print(M)

Submission status: Wrong Answer

Solution code:
#写経and実験
from heapq import heappushpop

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

l_list = sorted(A[:N])
l_sum = [sum(l_list)]
for a in A[N:2 * N]:
    l_sum.append(l_sum[-1] - heappushpop(l_list, a) + a)

r_list = [-x for x in A[-N:]]
r_sum = [sum(r_list)]
for a in reversed(A[N:2 * N]):
    r_sum.append(r_sum[-1] - heappushpop(r_list, -a) - a)

ans = -(10 ** 15)
for l, r in zip(l_sum, r_sum[::-1]):
    ans = max(ans, l + r)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n = int(input())
a = list(map(int,input().split()))
yobi = deque()
left = deque()
right = deque()
l = a[0:2*n]
r = a[2*n:3*n]
l.sort(reverse=True)
r.sort(reverse=True)
for i in range(n):
    yobi.append(l[i+n])
    left.appendleft(l[i])
    right.append(r[i])
sumr,suml = sum(right),sum(left)
ans = suml-sumr
for i in range(2*n-1,n-1,-1):
    left_max = left.popleft()
    right_min = right.popleft()
    if left_max > a[i]:
        left.appendleft(left_max)
    else:
        y = yobi.popleft()
        right.appendleft(y)
        suml = suml - left_max + y
    if right_min < a[i]:
        right.appendleft(right_min)
    else:
        sumr = sumr-right_min+a[i]
    ans = max(ans,suml-sumr)
print(ans)

Submission status: Wrong Answer

Solution code:
def f(a):q=a[:n];heapify(q);return sum(q)+cumsum([e-heappushpop(q,e)for e in a[n:n-~n]])
from heapq import*;from numpy import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),f([-e for e in a[::-1]])[::-1]))))

Submission status: Wrong Answer

Solution code:
def f(a):
	q=a[:n];s=sum(q);heapify(q)
	for e in a[n:2*n]:yield s;s+=e-heappushpop(q,e)
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1]))))

Submission status: Wrong Answer

Solution code:
from heapq import*
n,*a=map(int,open(0).read().split())
b=a[:n]
c=[-i for i in a[n:][::-1]]
d=c[:n]
e=c[n:]
heapify(b)
heapify(d)
s=sum(b)
t=sum(d)
red=[s]
blue=[t]
for i in range(n,n*2):
    s+=a[i]-heappushpop(b,a[i])
    t+=a[i]-heappushpop(d,c[i])
    red+=[s]
    blue+=[t]
print(max(j-i for i,j in zip(red,blue[::-1])))

Submission status: Wrong Answer

Solution code:
from heapq import*
n,*a=map(int,open(0).read().split())
ans=-float("inf")
b=a[:n]
heapify(b)
for i in range(n,n*2):
    heappush(b,a[i])
    c=a[i+1:]
    heapify(c)
    blue=sum(c[:n])
    heappop(b)
    red=sum(b)
    ans=max(ans,red-blue)
#    print(b,c)
#あｈｊｆｋぁｄｓｈｆｌｋじゃｇはｌｋｊｄｊｇｌｋ；あｊｄｇｌｋ；あｄｓｊｇｌ；あｊｓｄｇｌｋ；あｊｓｄｇｌ；かｓ
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
array = [int(i) for i in input().split()]
ans=-1e14
l_array = []
r_array = []
l_sum = [0]*(n+1)
r_sum = [0]*(n+1)

# left-n and right-n numbers
for i in range(n):
    heapq.heappush(l_array, array[i])
    heapq.heappush(r_array, (-array[3*n-1-i], array[3*n-1-i]))

l_sum[0] = sum(l_array)
r_sum[n] = sum([i[1] for i in r_array])

for i in range(n, 2*n):
    heapq.heappush(l_array, array[i])
    heapq.heappush(r_array, (-array[3*n-1-i], array[3*n-1-i]))
    heapq.heappop(l_array)
    heapq.heappop(r_array)

    l_sum[i-n+1] = sum(l_array)
    r_sum[2*n-1-i] = sum([j[1] for j in r_array])

for i in range(n):
    ans = max(ans, l_sum[i]-r_sum[i])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
array = [int(i) for i in input().split()]
ans=-1e8

# 左側にある数はn～2nを動く
for i in range(n, 2*n+1):
    l_array = sorted(array[:i]) #sliceできたっけ
    r_array = sorted(array[i:])
    ans = max(ans, sum(l_array[i-n:])-sum(r_array[:n]))

print(ans)

Submission status: Wrong Answer

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


# L = heapq.heapify(A[:N])
# R = heapq.heapify(A[2*N:]) この記法ないらしい
# BC125C の累積GCDの直後にやっているので、似たやり方で解いてみる
L = A[:N]
R = [-a for a in A[2*N:]]
L_sum, R_sum = sum(L), sum(R)
heapq.heapify(L)
heapq.heapify(R)

L_acc = [L_sum]
R_acc = [R_sum]
for i in range(N, 2*N):
    if L[0] >= A[i]:
        if i > N:
            L_acc.append(L_acc[-1])
        elif i == N:
            pass
    else:
        heapq.heappush(L, A[i])
        out = heapq.heappop(L)
        L_acc.append(L_acc[-1] - out + A[i])

for i in range(2*N-1, N-1, -1):
    if R[0] >= -A[i]:
        if i <= 2*N-1:
            R_acc.append(R_acc[-1])
        elif i == 2*N-1:
            pass
    else:
        heapq.heappush(R, -A[i])
        out = heapq.heappop(R)
        R_acc.append(R_acc[-1] - out - A[i])

ans = -float('inf')
for i in range(N):
     ans = max(ans, L_acc[i]+R_acc[-(i+1)])

print(ans)

Submission status: Wrong Answer

Solution code:
import math


class MyHeap:
    def __init__(self, normal_list, smaller=True):
        self.smaller = smaller
        self.length = 0
        self.list = []
        for item in normal_list:
            self.heap_push(item)

    def heap_pop(self):
        top = self.list[0]
        bottom = self.list.pop()
        if top == bottom:
            return top
        self.length = len(self.list)
        self.list[0] = bottom
        current_index = 0
        while not self.is_bottom(current_index):
            left_child_index = current_index * 2 + 1
            right_child_index = current_index * 2 + 2
            if right_child_index >= self.length:
                prior_child_index = left_child_index
            else:
                prior_child_index = self.get_prior_index(left_child_index, right_child_index)
            if self.is_prior_index(prior_child_index, current_index):
                self.swap(prior_child_index, current_index)
                current_index = prior_child_index
            else:
                break

        return top

    def heap_push(self, item):
        self.list.append(item)
        self.length = len(self.list)
        current_index = self.length - 1
        while current_index != 0:
            parent_index = self.get_parent_index(current_index)
            if self.is_prior_index(current_index, parent_index):
                self.swap(current_index, parent_index)
                current_index = parent_index
            else:
                break

    def is_bottom(self, index):
        return index * 2 + 1 >= self.length

    def is_prior(self, a, b):
        less_than_bool = a <= b
        if self.smaller:
            return less_than_bool
        else:
            return not less_than_bool

    def is_prior_index(self, a_index, b_index):
        return self.is_prior(self.list[a_index], self.list[b_index])

    def get_prior_index(self, a_index, b_index):
        if self.is_prior_index(a_index, b_index):
            return a_index
        else:
            return b_index

    def swap(self, a_index, b_index):
        a_value = self.list[a_index]
        b_value = self.list[b_index]
        self.list[a_index] = b_value
        self.list[b_index] = a_value

    def get_parent_index(self, index):
        if index % 2 == 0:
            return index // 2 - 1
        else:
            return (index - 1) // 2


if __name__ == '__main__':
    n = int(input())
    raw_input = list(map(int, input().split()))
    left_list = raw_input[0:n]
    middle_list = raw_input[n:2 * n]
    right_list = raw_input[2 * n:3 * n]
    left_queue = MyHeap(left_list)
    right_queue = MyHeap(right_list, False)

    ans_left_list = [sum(left_queue.list)]
    ans_right_list = [sum(right_queue.list)]

    for i in range(n):
        left_queue.heap_push(middle_list[i])
        left_queue.heap_pop()
        ans_left_list.append(sum(left_queue.list))

        right_queue.heap_push(middle_list[n - i - 1])
        right_queue.heap_pop()
        ans_right_list.append(sum(right_queue.list))

    ans_right_list = list(reversed(ans_right_list))

    ans = -999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

    for i in range(n):
        diff = ans_left_list[i] - ans_right_list[i]
        if ans < diff:
            ans = diff

    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


class MyHeap:
    def __init__(self, normal_list, smaller=True):
        self.smaller = smaller
        self.length = 0
        self.list = []
        for item in normal_list:
            self.heap_push(item)

    def heap_pop(self):
        top = self.list[0]
        bottom = self.list.pop()
        if top == bottom:
            return top
        self.length = len(self.list)
        self.list[0] = bottom
        current_index = 0
        while not self.is_bottom(current_index):
            left_child_index = current_index * 2 + 1
            right_child_index = current_index * 2 + 2
            if right_child_index >= self.length:
                prior_child_index = left_child_index
            else:
                prior_child_index = self.get_prior_index(left_child_index, right_child_index)
            if self.is_prior_index(prior_child_index, current_index):
                self.swap(prior_child_index, current_index)
                current_index = prior_child_index
            else:
                break

        return top

    def heap_push(self, item):
        self.list.append(item)
        self.length = len(self.list)
        current_index = self.length - 1
        while current_index != 0:
            parent_index = self.get_parent_index(current_index)
            if self.is_prior_index(current_index, parent_index):
                self.swap(current_index, parent_index)
                current_index = parent_index
            else:
                break

    def is_bottom(self, index):
        return index * 2 + 1 >= self.length

    def is_prior(self, a, b):
        less_than_bool = a <= b
        if self.smaller:
            return less_than_bool
        else:
            return not less_than_bool

    def is_prior_index(self, a_index, b_index):
        return self.is_prior(self.list[a_index], self.list[b_index])

    def get_prior_index(self, a_index, b_index):
        if self.is_prior_index(a_index, b_index):
            return a_index
        else:
            return b_index

    def swap(self, a_index, b_index):
        a_value = self.list[a_index]
        b_value = self.list[b_index]
        self.list[a_index] = b_value
        self.list[b_index] = a_value

    def get_parent_index(self, index):
        if index % 2 == 0:
            return index // 2 - 1
        else:
            return (index - 1) // 2


if __name__ == '__main__':
    n = int(input())
    raw_input = list(map(int, input().split()))
    left_list = raw_input[0:n]
    middle_list = raw_input[n:2 * n]
    right_list = raw_input[2 * n:3 * n]
    left_queue = MyHeap(left_list)
    middle_queue = deque(middle_list)
    right_queue = MyHeap(right_list, False)

    left_turn = True

    while not len(middle_queue) == 0:
        if left_turn:
            middle_left = middle_queue.popleft()
            if middle_left > left_queue.list[0]:
                left_queue.heap_pop()
                left_queue.heap_push(middle_left)
                left_turn = False
        else:
            middle_right = middle_queue.pop()
            if middle_right < right_queue.list[0]:
                right_queue.heap_pop()
                right_queue.heap_push(middle_right)
                left_turn = True

    print(sum(left_queue.list) - sum(right_queue.list))

Submission status: Wrong Answer

Solution code:
from heapq import *

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
    heappush(B,A[i])
sumB=[sum(B)]
for i in range(N,2*N):
    heappush(B,A[i])
    poped=heappop(B)
    sumB.append(sumB[-1]-poped+A[i])

A.reverse()
C=[]
for i in range(N):
    heappush(C,A[i]*(-1))
sumC=[(-1)*sum(C)]
for i in range(N,2*N):
    heappush(C,A[i]*(-1))
    poped=heappop(C)*(-1)
    sumC.append(sumC[-1]-poped+A[i])
sumC.reverse()
ans=-10**19
for i,j in zip(sumB,sumC):
    ans=max(ans,i-j)

Submission status: Wrong Answer

Solution code:
from heapq import *

N=int(input())
A=list(map(int,input().split()))
A.reverse()
B=[]
heap=[]
for i in range(N):
    heappush(heap,A[i])
for i in range(N,2*N):
    if heap[0]<A[i]:
        B.append(heappop(heap))
        heappush(heap,A[i])
    else:
        B.append(A[i])
C=[]
for i in range(2*N,3*N):
    if 2*B[-1]-A[i]-heap[0]>0:
        C.append(B.pop(-1))
        B.append(heappop(heap))
    else:
        C.append(A[i])
print(sum(C)-sum(B))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
n=int(input())
a=list(map(int, input().split()))
q1=[]
q2=[]
s1=[]
s2=[]
for i in range(n):
    heappush(q1, a[i])
s1.append(sum(a[0:n]))
for ai in a[n:2*n]:
    heappush(q1, ai)
    m=heappop(q1)
    s1.append(s1[-1]+ai-m)
a=a[::-1]
for i in range(n):
    heappush(q2, -a[i])
s2.append(-sum(a[0:n]))
for ai in [-i for i in a[n:2*n]]:
    heappush(q2, ai)
    m=heappop(q2)
    s2.append(s2[-1]+ai-m)
ans=-1
for i in range(n+1):
    ans=max(s1[i]+s2[-i-1], ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
n=int(input())
a=list(map(int, input().split()))
q1=[]
q2=[]
s1=[]
s2=[]
for i in range(n):
    heappush(q1, a[i])
s1.append(sum(a[0:n]))
for ai in a[n:2*n]:
    heappush(q1, ai)
    m=heappop(q1)
    s1.append(s1[-1]+ai-m)
a=a[::-1]
for i in range(n):
    heappush(q2, -a[i])
s2.append(-sum(a[0:n]))
for ai in [-i for i in a[n:2*n]]:
    heappush(q2, ai)
    m=heappop(q2)
    s2.append(s2[-1]+ai-m)
ans=-1
print(s1, s2)
for i in range(n+1):
    ans=max(s1[i]+s2[-i-1], ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
L1 = A[:N]
L2 = A[N:2*N]
L3 = A[2*N:]

L1 = sorted(L1)
L3 = sorted(L3, reverse=True)

L1 = [0]+list(accumulate(L1))
L2 = [0]+list(accumulate(L2))
L3 = [0]+list(accumulate(L3))
# print(L1)
# print(L3)
ans = -float('inf')
for i in range(N+1):
    for j in range(N+1-i):
        #print("i,t->", i, j)
        sL1 = L1[-1] - L1[i]
        #print("sl1->", sL1)
        sL3 = L3[-1]-L3[j]
        #print("sl2->", sL3)
        #print("add->", L2[i])
        #print("sub->", L2[N]-L2[N-j])
        tmp = sL1-sL3+L2[i]-(L2[N]-L2[N-j])
        #print("tmp->", tmp)
        ans = max(ans, sL1-sL3+L2[i]-(L2[N]-L2[N-j]))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
a_ls = [int(i) for i in input().split()]
before = []
_sum_before = 0
before_scores = []
after = []
_sum_after = 0
after_scores = []
best = None
for i in range(2*N):
    _sum_before += a_ls[i]
    heapq.heappush(before, a_ls[i])
    _sum_after += a_ls[-i-1]
    heapq.heappush(after, -a_ls[-i-1])
    if i >= N:
        _sum_before -= heapq.heappop(before)
        _sum_after -= -heapq.heappop(after)
    if i >= N - 1:
        before_scores.append(_sum_before)
        after_scores.append(_sum_after)
after_scores = after_scores[::-1]
for i in range(N):
    score = before_scores[i] - after_scores[i]
    if best is None:
        best = score
    best = score if best < score else best
print(best)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
a_ls = [int(i) for i in input().split()]
before = []
before_scores = []
after = []
after_scores = []
best = None
for i in range(2*N):
    heapq.heappush(before, a_ls[i])
    heapq.heappush(after, -a_ls[-i-1])
    if i >= N:
        heapq.heappop(before)
        heapq.heappop(after)
    if i >= N - 1:
        before_scores.append(sum(before[-N:]))
        after_scores.append(-sum(after[:N]))
after_scores = after_scores[::-1]
for i in range(N):
    score = before_scores[i] - after_scores[i]
    if best is None:
        best = score
    best = score if best < score else best
print(best)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
a_ls = [int(i) for i in input().split()]
before = []
after = []
best = None
for i in range(len(a_ls)-N):
    heapq.heappush(before, a_ls[i])
    if i > N - 1:
        score = sum(before[-N:]) - sum(sorted(a_ls[i+1:])[:N])
        if best is None:
            best = score
        best = best if best > score else score
print(best)

Submission status: Wrong Answer

Solution code:
import heapq

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

l = A[:int(len(A)/2)]
r = A[int(len(A)/2):]
r = list(map(lambda n : n*-1, r))

#print(l)
#print(r)

heapq.heapify(l)
heapq.heapify(r)

for i in range(N):
    if len(l) >= len(r):
        heapq.heappop(l)
    else:
        heapq.heappop(r)

#print(r)
#print(l)

r = list(map(lambda n : n*-1, r))

print(sum(l)-sum(r))

Submission status: Wrong Answer

Solution code:
import heapq
n= int(input())
a=[int(i) for i in input().split()]
heap1=[]
heap2=[]
a_max=[]
b_max=[]
s=0
for i in range(n):
    heapq.heappush(heap1, a[i])
    s+=a[i]
a_max.append(s)
for i in range(n):
    heapq.heappush(heap1,a[n+i])
    mini=heapq.heappop(heap1)
    s=s+a[n+i]-mini
    a_max.append(s)
s=0
for i in range(n):
    heapq.heappush(heap2,-a[2*n+i])
    s=s-a[2*n+i]
b_max.append(s)    
for i in range(n):
    heapq.heappush(heap2,-a[2*n-1-i])
    mini=heapq.heappop(heap2)
    s=s-a[2*n-1-i]-mini
    b_max.append(s)
ans=a_max[0]+b_max[len(b_max)-1]
for i in range(n):
    res=a_max[i]+b_max[-(i+1)]
    ans=max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n= int(input())
a=[int(i) for i in input().split()]
heap1=[]
heap2=[]
a_max=[]
b_max=[]
s=0
for i in range(n):
    heapq.heappush(heap1, a[i])
    s+=a[i]
a_max.append(s)
for i in range(n):
    heapq.heappush(heap1,a[n+i])
    mini=heapq.heappop(heap1)
    s=s+a[n+i]-mini
    a_max.append(s)
s=0
for i in range(n):
    heapq.heappush(heap2,-a[2*n+i])
    s=s-a[2*n+i]
b_max.append(s)    
for i in range(n):
    heapq.heappush(heap2,-a[2*n-1-i])
    mini=heapq.heappop(heap2)
    s=s-a[2*n-1-i]-mini
    b_max.append(s)
ans=-(10**15)
for i in range(n):
    res=a_max[i]+b_max[-(i+1)]
    if ans<res:
        ans=res
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n= int(input())
a=[int(i) for i in input().split()]
heap1=[]
heap2=[]
a_max=[]
b_max=[]
s=0
for i in range(n):
    heapq.heappush(heap1, a[i])
    s+=a[i]
a_max.append(s)
for i in range(n):
    heapq.heappush(heap1,a[n+i])
    mini=heapq.heappop(heap1)
    s=s+a[n+i]-mini
    a_max.append(s)
s=0
for i in range(n):
    heapq.heappush(heap2,-a[2*n+i])
    s=s-a[2*n+i]
b_max.append(s)    
for i in range(n):
    heapq.heappush(heap2,-a[2*n-1-i])
    mini=heapq.heappop(heap2)
    s=s-a[2*n-1-i]-mini
    b_max.append(s)
ans=a_max[1]+b_max[-2]
for i in range(n):
    res=a_max[i]+b_max[-(i+1)]
    if ans<res:
        ans=res
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n= int(input())
a=[int(i) for i in input().split()]
heap1=[]
heap2=[]
a_max=[]
b_max=[]
s=0
for i in range(n):
    heapq.heappush(heap1, a[i])
    s+=a[i]
a_max.append(s)
for i in range(n):
    heapq.heappush(heap1,a[n+i])
    mini=heapq.heappop(heap1)
    s=s+a[n+i]-mini
    a_max.append(s)
s=0
for i in range(n):
    heapq.heappush(heap2,-a[2*n+i])
    s=s-a[2*n+i]
b_max.append(s)    
for i in range(n):
    heapq.heappush(heap2,-a[2*n-1-i])
    mini=heapq.heappop(heap2)
    s=s-a[2*n-1-i]-mini
    b_max.append(s)
ans=a_max[0]+b_max[-1]
for i in range(n):
    res=a_max[i]+b_max[-(i+1)]
    if ans<res:
        ans=res
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n= int(input())
a=[int(i) for i in input().split()]
heap1=[]
heap2=[]
a_max=[]
b_max=[]
s=0
for i in range(n):
    heapq.heappush(heap1, a[i])
    s+=a[i]
a_max.append(s)
for i in range(n):
    heapq.heappush(heap1,a[n+i])
    mini=heapq.heappop(heap1)
    s=s+a[n+i]-mini
    a_max.append(s)
s=0
for i in range(n):
    heapq.heappush(heap2,-a[2*n+i])
    s=s-a[2*n+i]
b_max.append(s)    
for i in range(n):
    heapq.heappush(heap2,-a[2*n-1-i])
    mini=heapq.heappop(heap2)
    s=s-a[2*n-1-i]-mini
    b_max.append(s)
ans=-10000000
for i in range(n):
    res=a_max[i]+b_max[-(i+1)]
    if ans<res:
        ans=res
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
a = [0] + list(map(int, input().split())) #index調整
selectleft, remainleft, selectright, remainright = [], [], [], []
leftscore, rightscore = [], []
for i in range(1,n+1): heapq.heappush(selectleft, a[i]) # selectleftからは最小値を取り出す
leftscore.append(sum(selectleft)) # 左のn個中n個選ぶとき
for i in range(n+1,2*n+1): # n+1~n+n個の中から選ぶとき
    poped = heapq.heappop(selectleft)
    tmpscore = leftscore[-1] - poped
    heapq.heappush(remainleft, (-1) * a[i])
    heapq.heappush(remainleft, (-1) * poped)
    poped = heapq.heappop(remainleft) * (-1)
    tmpscore += poped
    heapq.heappush(selectleft, poped)
    leftscore.append(tmpscore)
for i in range(2*n+1,3*n+1):
    heapq.heappush(selectright, (-1)*a[i]) # selectrightからは最大値を取り出す
rightscore.append(sum(selectright)*(-1))
for i in range(2*n,n,-1):
    poped = heapq.heappop(selectright) * -1
    tmpscore = rightscore[-1] - poped
    heapq.heappush(remainright, a[i])
    heapq.heappush(remainright, poped)
    poped = heapq.heappop(remainright)
    tmpscore += poped
    heapq.heappush(selectright, poped)
    rightscore.append(tmpscore)
rightscore.reverse()
print(max(map(lambda x,y:x-y, leftscore, rightscore)))