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:
INF = 10 ** 20
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  heapq import heappop,heapify,heappush

def main():
    n = int(input())
    a = list(map(int,input().split()))
    
    lM = [0] * (n + 1)
    rm = [0] * (n + 1)

    q = []
    cumsum = 0
    for i in range(n):
        heappush(q,a[i])
        cumsum += a[i]
    
    lM[0] = cumsum
    drop = 0
    for i in range(n,2 * n):
        heappush(q,a[i])
        drop += heappop(q)
        cumsum += a[i]
        lM[i - n + 1] = cumsum - drop
    
    q = []
    cumsum = 0
    for i in range(3 * n - 1,2 * n - 1,-1):
        heappush(q,-a[i])
        cumsum += a[i]
    
    rm[-1] = cumsum
    drop = 0
    for i in range(2 * n - 1,n - 1,-1):
        heappush(q,-a[i])
        drop -= heappop(q)
        cumsum += a[i]
        rm[i - n] = cumsum - drop
    
    ans = -INF
    for i in range(n + 1):
        ans = max(ans,lM[i] - rm[i])
        
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

# ----- heapq ここから-----
import heapq
class Reverse:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val
        
    def __repr__(self):
        return repr(self.val)
    
class Heapq:
    def __init__(self, arr, desc = False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        if self.desc: return heapq.heappop(self.hq).val
        else: return heapq.heappop(self.hq)
 
    def push(self, a):
        if self.desc: heapq.heappush(self.hq, Reverse(a))
        else: heapq.heappush(self.hq, a)
 
    def top(self):
        if self.desc: self.hq[0].val
        else: return self.hq[0]
# ----- heapq ここまで-----

n = int(input())
a = list(myinput())
# print(a)

red = a[:n]
blue = a[(2*n):]

s_red = sum(red)
s_blue = sum(blue)

ans = s_red - s_blue
# print(ans)

hq_red = Heapq(red,False)
# print(red)
hq_blue = Heapq(blue,True)
# print(blue)

ans = -1*float("inf")

ls_s_red = [s_red]
for k in range(n,2*n):
    hq_red.push(a[k])
    p = hq_red.pop()
    s_red = s_red + a[k] - p  
    ls_s_red.append(s_red)
# print(ls_s_red)   

ls_s_blue = [s_blue]
for k in range(n,2*n):
    hq_blue.push(a[-(k+1)])
    p = hq_blue.pop()
    s_blue = s_blue + a[-(k+1)] - p
    ls_s_blue.append(s_blue)
ls_s_blue_sorted = ls_s_blue[::-1]
# print(ls_s_blue_sorted)

for k in range(len(ls_s_red)):
    M = ls_s_red[k] - ls_s_blue_sorted[k]
    ans = max(ans,M)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heapreplace, heapify


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

dp = [0] * (N + 1)
q = A[:N]
heapify(q)
dp[0] = sum(q)
for i in range(N, 2 * N):
    a = A[i]
    if a > q[0]:
        dp[i - N + 1] += a - heapreplace(q, a)
    dp[i - N + 1] += dp[i - N]


dp2 = [0] * (N + 1)
q = [-A[i] for i in range(2 * N, 3 * N)]
heapify(q)
dp2[N] = -sum(q)
for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    if a < -q[0]:
        dp2[i - N] += a - (-heapreplace(q, -a))
    dp2[i - N] += dp2[i - N + 1]

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

Submission status: Accepted

Solution code:
from heapq import heappush, heapreplace


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

dp = [0] * (N + 1)
q = []
cnt = 0
for i in range(N):
    a = A[i]
    heappush(q, a)
    cnt += a
dp[0] = cnt
for i in range(N, 2 * N):
    a = A[i]
    if a > q[0]:
        cnt += a - heapreplace(q, a)
    dp[i - N + 1] = cnt


dp2 = [0] * (N + 1)
q = []
cnt = 0
for i in range(2 * N, 3 * N):
    a = A[i]
    heappush(q, -a)
    cnt += a
dp2[N] = cnt
for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    if a < -q[0]:
        cnt += a - (-heapreplace(q, -a))
    dp2[i - N] = cnt

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

Submission status: Accepted

Solution code:
import heapq
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = []
    heapq.heapify(q)
    frnt = [None]*3*n
    back = [None]*3*n
    heapq.heappush(q, a[0])
    frnt[0] = a[0]
    for i in range(1, 2*n+1):
        frnt[i] = a[i]
        frnt[i] += frnt[i-1]
        heapq.heappush(q, a[i])
        if n <= i:
            frnt[i] -= heapq.heappop(q)
    q = []
    heapq.heapify(q)
    heapq.heappush(q, -1*a[3*n-1])
    back[3*n-1] = a[3*n-1]
    for i in reversed(range(n-1, 3*n-1)):
        back[i] = a[i]
        back[i] += back[i+1]
        heapq.heappush(q, -1*a[i])
        if i < 2*n:
            back[i] += heapq.heappop(q)
    ans = -float("inf")
    for i in range(n-1, 2*n):
        ans = max(ans, frnt[i] - back[i+1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

left=[0]*(n+1)
right=[0]*(n+1)
left[0]=sum(a[:n])
right[n]=sum(a[n+n:])

mae,usi=a[:n],list(map(lambda x: x*-1,a[n+n:]))

heapq.heapify(mae)
heapq.heapify(usi)

for i in range(n):
    tmp=heapq.heappushpop(mae,a[n+i])
    left[i+1]=left[i]+a[n+i]-tmp
    tmp=heapq.heappushpop(usi,-a[n+n-i-1])
    right[n-i-1]=right[n-i]+a[n+n-i-1]+tmp
# print(mae)
# print(left)
# print(right)
ans=-float('inf')
for i in range(n+1):
    ans=max(ans, left[i]-right[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

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

	left = a[0 : N]
	right = a[N*2 : N*3]

	for i in range(N):
		right[i] *= -1

	left_sum = 0
	right_sum = 0

	heap_left = []
	heap_right = []

	for i in range(N):
		left_sum += left[i]
		heapq.heappush(heap_left, left[i])
		right_sum += right[i]
		heapq.heappush(heap_right, right[i])

	temp1 = [0] * (N + 1)
	temp2 = [0] * (N + 1)

	temp1[0] = left_sum
	temp2[N] = right_sum

	for i in range(0, N):
		left_sum += a[N+i]
		heapq.heappush(heap_left, a[N+i])
		left_sum -= heapq.heappop(heap_left)
		temp1[i+1] = left_sum

	for i in range(0, N):
		right_sum -= a[N*2-1-i]
		heapq.heappush(heap_right, -a[N*2-1-i])
		right_sum -= heapq.heappop(heap_right)
		temp2[N - 1 - i] = right_sum

	ans = -100000000000000000000000000000000000000000
	for i in range(0, N + 1):
		x = temp1[i] + temp2[i]
		if(ans < x):
			ans = x
	print(ans)
main()

Submission status: Accepted

Solution code:
import heapq
n=int(input())
a=list(map(int,input().split()))
s1=sum(a[:n])
hq1=a[:n]
heapq.heapify(hq1)
A=[s1]
for i in range(n,2*n):
  s1+=a[i]
  heapq.heappush(hq1,a[i])
  x=heapq.heappop(hq1)
  s1-=x
  A.append(s1)
a=a[::-1]
s2=sum(a[:n])
hq2=[-a[i] for i in range(n)]
heapq.heapify(hq2)
B=[s2]
for i in range(n,2*n):
  s2+=a[i]
  heapq.heappush(hq2,-a[i])
  x=heapq.heappop(hq2)
  s2-=-x
  B.append(s2)
B=B[::-1]
ans=-10**18
for i in range(len(A)):
  ans=max(ans,A[i]-B[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

pre = [0]*(n+1)
pre_list = [e for e in A[:n]]
heapq.heapify(pre_list)
pre_sum = sum(pre_list)
pre[0] = pre_sum
for i in range(n, 2*n):
    small = heapq.heappushpop(pre_list, A[i])
    pre_sum += A[i] - small
    pre[i-n+1] = pre_sum

suf = [0]*(n+1)
suf_list = [-e for e in A[2*n:]]
heapq.heapify(suf_list)
suf_sum = -sum(suf_list)
suf[-1] = suf_sum
for i in range(2*n-1, n-1, -1):
    large = -heapq.heappushpop(suf_list, -A[i])
    suf_sum += A[i] - large
    suf[i-n] = suf_sum

# print(pre)
# print(suf)

print(max([pre[i] - suf[i] for i in range(n+1)]))

Submission status: Accepted

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

N = int(input())
a = list(map(int, input().split()))
pq = []
s = 0
minus = [-1]*(N+1)

for i in range(3*N-1, 2*N-1, -1):
    heappush(pq, -a[i])
    s += a[i]

minus[N] = s

for i in range(2*N-1, N-1, -1):
    if a[i]<-pq[0]:
        s -= -heappop(pq)
        heappush(pq, -a[i])
        s += a[i]
    
    minus[i-N] = s

pq = []
s = 0

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

ans = s-minus[0]

for i in range(N, 2*N):
    if a[i]>pq[0]:
        s -= heappop(pq)
        heappush(pq, a[i])
        s += a[i]
    
    ans = max(ans, s-minus[i-N+1])

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
import heapq as hq
f1=[0]*(3*n)
f1[n-1]=sum(a[:n])
h=a[:n]
hq.heapify(h)
su=f1[n-1]
for i in range(n,2*n):
    cur=a[i]
    x=hq.heappop(h)
    if cur>x:
        su-=x
        su+=cur
        hq.heappush(h,cur)
    else:
        hq.heappush(h,x)
    f1[i]=su
f2=[0]*(3*n)
f2[2*n]=sum(a[2*n:])
su=f2[2*n]
h2=[]
for i in a[2*n:]:
    h2.append(-i)
hq.heapify(h2)
for i in range(2*n-1,n-1,-1):
    cur=a[i]
    x=-1*hq.heappop(h2)
    if cur<x:
        su-=x
        su+=cur
        hq.heappush(h2,-cur)
    else:
        hq.heappush(h2,-x)
    f2[i]=su
ans=-float('inf')
for i in range(n-1,2*n):
    ans=max(ans,f1[i]-f2[i+1])
print(ans)

Submission status: Accepted

Solution code:

import heapq 
n = int(input())
An = list(map(int, input().split()))
former = An[:n]
latter = An[2*n:]
latter = list(map(lambda x:-x, latter))
heapq.heapify(former)
heapq.heapify(latter)

sum_former = sum(former)
sum_latter = sum(latter)

former_list = [0]*(n+1) 
latter_list = [0]*(n+1) 
former_list[0] = sum_former 
latter_list[0] = sum_latter 

for i in range(n, 2*n):
  heapq.heappush(former, An[i])
  m = heapq.heappop(former)
  former_list[i-n+1] = former_list[i-n] + An[i] - m 

for i in range(2*n-1, n-1, -1):
  heapq.heappush(latter, -An[i])
  m = heapq.heappop(latter)
  latter_list[2*n-i] = latter_list[2*n-i-1] - An[i] - m

latter_list.reverse()
ans = -float('inf')
for i in range(n+1):
  ans = max(ans, former_list[i]+latter_list[i])
print(ans)

Submission status: Accepted

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

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

h = list(map(lambda x: -x, a[2*n:]))
heapq.heapify(h)
second = [0] * (n+1)
s = - sum(a[2*n:])
second[0] = s
for i in range(n):
    s -= a[2*n - i - 1]
    heapq.heappush(h, -a[2*n - i - 1])
    s -= heapq.heappop(h)
    second[i+1] = s

ans = - 10 ** 18
for i in range(n+1):
    ans = max(ans, first[i] + second[n-i])
print(ans)

Submission status: Accepted

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

b = list(enumerate(a))

l = sorted(b[:2*n], key=lambda x: x[1], reverse=True)
r = sorted(b[n:], key=lambda x: x[1])

big = [0] * (3*n)
small = [0] * (3*n)

for i, (pos, z) in enumerate(l):
    big[pos] = i
for i, (pos, z) in enumerate(r):
    small[pos] = i

first = sum(a[:n])
second = 0
for pos, z in r[:n]:
    second += z
i = 2 * n
j = n-1
ans = first - second
for split in range(n, 2*n):
    if big[split] < i:
        first += a[split]
        i -= 1
        while l[i][0] > split:
            i -= 1
        first -= l[i][1]
    if small[split] <= j:
        second -= a[split]
        j += 1
        while r[j][0] < split:
            j += 1
        second += r[j][1]
    ans = max(ans, first - second)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N=int(input())
a=list(map(int,input().split()))
l=[None]*(N+1)
r=[None]*(N+1)
h=a[:N]
s=sum(h)
heapq.heapify(h)
l[0]=s
for i in range(N):
    heapq.heappush(h,a[i+N])
    s+=a[i+N]-heapq.heappop(h)
    l[i+1]=s
h=list(map(lambda x:-x,a[2*N:]))
heapq.heapify(h)
s=sum(h)
r[-1]=s
for i in range(N):
    heapq.heappush(h,-a[-N-i-1])
    s+=-a[-N-i-1]-heapq.heappop(h)
    r[-i-2]=s
a=l[0]+r[0]
for i in range(1,N+1):
    if a<l[i]+r[i]:
        a=l[i]+r[i]
print(a)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

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

L = A[:N]
heapify(L)
sumL = [sum(A[:N])]

for i in range(N):
    x = heappop(L)
    if x < A[N + i]:
        sumL.append(sumL[-1] - x + A[N + i])
        heappush(L, A[N + i])
    else:
        sumL.append(sumL[-1])
        heappush(L, x)

R = list(map(lambda x: -x, A[2 * N:]))
heapify(R)
sumR = [sum(A[2 * N:])]

for i in range(N):
    x = -heappop(R)
    if x > A[2 * N - 1 - i]:
        sumR.append(sumR[-1] - x + A[2 * N - 1 - i])
        heappush(R, -A[2 * N - 1 - i])
    else:
        sumR.append(sumR[-1])
        heappush(R, -x)

res = -10**18

for i in range(N + 1):
    res = max(res, sumL[i] - sumR[-1 - i])

print(res)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    wakeme = N
    Aleftsum = [0 for _ in range(3*N+1)]
    Arightsum = [0 for _ in range(3*N+1)]

    leftA = [x for x in A[:N]]
    rightA = [-x for x in A[-N:]]

    heapq.heapify(leftA)
    heapq.heapify(rightA)

    lsum = sum(leftA)
    rsum = sum(rightA)

    Aleftsum[wakeme] = lsum
    Arightsum[2*N] = -rsum

    # [0, N)から[0, 2N)までの和が欲しい
    # Aleftsum(i): [0, i)までの上位N個の和

    # [2N, 3N)から[N, 3N)までの和が欲しい
    # Arightsum(i): [i, 3N)までの上位N個の和

    for i in range(N):
        # [0, N+1)から[0, 2N)までやる。
        # [0, wakeme + i + 1)の和を計算する。
        # wakeme=Nなので、wakeme + i + 1 = 2N -> i = N - 1
        newl = A[wakeme + i]
        lsum += newl
        lsum -= heapq.heappushpop(leftA, newl)
        Aleftsum[wakeme+i+1] = lsum

        # [2N-1, 3N)から[N, 3N)までやる。
        # r_wakeme = 2N-1として、
        # r_wakeme - i = 2N - 1 -> i=0
        # r_wakeme - i = N -> i=N-1
        newr = A[2*N-1 - i]
        rsum -= newr
        rsum -= heapq.heappushpop(rightA, -newr)
        Arightsum[2*N-1 - i] = -rsum

    ans = -inf
    for i in range(N, 2*N+1):
        ans = max(ans, Aleftsum[i] - Arightsum[i])

    print(ans)
main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    wakeme = N
    Aleftsum = [0 for _ in range(3*N+1)]
    leftA = [x for x in A[:N]]
    heapq.heapify(leftA)
    subsum = sum(leftA)
    Aleftsum[wakeme] = subsum
    for i in range(N):
        heapq.heappush(leftA, A[wakeme + i])
        subsum += A[wakeme + i]
        subsum -= heapq.heappop(leftA)
        Aleftsum[wakeme+i+1] = subsum

    Arightsum = [0 for _ in range(3*N+1)]
    rightA = [-x for x in A[-N:]]
    heapq.heapify(rightA)
    subsum = sum(rightA)
    wakeme = 2*N
    Arightsum[wakeme] = -subsum
    for i in range(1, N+1):
        heapq.heappush(rightA, -A[wakeme-i])
        subsum -= A[wakeme - i]
        subsum -= heapq.heappop(rightA)
        Arightsum[wakeme - i] = -subsum
    ans = -inf
    for i in range(N, 2*N+1):
        ans = max(ans, Aleftsum[i] - Arightsum[i])
    print(ans)
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import heapq
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, a: "List[int]"):
    h = a[:N]
    heapq.heapify(h)
    l1 = [0] * (N + 1)
    l1[0] = sum(h)
    for i in range(N):
        m = heapq.heappushpop(h, a[N + i])
        l1[i + 1] = l1[i] + a[N + i] - m
    h = [-ai for ai in a[-N:]]
    heapq.heapify(h)
    l2 = [0] * (N + 1)
    l2[N] = sum(h)
    for i in reversed(range(N)):
        m = heapq.heappushpop(h, -a[N + i])
        l2[i] = l2[i + 1] + (-a[N + i]) - m
    print(max(l1[i] + l2[i] for i in range(N + 1)))


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 sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import heapq

def main():
    mod=10**9+7
    N=I()
    a=LI()
    q1=a[:N]
    s1=[0]*(N+1)#境界を決めたときの，a'前半部分の最大値
    s1[0]=sum(q1)
    heapq.heapify(q1)
        
    q2=[]
    heapq.heapify(q2)
    s2=[0]*(N+1)
    for i in range(N):
        b=a[-1-i]*(-1)
        s2[0]+=b
        heapq.heappush(q2,b)
    
    
    for i in range(N):
        bb=a[i+N]
        heapq.heappush(q1,bb)
        b=heapq.heappop(q1)
        s1[i+1]=s1[i]+bb-b
        
        cc=a[-1-N-i]*(-1)
        heapq.heappush(q2,cc)
        c=heapq.heappop(q2)
        s2[i+1]=s2[i]+cc-c
        
    L=[0]*(N+1)
    ans=-1*10**16
    for i in range(N+1):
        temp=s1[i]+s2[-1-i]
        if ans<temp:
            ans=temp
    print(ans)
        
        
    

main()

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
Af = A[:N]
Ab = [-i for i in A[2*N:]]
asum = sum(Af)
bsum = -sum(Ab)
bsum2 = -sum(Ab)
heapq.heapify(Af)
heapq.heapify(Ab)
flist = [sum(Af)]
blist = []
for i in range(N,2*N):
    mina = heapq.heappop(Af)
    if A[i] > mina:
        asum = asum -mina + A[i]
        flist.append(asum)
        heapq.heappush(Af,A[i])        
    else:
        flist.append(asum)
        heapq.heappush(Af,mina)
    
for i in range(2*N-1,N-1,-1):
    maxa = heapq.heappop(Ab)
    if (-A[i]) > maxa:
        bsum2 = bsum2 + maxa +A[i]
        blist.append(bsum2)
        heapq.heappush(Ab,-A[i])
    else:
        blist.append(bsum2)
        heapq.heappush(Ab,maxa)    
blist = blist[::-1]
ans = []
blist.append(bsum)
for i in range(N+1):
    ans.append(flist[i]-blist[i])
print(max(ans))

Submission status: Accepted

Solution code:
import heapq
import bisect
n = int(input())
a = list(map(int, input().split()))
first_que = [a[i] for i in range(n)]
first_sum = sum(first_que)
heapq.heapify(first_que)
latter_que = [a[i] * -1 for i in range(2*n,3*n)]
latter_sum = sum(latter_que) * -1
heapq.heapify(latter_que)
ans = [0 for i in range(n+1)]
ans[0] = first_sum
for i in range(n,2*n):
    heapq.heappush(first_que, a[i])
    p = heapq.heappop(first_que)
    first_sum += (a[i] - p)
    ans[i-n+1] = first_sum
ans[-1] -= latter_sum

for i in range(2*n-1,n-1,-1):
    heapq.heappush(latter_que,a[i]*(-1))
    p = heapq.heappop(latter_que) * (-1)
    latter_sum += (a[i] - p)
    ans[i-n] -= latter_sum
print(max(ans))

Submission status: Accepted

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

maxL=[]
l=[]
for i in range(n):
  l.append(a[i])
s=sum(l)
maxL.append(s)
heapq.heapify(l)
for i in range(n,2*n):
  heapq.heappush(l,a[i])
  s+=a[i]
  s-=heapq.heappop(l)
  maxL.append(s)

minL=[]
l2=[]
for i in range(2*n,3*n):
  l2.append(-a[i])
s2=sum(l2)
minL.append(s2*(-1))
heapq.heapify(l2)
for i in range(2*n-1,n-1,-1):
  heapq.heappush(l2,-a[i])
  s2-=a[i]
  s2-=heapq.heappop(l2)
  minL.append(s2*(-1))

minL.reverse()
ans=[]
for i in range(n+1):
  ans.append(maxL[i]-minL[i])
print(max(ans))

Submission status: Accepted

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

X=A[:N]
Y=[-i for i in A[2*N:]]
heapq.heapify(X)
heapq.heapify(Y)
x=sum(X)
y=-sum(Y)
XMA=[0]*(N+1)
YMI=[0]*(N+1)
XMA[0]=x
YMI[N]=y
for i in range(N):
  heapq.heappush(X,A[N+i])
  s=heapq.heappop(X)
  x+=A[N+i]-s
  XMA[i+1]=x
  
  heapq.heappush(Y,-A[2*N-1-i])
  t=-heapq.heappop(Y)
  y+=A[2*N-1-i]-t
  YMI[N-i-1]=y
  
ANS=[0]*(N+1)
for i in range(N+1):
  ANS[i]=XMA[i]-YMI[i]
print(max(ANS))

Submission status: Accepted

Solution code:
import heapq

n = int(input())
A = list(map(int, input().split()))
Left_top = A[:n]
Right_bottom = [-i for i in A[-n:]]
L = [0]*(n+1)
R = [0]*(n+1)
L[0] = sum(Left_top)
R[-1] = sum(Right_bottom)
heapq.heapify(Left_top)
heapq.heapify(Right_bottom)
for i in range(n, 2*n):
  L[i-n+1] = L[i-n] - heapq.heappushpop(Left_top, A[i]) + A[i]
  R[2*n-i-1] = R[2*n-i] - heapq.heappushpop(Right_bottom, -A[-(i+1)]) - A[-(i+1)]
ans = -float("inf")
for i in range(n+1):
  ans = max(ans, L[i] + R[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq
n = int(input())
a = list(map(int, input().split()))
p = [0] * (n + 1)
hq = a[:n]
heapq.heapify(hq)
for i in range(n, 2 * n):
    heapq.heappush(hq, a[i])
    p[i + 1 - n] = heapq.heappop(hq) + p[i - n]
q = [0] * (n + 1)
hq = list(map(lambda x: -x, a[2 * n:]))
heapq.heapify(hq)
for i in range(2 * n, n, -1):
    heapq.heappush(hq, -a[i - 1])
    q[i - 1 - n] = -heapq.heappop(hq) + q[i - n]
s = sum(a[:n])
t = sum(a[n:])
ans = -float('inf')
for i in range(n + 1):
    ans = max(ans, s - t + q[i] - p[i])
    s += a[n + i]
    t -= a[n + i]
print(ans)

Submission status: Accepted

Solution code:
import heapq
n=int(input())
l=list(map(int,input().split()))
q=[]
for i in range(n):
    heapq.heappush(q,l[i])
a1=[0]*(n+1)
a1[0]=sum(l[:n])
for i in range(n):
    p=heapq.heappop(q)
    a1[i+1]=a1[i]-p+max(p,l[i+n])
    heapq.heappush(q,max(p,l[i+n]))
#print(a1)
q=[]
l.reverse()
for i in range(n):
    heapq.heappush(q,-l[i])
a1.reverse()
a1[0]-=sum(l[:n])
z=sum(l[:n])
for i in range(n):
    p=heapq.heappop(q)
    z=z+p+min(-p,l[i+n])
    a1[i+1]-=z
    heapq.heappush(q,max(p,-l[i+n]))
print(max(a1))

Submission status: Accepted

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

read = sys.stdin.read

N, *a = map(int, read().split())

a1 = a[:N]
a2 = a[N:-N]
a3 = a[-N:]

left = sum(a1)
right = sum(a3)

heapify(a1)
a3 = [-i for i in a3]
heapify(a3)

b = [0] * (N + 1)
b[0] = left
for n, i in enumerate(a2, 1):
    if a1[0] < i:
        j = heappop(a1)
        left = left - j + i
        heappush(a1, i)
    b[n] = left

c = [0] * (N + 1)
c[0] = right
for n, i in enumerate(a2[::-1], 1):
    if i < -a3[0]:
        j = -heappop(a3)
        right = right - j + i
        heappush(a3, -i)
    c[n] = right
c = c[::-1]

answer = max(i - j for i, j in zip(b, c))
print(answer)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N = int(input())
A = [int(a) for a in input().split()]
dpx = [0]*(N+1)
dpy = [0]*(N+1)
dpx[0] = sum(A[:N])
dpy[-1] = sum(A[2*N:])
X = []
Y = []
for i in range(N):
  heappush(X,A[i])

for i in range(N):
  heappush(Y,-A[3*N-1-i])

for i in range(N):
  a = heappop(X)
  b = A[N+i]
  if b>a:
    heappush(X,b)
    dpx[i+1] = dpx[i]+b-a
  else:
    heappush(X,a)
    dpx[i+1] = dpx[i]
  
  c = -heappop(Y)
  d = A[2*N-1-i]
  if d<c:
    heappush(Y,-d)
    dpy[N-1-i] = dpy[N-i]+d-c
  else:
    heappush(Y,-c)
    dpy[N-1-i] = dpy[N-i]

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop

N, *A = map(int, open(0).read().split())

L, C, R = A[:N], A[N:2 * N], A[2 * N:]

F = [sum(L)]
heapify(L)
for c in C:
    F.append(F[-1] + c - heappushpop(L, c))

R = [-r for r in R]
B = [sum(R)]
heapify(R)
for c in reversed(C):
    B.append(B[-1] - c - heappushpop(R, -c))

print(max(f + b for f, b in zip(F, reversed(B))))

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop
import sys
sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * (N+1)
    C = [0] * (N+1)
    H = [a for a in A[:N]]
    heapify(H)
    B[0] = sum(A[:N])
    for i in range(N):
        x = heappushpop(H, A[N+i])
        B[i+1] = B[i] + A[N+i] - x
    H = [-a for a in A[2*N:]]
    heapify(H)
    C[0] = sum(A[2*N:])
    for i in range(N):
        x = -heappushpop(H, -A[2*N-i-1])
        C[i+1] = C[i] + A[2*N-i-1] - x
    print(max(b-c for b,c in zip(B, C[::-1])))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq

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

N = int(input())
d = list(map(int, input().split()))
d_rev = d[::-1]

d1 = d[:N]
heapq.heapify(d1)
d2 = [-i for i in d_rev[:N]]
heapq.heapify(d2)
sum_d1 = sum(d1)
sum_d2 = sum(d2)

sum_d1_arr = [sum_d1]
sum_d2_arr = [sum_d2]

for k in range(N, 2 * N):
    c = sum_d1_arr[-1]
    c += d[k]
    n = heapq.heappushpop(d1, d[k])
    c -= n
    sum_d1_arr.append(c)

    e = sum_d2_arr[-1]
    e += -d_rev[k]
    n = heapq.heappushpop(d2, -1 * d_rev[k])
    e -= n
    sum_d2_arr.append(e)

print(max(v+w for v, w in zip(sum_d1_arr, sum_d2_arr[::-1])))

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop
 
N = int(input())
a = list(map(int, input().split()))
 
a_list_1 = []
a_list_2 = []
for i in a[0:N]:
    heappush(a_list_1, i)
for i in list(reversed(a))[0:N]:
    heappush(a_list_2, -i)
 
sum_1 = sum(a_list_1)
sum_2 = sum(a_list_2)
sum_arr_1 = [0] * (N + 1)
sum_arr_1[0] = sum_1
sum_arr_2 = [0] * (N + 1)
sum_arr_2[-1] = sum_2
for k in range(N, 2 * N):
    l = heappushpop(a_list_1, a[k])
    sum_1 += a[k] - l
    sum_arr_1[k - N + 1] = sum_1
 
for k in reversed(range(N, 2 * N)):
    l = heappushpop(a_list_2, -a[k])
    sum_2 += -a[k] - l
    sum_arr_2[k - N] = sum_2
 
max_score = float('-inf')
for s1, s2 in zip(sum_arr_1, sum_arr_2):
    score = s1 + s2
    if score > max_score:
        max_score = score
 
print(max_score)

Submission status: Accepted

Solution code:
def main():
    from heapq import heappush, heappushpop

    n = int(input())
    *a, = map(int, input().split())  # [0,n),[n,2n),[2n,3n)

    to_rm = [0] * (n * 3)

    h = []
    for x in a[:n]:
        heappush(h, x)

    mid = tuple(enumerate(a[n:n * 2], n))

    t = 0
    for i, x in mid:
        mi = heappushpop(h, x)
        t += mi
        to_rm[i] = -t

    h = []
    for x in a[n * 2:n * 3]:
        heappush(h, -x)

    t = 0
    for i, x in reversed(mid):
        ma = -heappushpop(h, -x)
        t += ma
        to_rm[i - 1] += t

    tot = sum(a)
    ret = -10 ** 30
    s = sum(a[:n - 1])
    for tail in range(n - 1, n * 2):
        s += a[tail]
        ret = max(ret, s - (tot - s) + to_rm[tail])  # [0,tail]=前半
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
#print(a)
s=a[:n]
m=a[n:2*n]
f=a[2*n:]

ssum=sum(s)
fsum=sum(f)
#print(fsum)
import heapq

heapq.heapify(s)
ms=[0]*n
mf=[0]*n

for i in range(n):
    heapq.heappush(s,m[i])
    mn=heapq.heappop(s)
    ms[i]=mn
#print(ms)
for i in range(n):
    f[i]*=-1
heapq.heapify(f)
#print(f)
for i in range(n-1,-1,-1):
    heapq.heappush(f,-m[i])
    mx=-heapq.heappop(f)
    mf[i]=mx
#print(mf)
#print(m)
srui=[0]*(n+1)
srui[0]=ssum
for i in range(n):
    srui[i+1]=srui[i]-ms[i]+m[i]
#print(srui)
frui=[0]*(n+1)
frui[-1]=fsum
#print(frui)
for i in range(n,0,-1):
    frui[i-1]=frui[i]-mf[i-1]+m[i-1]
#print(srui)
#print(frui)
ans=-float("inf")
for i in range(n+1):
    ans=max(ans,srui[i]-frui[i])
print(ans)

Submission status: Accepted

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