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: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import heapq

def make_score(l1, l2):
    h = []
    for num in l1:
        heapq.heappush(h, num)

    init_score = sum(h)

    v_temp = [0]
    v_max = [0]

    for num in l2:
        mini = heapq.heappop(h)
        score = num - mini
        heapq.heappush(h, num)
        v_temp.append(v_temp[-1] + score)
        if v_temp[-1] > v_max[-1]:
            v_max.append(v_temp[-1])
        else:
            v_max.append(v_max[-1])

    return init_score, v_max


def make_score_rev(l1, l2):
    h = []
    for num in l1:
        heapq.heappush(h, -num)

    init_score = -sum(h)

    v_temp = [0]
    v_max = [0]

    for num in l2:
        maxi = heapq.heappop(h) * -1
        score = maxi - num
        heapq.heappush(h, -num)
        v_temp.append(v_temp[-1] + score)
        if v_temp[-1] > v_max[-1]:
            v_max.append(v_temp[-1])
        else:
            v_max.append(v_max[-1])

    return init_score, v_max

n = getN()
nums = getList()


l1 = nums[:n]
l2 = nums[n:2*n]
l3 = nums[2*n:]

init_zen, v_max_zen = make_score(l1, l2)
init_kou, v_max_kou = make_score_rev(l3, l2[::-1])

# print(init_zen, init_kou)
# print(v_max_zen, v_max_kou)

t_score = 0
for i, j in zip(v_max_zen, v_max_kou[::-1]):
    if t_score < i + j:
        t_score = i + j

print(init_zen - init_kou + t_score)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())

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

from heapq import heappop,heappush

q = []
left_sum = 0

for i in range(N):
    heappush(q, a[i])
    left_sum+=a[i]

ls_list = [left_sum]

for i in range(N):
    heappush(q,a[i+N])
    b = heappop(q)
    left_sum-=b
    left_sum+=a[i+N]
    ls_list.append(left_sum)

q = []

right_sum = 0
for i in range(N):

    heappush(q, -a[3*N-i-1])
    right_sum+=a[3*N-i-1]

rs_list = [right_sum]

for i in range(N):
    heappush(q,-a[2*N-i-1])
    b = -heappop(q)
    right_sum-=b
    right_sum+=a[2*N-i-1]
    rs_list.append(right_sum)

rs_list = rs_list[::-1]

max_score = -10**27

for i in range(N+1):
    max_score = max(ls_list[i]-rs_list[i],max_score)

print(max_score)

Submission status: Accepted

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 ** 15
for i in range(N, N*2+1):
    res = max(res, s[i] - t[N*3-i])

print(res)

Submission status: Accepted

Solution code:
import heapq

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

q1 = a[:N]
heapq.heapify(q1)
sum1 = sum(a[:N])
slist1 = [sum1]
for k in range(N, 2*N):
    sum1 += a[k] - heapq.heappushpop(q1, a[k])
    slist1.append(sum1)

q2 = [-i for i in a[2*N:]]
heapq.heapify(q2)
sum2 = (-1)*sum(a[2*N:])
slist2 = [sum2]
for k in range(2 * N - 1, N - 1, -1):
    sum2 += -1*a[k] - heapq.heappushpop(q2, -1*a[k])
    slist2.append(sum2)

ans = -1*float("inf")
for i in range(N+1):
    ans = max(ans, slist2[-1*(i+1)] + slist1[i])
print(ans)

Submission status: Accepted

Solution code:
#### import ####
import sys
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N = I()
a = [0] + III()

from heapq import heapify,heappush,heappop
red = [0]*(3*N+1)
blue = [0]*(3*N+1)

q1 = a[1:N+1]
red[N] = sum(q1)
heapify(q1)

for k in range(N+1,2*N+1):
  heappush(q1,a[k])
  red[k] = red[k-1] + a[k] -q1[0]
  heappop(q1)

q2 = a[2*N+1:3*N+1]
blue[2*N] = sum(q2)
q2 = [(-x,x) for x in q2]
heapify(q2)

for k in range(N,2*N)[::-1]:
  heappush(q2,(-a[k+1],a[k+1]))
  blue[k] = blue[k+1] + a[k+1] -q2[0][1]
  heappop(q2)
  
ans = -float('inf')
for i in range(N,2*N+1):
  temp = red[i]-blue[i]
  if temp > ans:
    ans = temp
print(ans)

Submission status: Accepted

Solution code:
import heapq

N = int(input())

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

n1 = a[:N]

heapq.heapify(n1)

sum1 = sum(n1)

arr1 = [sum1]

for i in range(N, 2*N):
    heapq.heappush(n1, a[i])
    sum1 += a[i]
    sum1 -= heapq.heappop(n1)
    arr1.append(sum1)

n2 = [-i for i in a[2*N:]]

heapq.heapify(n2)
sum2 = sum(n2)

arr2 = [sum2]

for i in range(1, N+1):
    heapq.heappush(n2, -a[2*N-i])
    sum2 += -a[2*N-i]
    sum2 -= heapq.heappop(n2)
    arr2.append(sum2)

ans = -10**17

for i, j in zip(arr1, reversed(arr2)):
    ans = max(ans, i+j)

print(ans)

Submission status: Accepted

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: Accepted

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(len(ans1))))

Submission status: Accepted

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


inf = float("inf")

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 = a[N:2*N]
    sumL = [0 for _ in range(N+1)] # sumL[i]: a[0]からa[N-1+i]までの大きい順にN個の和
    sumR = [0 for _ in range(N+1)] # sumR[i]: -(a[N-1+i]からa[3*N-1]までの小さい順にN個の和)

    sumL[0] = sum(L)
    sumR[N] = sum(R)

    for i in range(N):
        heapq.heappush(L, M[i])
        l = heapq.heappop(L)
        diff = M[i] - l
        sumL[i+1] = sumL[i] + diff
    
    for i in range(N-1, -1, -1):
        heapq.heappush(R, -M[i])
        r = heapq.heappop(R)
        diff = -M[i] - r
        sumR[i] = sumR[i+1] + diff
    
    res = max(suml + sumr for suml, sumr in zip(sumL, sumR))
    print(res)
    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: Accepted

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


inf = float("inf")

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 = a[N:2*N]
    sumL = [0 for _ in range(N+1)] # sumL[i]: a[0]からa[N-1+i]までの大きい順にN個の和
    sumR = [0 for _ in range(N+1)] # sumR[i]: -(a[N-1+i]からa[3*N-1]までの小さい順にN個の和)

    sumL[0] = sum(L)
    sumR[N] = sum(R)

    for i in range(N):
        l = heapq.heappop(L)
        diff = M[i] - l
        if diff > 0:
            sumL[i+1] = sumL[i] + diff
            heapq.heappush(L, M[i])
        else:
            sumL[i+1] = sumL[i]
            heapq.heappush(L, l)
    
    for i in range(N-1, -1, -1):
        r = heapq.heappop(R)
        diff = -M[i] - r
        if diff > 0:
            sumR[i] = sumR[i+1] + diff
            heapq.heappush(R, -M[i])
        else:
            sumR[i] = sumR[i+1]
            heapq.heappush(R, r)
    
    res = -inf
    for suml, sumr in zip(sumL, sumR):
        res = max(res, suml + sumr)
    print(res)
    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: Accepted

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

n=int(input())
a=[int(i) for i in input().split()]
#f=[-i for i in a[:n]]
f=a[:n]
l=[-i for i in a[2*n:]]
heapq.heapify(f)
heapq.heapify(l)
fs=[0]*(n+1)
ls=[0]*(n+1)
fs[0]=sum(f)
ls[n]=-sum(l)

for i in range(n):
    c=a[n+i]
    m=heapq.heappushpop(f,c)
    fs[i+1]=fs[i]+c-m
#    print(f,c,m)

for i in range(n):
    c=a[2*n-1-i]
    m=heapq.heappushpop(l,-c)
    ls[n-i-1]=ls[n-i]+c+m
#    print(l,-c,m)


ans=fs[0]-ls[0]
for k in range(n+1):
    ans=max(ans,fs[k]-ls[k])
print(ans)#,a,n,fs,ls)

Submission status: Accepted

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

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



if __name__ == "__main__":
    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

    print(calc(front_sum, back_sum))

Submission status: Accepted

Solution code:
import heapq

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



if __name__ == "__main__":
    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

    print(calc(front_sum, back_sum))

Submission status: Accepted

Solution code:
import heapq

def calc(front_sum, back_sum):
    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]
    return max([front_sums[i] - back_sums[-i-1] for i in range(n+1)])



if __name__ == "__main__":
    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

    print(calc(front_sum, back_sum))

Submission status: Accepted

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: Accepted

Solution code:
import heapq

n = int(input())
A = [int(x) for x in input().split()]
A_rev = [-x for x in A[::-1]]

def get_sum_list(A):
  h = []
  result = []
  current_sum = 0
  for i,a in enumerate(A[:2*n]):
    heapq.heappush(h,a)
    current_sum += a
    if i >= n:
      m = heapq.heappop(h)
      current_sum -= m
    if i >= n-1:
      result.append(current_sum)
  return result

from_left = get_sum_list(A)
from_right = get_sum_list(A_rev)

ans = -10**18
for i in range(n+1):
  score = from_left[i] + from_right[n-i]
  if ans < score:
    ans = score
    
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop

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

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
N=int(input())
A=list(map(int,input().split()))
X=0
Z=0
mae=[]
ushiro=[]
for i in range(N):
    X+=A[i]
    heappush(mae,A[i])
    Z-=A[i+2*N]
    heappush(ushiro,-1*A[i+2*N])
maedata=[0]*(N+1)
ushirodata=[0]*(N+1)
maedata[0]=X
ushirodata[0]=Z
for i in range(N):
    X+=A[i+N]
    heappush(mae,A[i+N])
    X-=heappop(mae)
    maedata[i+1]=X
    
    Z-=A[2*N-i-1]
    heappush(ushiro,-1*A[2*N-i-1])
    Z-=heappop(ushiro)
    ushirodata[i+1]=Z
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,maedata[i]+ushirodata[N-i])
print(ans)

Submission status: Accepted

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**15
# print(s3)
for i,j in zip(s1,s3[::-1]):
    # print(i,j)
    M = max(M,i+j)

print(M)

Submission status: Accepted

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**15
# print(s3)
for i,j in zip(s1,s3[::-1]):
    # print(i,j)
    M = max(M,i+j)

print(M)

Submission status: Accepted

Solution code:
n=int(input())
a_list=list(map(int,input().split()))
import heapq
pre=a_list[0:n]
heapq.heapify(pre)
pre_list=[sum(a_list[0:n])]
for i in range(n):
    heapq.heappush(pre,a_list[i+n])
    pre_list.append(pre_list[-1]+a_list[i+n]-heapq.heappop(pre))
b_list=[]
for i in range(2*n,3*n):
    b_list.append(-a_list[i])
post=b_list
heapq.heapify(post)
post_list=[sum(b_list)]
for i in range(n):
    heapq.heappush(post,-a_list[2*n-1-i])
    post_list.append(post_list[-1]-a_list[2*n-1-i]-heapq.heappop(post))
ans=-10**16
for i in range(n+1):
    Max=pre_list[i]+post_list[n-i]
    ans=max(ans,Max)
print(ans)

Submission status: Accepted

Solution code:
import heapq
import numpy as np

n = int(input())
a = list(map(int, input().split()))
s_front = [0] * (n + 1)
s_back = [0] * (n + 1)

a_front = a[:n]
heapq.heapify(a_front)
s_front[0] = sum(a_front)
for k in range(n):
    heapq.heappush(a_front, a[n + k])
    b = heapq.heappop(a_front)
    s_front[k + 1] = s_front[k] + a[n + k] - b

a_back = [(-x, x) for x in a[2 * n:]]
heapq.heapify(a_back)
s_back[0] = sum([x[1] for x in a_back])
for k in range(n):
    heapq.heappush(a_back, (-1 * a[2 * n - k - 1], a[2 * n - k - 1]))
    b = heapq.heappop(a_back)[1]
    s_back[k + 1] = s_back[k] + a[2 * n - k - 1] - b

s_front = np.array(s_front)
s_back = np.array(s_back[::-1])
print(max(s_front - s_back))

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
N=int(input())
A=list(map(int,input().split()))
X=[]
Y=[]
Xnow=sum(A[0:N])
Ynow=-1*sum(A[2*N:3*N])
ansX=[Xnow]
ansY=[Ynow]
for i in range(N):
    heappush(X,A[i])
    heappush(Y,-1*A[i+2*N])
for i in range(N):
    a=A[N+i]
    Xnow+=a
    heappush(X,a)
    a=heappop(X)
    Xnow-=a
    ansX+=[Xnow]
    
    a=-1*A[2*N-1-i]
    Ynow+=a
    heappush(Y,a)
    a=heappop(Y)
    Ynow-=a
    ansY+=[Ynow]

ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,ansX[i]+ansY[N-i])
print(ans)

Submission status: Accepted

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()))
left = a[:n]
suml = sum(left)
right = [-a[i] for i in range(3*n-1,2*n-1,-1)]
sumr = sum(right)
Suml = [suml]
Sumr = [sumr]
heapify(left)
heapify(right)

#左からi(n<=i<=2*n-1)番目までの大きい方の総和と(3*n-1-i)番目までの小さい方の総和を求める
for i in range (n,2*n):
    heappush(left,a[i])
    x = heappop(left) #ここまでで常に大きい方からnことって来ている
    suml += a[i]-x
    Suml.append(suml)
for i in range(2*n-1,n-1,-1):
    heappush(right,-a[i])
    y = heappop(right)
    sumr += -a[i]-y
    Sumr.append(sumr)
ans = -inf
for i in range(n+1):
    ans = max(ans,Suml[i]+Sumr[n-i])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from heapq import heapreplace, heapify
N=int(input())
A=np.array([int(a) for a in input().split(" ")])
lheap, rheap = list(A[:N]), list(-A[2*N:])
heapify(lheap)
heapify(rheap)
Lsum, Rsum = sum(lheap), sum(rheap)
left = [Lsum]
right = [Rsum]

for i in range(N):
    if A[N+i] > lheap[0]:
        Lsum += (A[N+i]-lheap[0])
        heapreplace(lheap, A[N+i])
    
    if -A[2*N-i-1] > rheap[0]:
        Rsum += (-A[2*N-i-1]-rheap[0])
        heapreplace(rheap, -A[2*N-i-1])
    
    left.append(Lsum)
    right.append(Rsum)
print(max(np.array(left)+np.array(right)[::-1]))

Submission status: Accepted

Solution code:
import heapq

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

h = []
goukei = 0
for a in a_list[:N]:
    goukei += a
    heapq.heappush(h,a)

k_left_goukei = [goukei]

for a in a_list[N:2*N]:
    goukei += a
    d = heapq.heappushpop(h,a)
    goukei -= d
    k_left_goukei.append(goukei)

h = []
goukei = 0
for a in a_list[::-1][:N]:
    goukei += a
    heapq.heappush(h,(-a,a))
    
k_right_goukei = [goukei]

for a in a_list[::-1][N:2*N]:
    goukei += a
    d = heapq.heappushpop(h,(-a,a))
    goukei -= d[1]
    k_right_goukei.append(goukei)

max_diff = None
for l, r in zip(k_left_goukei, k_right_goukei[::-1]):
    diff = l-r
    if max_diff == None:
        max_diff = diff
    else:
        max_diff = max(diff,max_diff)

print(max_diff)

Submission status: Accepted

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


def brute_force():
    N = int(input())
    L = list(map(int, input().split()))

    ans = -float('inf')
    for i in range(N, 2*N+1):
        tmp = sum(list(sorted(L[:i], reverse=True))[:N])\
            - sum(list(sorted(L[i:]))[:N])

        ans = max(ans, tmp)


def solve():
    N = int(input())
    L = list(map(int, input().split()))

    first = L[:N]
    heapq.heapify(first)
    first_sum = [0]*(N+1)
    tmp_first = sum(first)
    first_sum[0] = tmp_first
    for i in range(N, 2*N):
        first_ind = i-N+1
        if L[i] > first[0]:
            rem = heapq.heappop(first)
            heapq.heappush(first, L[i])
            tmp_first += L[i]-rem
        first_sum[first_ind] = tmp_first

    third = [-v for v in L[N*2:]]
    heapq.heapify(third)
    third_sum = [0]*(N+1)
    tmp_third = -sum(third)
    third_sum[-1] = tmp_third
    for i in reversed(range(N+1, 2*N+1)):
        third_ind = i-N-1
        if -L[i-1] > third[0]:
            rem = heapq.heappop(third)
            heapq.heappush(third, -L[i-1])
            tmp_third = tmp_third + rem+L[i-1]
        third_sum[third_ind] = tmp_third

    ans = max([f-l for f, l in zip(first_sum, third_sum)])
    print(ans)


# brute_force()
solve()

Submission status: Accepted

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


def brute_force():
    N = int(input())
    L = list(map(int, input().split()))

    ans = -float('inf')
    for i in range(N, 2*N+1):
        tmp = sum(list(sorted(L[:i], reverse=True))[:N])\
            - sum(list(sorted(L[i:]))[:N])
        #print("first->", L[:i])
        #print("sum_f->", sum(list(sorted(L[:i], reverse=True))[:N]))
        #print("second->", L[i:])
        #print("sum_sec->", sum(list(sorted(L[i:]))[:N]))
        #print("tmp->", tmp)
        # print("----")

        ans = max(ans, tmp)

    # print(ans)


def solve():
    N = int(input())
    L = list(map(int, input().split()))

    first = L[:N]
    heapq.heapify(first)
    first_sum = [0]*(N+1)
    tmp_first = sum(first)
    first_sum[0] = tmp_first
    #print("first->", first)
    for i in range(N, 2*N):
        first_ind = i-N+1
        #print("new->", L[i])
        if L[i] > first[0]:
            rem = heapq.heappop(first)
            heapq.heappush(first, L[i])
            tmp_first += L[i]-rem
            #print("rem->", rem)
            #print("new_sum->", tmp_first)
        first_sum[first_ind] = tmp_first
        #print("first_sum->", first_sum)
        # print("--------")

    third = [-v for v in L[N*2:]]
    heapq.heapify(third)
    third_sum = [0]*(N+1)
    tmp_third = -sum(third)
    third_sum[-1] = tmp_third
    #print("third->", third)
    for i in reversed(range(N+1, 2*N+1)):
        #print("cand->", L[i:])
        third_ind = i-N-1
        #print("new->", L[i-1])
        #print("last->", third[0])
        if -L[i-1] > third[0]:
            rem = heapq.heappop(third)
            #print("rem->", rem)
            heapq.heappush(third, -L[i-1])
            tmp_third = tmp_third + rem+L[i-1]
        #print("new_sum->", tmp_third)
        third_sum[third_ind] = tmp_third
        # print("----")
    # print(third_sum)
    # print(first_sum)
    # print(L)

    ans = max([f-l for f, l in zip(first_sum, third_sum)])
    print(ans)


# brute_force()
solve()

Submission status: Accepted

Solution code:
def f(a):
	q=a[:n];s=sum(q);heapify(q)
	for e in a[n:n-~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: Accepted

Solution code:
def f(a):
	q=a[:n];s=sum(q);heapify(q)
	for e in a[n:2*n+1]: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: Accepted

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

Submission status: Accepted

Solution code:
def f(a):
	q=a[:n];s=sum(q);heapify(q);yield s
	for e in a[n:2*n]:s+=e-heappushpop(q,e);yield s
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: Accepted

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

Submission status: Accepted

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+=c[i]-heappushpop(d,c[i])
    red+=[s]
    blue+=[t]
print(max(map(sum,zip(red,blue[::-1]))))

#あｈｊｆｋぁｄｓｈｆｌｋじゃｇはｌｋｊｄｊｇｌｋ；あｊｄｇｌｋ；あｄｓｊｇｌ；あｊｓｄｇｌｋ；あｊｓｄｇｌ；かｓ

Submission status: Accepted

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]))
    l_min = heapq.heappop(l_array)
    r_max = heapq.heappop(r_array)[1]

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

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

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

a1 = a[:n]
a2 = a[n:2*n]
a3 = [-x for x in a[2*n:]]

suma1 = [sum(a1)]
suma3 = [-sum(a3)]

heapq.heapify(a1)
heapq.heapify(a3)

for i in range(n):
    heapq.heappush(a1,a[n+i])
    heapq.heappush(a3,-a[2*n-1-i])
    suma1.append(suma1[-1]+a[n+i]-heapq.heappop(a1))
    suma3.append(suma3[-1]+a[2*n-1-i]+heapq.heappop(a3))

ans = suma1[0]-suma3[-1]
for i in range(n):
    ans = max(ans, suma1[i+1]-suma3[-2-i])
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

# 先頭からi(N <=i <= 2N)番目までの要素からN個の要素を選んだときの和の最大値を求める
ql = []
for a in A[:N]:
    heappush(ql, a)
L = [sum(A[:N])]
for a in A[N:(2 * N)]:
    heappush(ql, a)
    m = heappop(ql)
    L.append(L[-1] + a - m)

# 末尾からi(N <=i <= 2N)番目までの要素からN個の要素を選んだときの和の最小値を求める
qr = []
for a in A[-N:]:
    heappush(qr, -a)
R = [sum(A[-N:])]
for a in A[-(N + 1):-(2 * N + 1):-1]:
    heappush(qr, -a)
    m = -heappop(qr)
    R.append(R[-1] + a - m)

# L, R を用いて解を求める
ans = max(l - r for l, r in zip(L, R[::-1]))

# 出力
print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
L = []
R = []
for i in range(N):
  L.append(A[i])
for i in range(N):
  R.append(-A[3*N-i-1])
SUML = [0]*(N+1)
SUMR = [0]*(N+1)
S = sum(L)
T = sum(R)
SUML[0] = S
SUMR[0] = -T
heapq.heapify(L) #これ必要
heapq.heapify(R)
for i in range(N,2*N):
  a = heapq.heappushpop(L,A[i])
  S = S-a+A[i]
  SUML[i-N+1] = S
for j in range(N,2*N):
  b = heapq.heappushpop(R,-A[3*N-j-1])
  T = T-b-A[3*N-j-1]
  SUMR[j-N+1] = -T
ans = -float('inf')
for i in range(N+1):
  if SUML[i]-SUMR[N-i] >= ans:
    ans = SUML[i]-SUMR[N-i]
print(ans)

Submission status: Accepted

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])
    #print(L_acc)

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])
    #print(R_acc)

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

print(ans)