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 heapq

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

    left = [0] * (3 * N)
    right = [0] * (3 * N)

    tmp = 0
    q = []
    for i in range(N):
        heapq.heappush(q, a[i])
        tmp += a[i]
    left[N-1] = tmp
    for i in range(N, 2*N):
        heapq.heappush(q, a[i])
        left[i] = left[i-1] + a[i] - heapq.heappop(q)
    
    tmp = 0
    q = []
    for i in range(N*3-1, N*2-1, -1):
        heapq.heappush(q, -a[i])
        tmp += a[i]
    right[2*N] = tmp
    for i in range(2*N-1, N-1, -1):
        heapq.heappush(q, -a[i])
        right[i] = right[i+1] + a[i] + heapq.heappop(q)
    
    ans = left[N-1] - right[N]
    for i in range(N, 2*N):
        ans = max(ans, left[i]-right[i+1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

s1 = [0] * 3*n
pq = []
s = 0
for i in range(3*n):
    if len(pq) < n:
        s += a[i]
        heappush(pq, a[i])
        if len(pq) == n:
            s1[i] = s
    else:
        s += a[i]
        heappush(pq, a[i])
        s -= heappop(pq)
        s1[i] = s


s2 = [0] * 3*n
pq = []
s = 0
for i in reversed(range(3*n)):
    if len(pq) < n:
        s += a[i]
        heappush(pq, -a[i])
        if len(pq) == n:
            s2[i] = s
    else:
        s += a[i]
        heappush(pq, -a[i])
        s -= -heappop(pq)
        s2[i] = s

ans = - 10**15
for i in range(n-1, 2*n):
    ans = max(ans, s1[i] - s2[i+1])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, y = LI()
    a = [1, 3, 5, 7, 8, 10, 12]
    b = [4, 6, 9, 11]
    c = [2]
    if x in a and y in a:
        print("Yes")
        return
    if x in b and y in b:
        print("Yes")
        return
    if x in c and y in c:
        print("Yes")
        return
    print("No")
    return

#B
def B():
    h, w = LI()
    print("#" * (w + 2))
    for _ in range(h):
        a = ["#"]
        for s in S():
            a.append(s)
        a.append("#")
        print("".join(a))
    print("#" * (w + 2))
    return

#C
def C():
    h, w = LI()
    ans = inf
    for i in range(1, h):
        ans = min(ans, max(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)) - min(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)))
        ans = min(ans, max(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w) - min(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w))
    h, w = w, h
    for i in range(1, h):
        ans = min(ans, max(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)) - min(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)))
        ans = min(ans, max(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w) - min(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w))
    print(ans)
    return

# D
# 解説AC
# ある点kにおいて2つに分けてa'の
# 前後半の要素を考える
# シンプルにわからなかった 
def D():
    n = II()
    a = LI()
    first_half_list = []
    final_half_list = []
    first_half_sum = deque([0])
    final_half_sum = deque([0])
    ans = -inf
    for i in range(n):
        heappush(first_half_list, a[i])
        first_half_sum[0] += a[i]
        heappush(final_half_list, -a[-i - 1])
        final_half_sum[0] -= a[-i - 1]
    for i in range(1, n + 1):
        q = heappop(first_half_list)
        heappush(first_half_list, max(q, a[i + n - 1]))
        first_half_sum.append(first_half_sum[-1] - q + max(q, a[i + n- 1]))
        q = heappop(final_half_list)
        heappush(final_half_list, max(q, -a[-n - i]))
        final_half_sum.appendleft(final_half_sum[0] - q + max(q, -a[-n - i]))
    for i in range(n + 1):
        ans = max(ans, first_half_sum[i] + final_half_sum[i])
    print(ans)
    return


#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
import heapq

n=int(input())
arr=list(map(int,input().split()))
q1=[]
tmp=0
for val in arr[:n]:
  heapq.heappush(q1,val)
  tmp+=val
sum1=[tmp]
for val in arr[n:2*n]:
  tmp=heapq.heappop(q1)
  if val>tmp:
    heapq.heappush(q1,val)
    sum1.append(sum1[-1]+(val-tmp))
  else:
    heapq.heappush(q1,tmp)
    sum1.append(sum1[-1])
q2=[]
tmp=0
for val in arr[2*n:]:
  heapq.heappush(q2,-val)
  tmp+=val
sum2=[tmp]
for val in arr[2*n-1:n-1:-1]:
  tmp=-heapq.heappop(q2)
  if val<tmp:
    heapq.heappush(q2,-val)
    sum2.append(sum2[-1]+(val-tmp))
  else:
    heapq.heappush(q2,-tmp)
    sum2.append(sum2[-1])
sum2=sum2[::-1]
ans=-10**18
for i in range(n+1):
  tmp=sum1[i]-sum2[i]
  ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import deque

import heapq


class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)

    def push(self, value):
        heapq.heappush(self.heap, -value)

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


class MinHeap(object):
    def __init__(self, x):
        self.heap = [e for e in x]
        heapq.heapify(self.heap)

    def push(self, value):
        heapq.heappush(self.heap, value)

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


def solve(N: int, a: "List[int]"):

    mae = MinHeap(a[:N])
    mae_tot = [sum(a[:N])]
    for curr in range(N, 2*N):
        mae.push(a[curr])
        mmin = mae.pop()
        mae_tot.append(mae_tot[-1]+a[curr]-mmin)

    ushiro = MaxHeap(a[2*N:])
    ushiro_tot = [sum(a[2*N:])]
    for curr in range(2*N-1, N-1, -1):
        ushiro.push(a[curr])
        umax = ushiro.pop()
        ushiro_tot.append(ushiro_tot[-1]+a[curr]-umax)

    m = -INF
    for mt, ut in zip(mae_tot, reversed(ushiro_tot)):
        m = max(m, mt-ut)
    print(m)

    return


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:
from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.readline

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

dpl = [0] * (N * 3)
dpr = [0] * (N * 3)
l = [a[i] for i in range(N)]
r = [-a[i] for i in range(2*N, 3*N)]
heapify(l)
heapify(r)

dpl[N-1] = sum(l)
for i in range(N, 2*N) :
    heappush(l, a[i])
    m = heappop(l)
    dpl[i] = dpl[i-1] + a[i] - m
    
dpr[2*N] = -sum(r)
for i in range(2*N-1, N-1, -1) :
    heappush(r, -a[i])
    M = heappop(r)
    dpr[i] = dpr[i+1] + a[i] + M

M = -float('inf')
for i in range(N-1, 2*N) :
    M = max(M, dpl[i]-dpr[i+1])
print(M)

Submission status: Accepted

Solution code:
import heapq

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

leftQue = []
rightQue = []

leftSum = 0
rightSum = 0

for i in range(N):
    heapq.heappush(leftQue, A[i])
    leftSum += A[i]

    heapq.heappush(rightQue, -A[-1 - i])
    rightSum -= A[-1 - i]

left = [-float('inf') for _ in range(3 * N)]
right = [-float('inf') for _ in range(3 * N)]

left[N - 1] = leftSum

for middle in range(N, 2 * N):
    leftSum += A[middle]
    leftSum -= heapq.heappushpop(leftQue, A[middle])
    left[middle] = leftSum

right[2 * N - 1] = rightSum
for middle in range(2 * N - 1, N - 1, -1):
    rightSum -= A[middle]
    rightSum -= heapq.heappushpop(rightQue, -A[middle])
    right[middle - 1] = rightSum

ans = -float('inf')
for l, r in zip(left, right):
    ans = max(ans, l + r)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
n=int(input())
a=list(map(int,input().split()))
ans=-float("inf")
l=a[:n]
heapify(l)
t=sum(a[:n])
ls=[t]
for i in range(n,2*n):
    t+=a[i]
    heappush(l,a[i])
    t-=heappop(l)
    ls.append(t)
r=[-i for i in a[2*n:]]
heapify(r)
t=sum(a[2*n:])
rs=[t]
for i in range(2*n-1,n-1,-1):
    t+=a[i]
    heappush(r,-a[i])
    t+=heappop(r)
    rs.append(t)
for i in range(n+1):
    ans=max(ans,ls[i]-rs[-i-1])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int,input().split())

from heapq import *

B1 = []
hpu = heappush
hpp = heappushpop
for a in A[:N]:
    hpu(B1,a)
S1 = [sum(B1)]
for a in A[N:2*N]:
    S1.append(S1[-1]+ a - hpp(B1,a))
B2 = []
for a in A[2*N:]:
    hpu(B2,-a)
S2 = [-sum(B2)]
for a in A[N:2*N][::-1]:
    S2.append(S2[-1] + a + hpp(B2,-a))

print(max(S1[i]-S2[-i-1] for i in range(N+1)))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

inf = float('inf')

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

# sum_max[k] : [0,k)のうちN個までの総和の最大値
# sum_min[k] : (3N-1-k,3N-1]のうちN個までの総和の最小値
sum_max = [0]*(3*N+1)
sum_min = [0]*(3*N+1)

def init_max():
    res = 0
    hq = []
    for i, a in enumerate(A):
        if len(hq) < N:
            heappush(hq,a)
            res += a
        else:
            if hq[0] < a:
                res -= heappop(hq)
                heappush(hq,a)
                res += a
        sum_max[i+1] = res

def init_min():
    res = 0
    hq = []
    for i, a in enumerate(A[::-1]):
        if len(hq) < N:
            heappush(hq,-a)
            res += a
        else:
            if -hq[0] > a:
                res -= -heappop(hq) 
                heappush(hq,-a)
                res += a
        sum_min[i+1] = res

init_max()
init_min()

ans = -inf

for k in range(N,2*N+1):
    res = sum_max[k] - sum_min[3*N-k]
    ans = max(ans, res)

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
x,y = LI()
f = [0,1,2,1,3,1,3,1,1,3,1,3,1]
if f[x] == f[y]:
    print("Yes")
else:
    print("No")
"""
#B
"""
h,w = LI()
a = SR(h)
print("#"*(w+2))
for i in range(h):
    print("#",end = "")
    for j in a[i]:
        print(j,end = "")
    print("#")
print("#"*(w+2))
"""
#C
"""
h,w = LI()
ans = float("inf")
x = w//2
y = h//2
if not w%2:
    for i in range(1,h):
        if (h-i)%2 == 0:
            ans = min(ans,abs(w*i-w*(h-i)//2))
        ans = min(ans,abs(w*i-x*(h-i)))
else:
    for i in range(1,h):
        if (h-i)%2 == 0:
            ans = min(ans,abs(w*i-w*(h-i)//2))
        if w*i < x*(h-i):
            ans = min(ans,abs(w*i-(x+1)*(h-i)))
        elif w*i < (x+1)*(h-i):
            ans = min(ans,h-i)
        else:
            ans = min(ans,abs(w*i-x*(h-i)))
if not h%2:
    for i in range(1,w):
        if (w-i)%2 == 0:
            ans = min(ans,abs(h*i-h*(w-i)//2))
        ans = min(ans,abs(h*i-y*(w-i)))
else:
    for i in range(1,w):
        if (w-i)%2 == 0:
            ans = min(ans,abs(h*i-h*(w-i)//2))
        if h*i < y*(w-i):
            ans = min(ans,abs(h*i-(y+1)*(w-i)))
        elif h*i < (y+1)*(w-i):
            ans = min(ans,w-i)
        else:
            ans = min(ans,abs(h*i-y*(w-i)))
print(ans)
"""

#D
n = I()
a = LI()
q = []
s = 0
for i in range(n):
    heappush(q,a[i])
    s += a[i]
fl = [s]

for i in range(n,2*n):
    heappush(q,a[i])
    s -= heappop(q)
    s += a[i]
    fl.append(s)
q = []
s = 0
for i in range(2*n,3*n)[::-1]:
    heappush(q,-a[i])
    s += a[i]
fr = [s]

for i in range(n,2*n)[::-1]:
    heappush(q,-a[i])
    s += heappop(q)
    s += a[i]
    fr.append(s)
print(max(list(map(lambda x: x[0]-x[1], zip(fl,fr[::-1])))))
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
import heapq

def main():
    num = int(input())
    data = list(map(int, input().split()))

    left_heap = []
    left_sum = 0
    for i in range(num):
        left_sum += data[i]
        heapq.heappush(left_heap, data[i])

    dp_left = [0 for i in range(num + 1)]
    dp_left[0] = left_sum

    for i in range(num):
        now_num = data[num + i]
        pop_data = heapq.heappushpop(left_heap, now_num)
        left_sum += now_num - pop_data
        dp_left[i + 1] = left_sum

    right_heap = []
    right_sum = 0
    for i in range(num):
        right_sum += data[3 * num - 1 - i]
        heapq.heappush(right_heap, -data[3 * num - 1 - i])

    dp_right = [0 for i in range(num + 1)]
    dp_right[0] = right_sum

    for i in range(num):
        now_num = data[2 * num - 1 - i]
        pop_data = heapq.heappushpop(right_heap, -now_num)
        right_sum += now_num + pop_data
        dp_right[i + 1] = right_sum
    dp_right = dp_right[::-1]

    ans = dp_left[-1] - dp_right[-1]
    for i in range(num):
        ans = max(ans, dp_left[i] - dp_right[i])

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n=int(input())
a=[int(i) for i in input().split()]
 
heap_left=[]
left=0
for i in range(n):
    left+=a[i]
    heapq.heappush(heap_left,a[i])
 
lst_left=[left]
for i in range(n,2*n):
    tmp=heapq.heappushpop(heap_left,a[i])
    left=left-tmp+a[i]
    lst_left+=[left]
 
heap_right=[]
right=0
for i in range(2*n,3*n):
    right+=a[i]
    heapq.heappush(heap_right,-a[i])
 
lst_right=[right]
for i in range(2*n-1,n-1,-1):
    tmp=heapq.heappushpop(heap_right,-a[i])
    right=right-(-tmp)+a[i]
    lst_right+=[right]
 

ans=-10**100
for i in range(n+1):
    ans=max(ans,lst_left[i]-lst_right[-(i+1)])
 
print (ans)

Submission status: Accepted

Solution code:
import heapq

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

push = heapq.heappush
pop = heapq.heappop
lq = []
l = [0] * (N + 1)
for i in range(N):
  push(lq, a[i])
  l[0] += a[i]
for i in range(N):
  l[i + 1] = l[i]
  x = pop(lq)
  if a[N + i] > x:
    l[i + 1] += a[N + i] - x
    push(lq, a[N + i])
  else:
    push(lq, x)

rq = []
r = [0] * (N + 1)
for i in range(N):
  push(rq, -a[-1 -i])
  r[-1] += a[-1 -i]
for i in range(N):
  r[-2 -i] = r[-1 -i]
  x = pop(rq)
  if a[-N-1 -i] < -x:
    r[-2 -i] -= -x -a[-N-1 -i]
    push(rq, -a[-N-1 -i])
  else:
    push(rq, x)

ans = l[0] - r[0]
for i in range(1, 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()))

f = A[:N]
heapq.heapify(f)
S = sum(f)
fs = [S]
for i in range(N):
    a = A[N+i]
    S += a
    heapq.heappush(f,a)
    a = heapq.heappop(f)
    S -= a
    fs.append(S)

l = [-a for a in A[2*N:]]
heapq.heapify(l)
S = sum(l)
ls = [S]
for i in range(N):
    a = -A[2*N-i-1]
    S += a
    heapq.heappush(l,a)
    a = heapq.heappop(l)
    S -= a
    ls.append(S)

ans = -10**15
for i in range(N+1):
    ans = max(ans,fs[i]+ls[N-i])
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
n=int(input()); a=[int(_) for _ in input().split()]
fh=[]; lh=[]
for i in range(n):
    heappush(fh, a[i])
    heappush(lh, -1*a[-i-1])
f=[sum(fh)]; l=[-1*sum(lh)]
for i in range(n,2*n):
    heappush(fh, a[i]); f.append(f[-1]+a[i]-heappop(fh))
    heappush(lh, -1*a[-i-1]); l.append(l[-1]+a[-i-1]+heappop(lh))
ans=-10**15
for i,j in zip(f,l[::-1]):ans=max(ans, i-j)
print(ans)

Submission status: Accepted

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

heap_left = []
left = 0
for i in range(N):
    left += a[i]
    heapq.heappush(heap_left, a[i])

lst_left = [left]
for i in range(N, 2 * N):
    tmp = heapq.heappushpop(heap_left, a[i])
    left = left - tmp + a[i]
    lst_left += [left]

heap_right = []
right = 0
for i in range(2 * N, 3 * N):
    right += a[i]
    heapq.heappush(heap_right, -1 * a[i])

lst_right = [right]
for i in range(2 * N -1, N-1, -1):
    tmp = heapq.heappushpop(heap_right, -1 * a[i])
    right = right - (-1 * tmp) + a[i]
    lst_right += [right]

# print (lst_left)
# print (lst_right)
ans = -1 * 10 ** 20
for i in range(N+1):
    # print (lst_left[i], lst_right[-(i+1)])
    ans = max(ans, lst_left[i]-lst_right[-(i+1)])

print (ans)

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N = ii()
As = list(mi())
minusAs = [-a for a in As]

#下準備。左側0～N-1, 右側2N～3N-1のN要素のheapqを作っておく
#leftQは大きいのを残したい（最小値を取り除く）、rightQは小さいのを残したい（最大値を取り除く）ので、leftQはそのままの配列、rightQは符号反転したminusAsを使用する
leftQ = As[:N]
rightQ = minusAs[-N:]
heapq.heapify(leftQ)
heapq.heapify(rightQ)

#この配列のidxは、右端（左端）から何番目(0スタート)の区切りを採用するかを表す。あとで突き合わせる時に添字でバグらせないよう注意
leftsum = [0]*(N+1)
rightsum = [0]*(N+1) #どうせ最後に引くんだから、マイナスのまま入れちゃう
#つまり、最後に最小値を求める時は、逆に「最も大きい＝マイナス幅が小さいsum」を求めることになるので注意

#初期値はもう入れておく
leftsum[0] = sum(leftQ)
rightsum[0] = sum(rightQ)

for i in range(N, 2*N): #左端（右端）から最低N個（N-1まで）は済んでいる。残りはNまで～2N-1まで)
  #iがNのとき、左側は[:N], 右側は[-N:]
  #iが2Nのとき、左側は[0:2N], 右側は[-2N:]
  if leftQ[0] < As[i]: #大きいのを残したいので、最小値のが小さければ入れ替える
    #入れ替える
    nowmin = heapq.heappop(leftQ)
    leftsum[i-N+1] = leftsum[i-N] - nowmin + As[i]
    heapq.heappush(leftQ,As[i])
  else: leftsum[i-N+1] = leftsum[i-N] #そうでなければ入れ替えない
  if rightQ[0] < minusAs[-1-i]: #小さいのを残したいので、マイナス幅が大きければ入れ替える
    nowmax = heapq.heappop(rightQ)
    rightsum[i-N+1] = rightsum[i-N] - nowmax + minusAs[-1-i]
    heapq.heappush(rightQ,minusAs[-1-i])
  else: rightsum[i-N+1] = rightsum[i-N] #そうでなければ入れ替えない

ans = -INF
for lsum, rsum in zip(leftsum, rightsum[::-1]):
#  print(ans, lsum, rsum)
  ans = max(ans, lsum+rsum)

print(ans)

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:
import heapq
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

A = np.array(A, dtype=int)

# 区切る場所を N -> 2N まで全探索
# 区切る場所より左は大きいやつを順に
# 区切る場所より右は小さいやつを順に取るのが最適
lefts = list(A[:N])
heapq.heapify(lefts)

L_sum = sum(lefts)
L_hist = [L_sum]
for div in range(N, 2 * N):
    if A[div] > lefts[0]:
        L_sum += A[div] - lefts[0]
        heapq.heapreplace(lefts, A[div])
    L_hist.append(L_sum)

rights = list(-A[N * 2:])
heapq.heapify(rights)
r_sum = -sum(rights)
r_hist = [r_sum]
for div in reversed(range(N, 2 * N)):
    if A[div] < -rights[0]:
        r_sum += A[div] - (-rights[0])
        heapq.heapreplace(rights, -A[div])
    r_hist.append(r_sum)
r_hist.reverse()

ans = -INF
for l, r in zip(L_hist, r_hist):
    ans = max(ans, l - r)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

B=A[:N]
S=sum(B)
heapq.heapify(B)

BS=[0]*(3*N)
BS[N]=S
for i in range(N,2*N):
    if B[0]<A[i]:
        x=heapq.heappop(B)
        S+=A[i]-x
        heapq.heappush(B,A[i])

    BS[i+1]=S
        
    
C=[-c for c in A[2*N:]]
S=-sum(C)
heapq.heapify(C)

CS=[0]*(3*N)
CS[2*N]=S

for i in range(2*N-1,N-1,-1):
    if -C[0]>A[i]:
        x=-heapq.heappop(C)
        S+=A[i]-x
        heapq.heappush(C,-A[i])

    CS[i]=S

ANS=-float("inf")
for i in range(N,2*N+1):
    ANS=max(ANS,BS[i]-CS[i])

print(ANS)

Submission status: Accepted

Solution code:
#from numpy import* #import numpy as np
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) #dijkstra #floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！


def main():
    n,*a=map(int,open(0).read().split())
    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
    print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1]))))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop,heapify
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    def rev(n):
        return -n
    N = I()
    A = LI()
    left_sum = [sum(A[:N])]  #left_sum[k]:=N+k個取って、小さいN個を選んだときの合計値
    left = A[:N]
    heapify(left)
    right_sum = [sum(A[2 * N:])]
    right=list(map(rev,A[2*N:]))
    heapify(right)
    for k in range(1, N + 1):
        heappush(left, A[N - 1 + k])
        poped = heappop(left)
        left_sum.append(left_sum[-1] + A[N - 1 + k] - poped)

        heappush(right, -A[-N - k])
        poped = -heappop(right)
        right_sum.append(right_sum[-1] + A[-N - k] - poped)
    ans = -inf
    for k in range(N + 1):
        ans = max(ans, left_sum[k] - right_sum[-k - 1])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N=int(input())
a=list(map(int,input().split()))
#print(a)
b=a[::-1]
A=a[:N]
#print(A)
AR=[A[0]]
for i in range(1,len(A)*2):
    AR.append(a[i]+AR[i-1])
#print("AR",AR)
AL=[]

heapq.heapify(A)
for i in range(N,N*2):
    heapq.heappush(A,a[i])
    AL.append(A[0])
    heapq.heappop(A)
#print(AL)
ALR=[AL[0]]
for i in range(1,len(AL)):
    ALR.append(ALR[i-1]+AL[i])
#print(ALR)
ANSA=[AR[N-1]]
for i in range(len(ALR)):
    ANSA.append(AR[N+i]-ALR[i])
#print(ANSA)

B=b[:N]
for i in range(len(B)):
    B[i]*=-1
#print("B",B)
BR=[B[0]]
for i in range(1,len(B)*2):
    BR.append(-b[i]+BR[i-1])
#print("BR",BR)
BL=[]
#print("B",B)
heapq.heapify(B)
for i in range(N,N*2):
    heapq.heappush(B,-b[i])
    BL.append(-B[0])
    heapq.heappop(B)
#print("BL",BL)
BLR=[BL[0]]
for i in range(1,len(BL)):
    BLR.append(BLR[i-1]+BL[i])
#print("BLR",BLR)
BNSA=[BR[N-1]]
for i in range(len(BLR)):
    BNSA.append(BR[N+i]+BLR[i])
#print(BNSA)
BNSA=BNSA[::-1]
#print(BNSA)
ANS=-10**20
for i in range(len(BNSA)):
    if (ANSA[i]+BNSA[i])>ANS:
        ANS=(ANSA[i]+BNSA[i])
print(ANS)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = a[:n]
m = a[n:2*n]
r = list(map(lambda x: -x, a[2*n:]))


import heapq
heapq.heapify(l)
heapq.heapify(r)
lremovesum = [0]
rremovesum = [0]


ruisekil = [sum(l)]
ruisekir = [sum(r)]
for i in range(n):
    ruisekil.append(ruisekil[-1] + m[i])
    ruisekir.append(ruisekir[-1] - m[-i - 1])
    # print(ruisekil,ruisekir)
ruisekir.reverse()

for i in range(n):
    heapq.heappush(l, m[i])
    lremovesum.append(lremovesum[-1] + heapq.heappop(l))
    heapq.heappush(r, -m[-i-1])
    rremovesum.append(rremovesum[-1] + heapq.heappop(r))
rremovesum.reverse()


# print(l,r)
# print(r)
# print(lremovesum)
# print(rremovesum)



ans = -10**20
for i in range(n + 1):
    # print(i, ruisekil[i],-lremovesum[i],+ruisekir[i],-rremovesum[i],ruisekil[i]-lremovesum[i]+ruisekir[i]-rremovesum[i])
    # print()
    ans = max(ans, ruisekil[i]-lremovesum[i]+ruisekir[i]-rremovesum[i])

print(ans)

Submission status: Accepted

Solution code:
import heapq
n=int(input())
A=[int(i) for i in input().split()]
AL=A[:n]
AR=[0]*n
for i in range(2*n,3*n):
  AR[i-2*n]-=A[i]
ALS,ARS=[0]*(n+1),[0]*(n+1)
ALS[0],ARS[0]=sum(AL),sum(AR)
heapq.heapify(AL)
heapq.heapify(AR)
for i in range(n):
  l,r=A[n+i],-A[2*n-i-1]
  heapq.heappush(AL,l)
  ALS[i+1]=ALS[i]+l-heapq.heappop(AL)
  heapq.heappush(AR,r)
  ARS[i+1]=ARS[i]+r-heapq.heappop(AR)
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]+ARS[n-i])
print(ans)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = list(map(int, input().split()))
 
L = A[:N]
heapq.heapify(L) 

sum_L = [0] * (N+1)
sum_L[0] = sum(L)

for i in range(N):
    min_L = heapq.heappushpop(L, A[N+i])
    sum_L[i+1] = sum_L[i] + A[N+i] - min_L
    #print(L, i, A[N+i], min_L, sum_L)

R = A[N*2:]
rev_R = list(map(lambda x: -x, R))
heapq.heapify(rev_R) 

sum_R = [0] * (N+1)
sum_R[N] = sum(R)

for i in range(N-1, -1, -1):
    max_R = -heapq.heappushpop(rev_R, -A[N+i])
    sum_R[i] = sum_R[i+1] + A[N+i] - max_R
    #print(rev_R, i, A[N+i], max_R, sum_R)

ans = -10**14

for i in range(N+1):
    ans = max(ans, sum_L[i] - sum_R[i])

print(ans)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = list(map(int, input().split()))
 
L = A[:N]
heapq.heapify(L) 

sum_L = [0] * (N+1)
sum_L[0] = sum(L)

for i in range(N):
    min_L = heapq.heappushpop(L, A[N+i])
    sum_L[i+1] = sum_L[i] + A[N+i] - min_L
    #print(L, i, A[N+i], min_L, sum_L)

R = A[N*2:]
rev_R = list(map(lambda x: x*(-1), R))
heapq.heapify(rev_R) 

sum_R = [0] * (N+1)
sum_R[N] = sum(R)

for i in range(N-1, -1, -1):
    max_R = heapq.heappushpop( rev_R, A[N+i]*(-1) ) * (-1)
    sum_R[i] = sum_R[i+1] + A[N+i] - max_R
    # print(rev_R, i, A[N+i], max_R, sum_R)

ans = -10**14

for i in range(N+1):
    ans = max(ans, sum_L[i] - sum_R[i])

print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
li = [ int(it) for it in input().split() ]

X = li[:N]
sX = [0]*(N+1)
sX[0] = sum(X)
heapq.heapify(X) 
for i in range(N):
  pu = li[N+i]
  heapq.heappush(X,pu)
  po = heapq.heappop(X)
  sX[1+i] = sX[i] + pu - po

li = [ -li[3*N-1-i] for i in range(3*N)] 
Y = li[:N]
sY = [0]*(N+1)
sY[0] = sum(Y)
heapq.heapify(Y) 
for i in range(N):
  pu = li[N+i]
  heapq.heappush(Y,pu)
  po = heapq.heappop(Y)
  sY[1+i] = sY[i] + pu - po

  
s = -100000000000000000000000
for i in range(N+1):
  s = max( sX[i] + sY[N-i] ,s )
print  (s)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
*A, = map(int,input().split())
q = []
for a in A[:N]:
    heapq.heappush(q,a)
S1 = [sum(q)]
for a in A[N:N*2]:
    if a>q[0]:
        S1.append(S1[-1] + a - q[0])
        heapq.heapreplace(q,a)
    else:
        S1.append(S1[-1])
q = []
for a in A[2*N:]:
    heapq.heappush(q,-a)
S2 = [sum(q)]
for a in A[N:N*2][::-1]:
    if a<-q[0]:
        S2.append(S2[-1] - a - q[0])
        heapq.heapreplace(q,-a)
    else:
        S2.append(S2[-1])
S2 = S2[::-1]
print(max(map(sum,zip(S1,S2))))

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);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:
def f(x):
    y=x[:n];heapify(y);z=sum(y);yield z
    for i in x[n:n*2]:z+=i-heappushpop(y,i);yield z
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f([-i for i in a[n:][::-1]]),list(f(a))[::-1]))))

Submission status: Accepted

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

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]))))