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 .

Solution (Python):
import heapq

N = int(input())
a    = [ int(x) for x in input().split() ]
arev = [ -x for x in a[::-1] ]

Hl = a[:N]
heapq.heapify(Hl) 
suml = sum(Hl)
sumL = [suml]

Hr = arev[:N]
heapq.heapify(Hr) 
sumr = sum(Hr)
sumR = [sumr]

for i in range(N):
    x = heapq.heappushpop(Hl, a[N+i])
    
    suml += -x + a[N+i]
    sumL.append(suml)
    
for i in range(N):
    x = heapq.heappushpop(Hr, arev[N+i])
    
    sumr += -x + arev[N+i]
    sumR.append(sumr)


dif = [ i+j for i, j in zip(sumL, sumR[::-1])]  
print(max(dif))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
a = LIST()

h = sorted(a[:N])
sum_h = sum(h)
h2 = sorted([-x for x in a[2*N:]])
sum_h2 = sum(h2)
max_h = [0]*(N+1)
max_h[0] = sum_h
min_h2 = [INF]*(N+1)
min_h2[-1] = sum_h2

for i in range(N, 2*N):
	if h[0] < a[i]:
		sum_h -= heapq.heappop(h)
		sum_h += a[i]
		heapq.heappush(h, a[i])
	max_h[i-N+1] = sum_h


for i in range(2*N-1, N-1, -1):
	if h2[0] < -a[i]:  
		sum_h2 -= heapq.heappop(h2)
		sum_h2 += -a[i]
		heapq.heappush(h2, -a[i])
	min_h2[i-N] = sum_h2


ans = -INF
for i in range(N+1):
	ans = max(ans, max_h[i]+min_h2[i])
print(ans)

Solution (Python):
import heapq
import sys

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    rA = list(map(lambda x: -1 * x, A[::-1]))

    MM = A[:N]
    mm = rA[:N]
    heapq.heapify(MM)
    heapq.heapify(mm)
    M = [sum(MM)]
    m = [sum(mm)]

    for i in range(N, 2*N):
        pM = heapq.heappushpop(MM, A[i])
        pm = heapq.heappushpop(mm, rA[i])
        M.append(M[-1] - pM + A[i])
        m.append(m[-1] - pm + rA[i])

    Dm = -10**14
    for i, j in zip(M, m[::-1]):
        if i + j > Dm:
            Dm = i + j

    print(Dm)


main()

Solution (Python):
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)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
dp1,dp2=[0]*(N+1),[0]*(N+1)
from heapq import heappop,heappush
q1,q2=[],[]
for i in range(2*N):
    heappush(q1,A[i])
    heappush(q2,-A[-i-1])
    if i<N:
        dp1[0]+=A[i]
        dp2[-1]+=A[-i-1]
    else:
        dp1[i-N+1]=dp1[i-N]+A[i]-heappop(q1)
        dp2[N-i-2]=dp2[N-i-1]+A[-i-1]+heappop(q2)
print(max([dp1[i]-dp2[i] for i in range(N+1)]))

Solution (Python):
def main():
    from heapq import heappushpop, heapify
    N = int(input())
    a = [int(val) for val in input().split()]
    first_half_sums = [0]*(N+1)
    second_half_sums = [0]*(N+1)

    first_half = a[:N]
    heapify(first_half)
    first_sum = sum(first_half)
    first_half_sums[0] = first_sum

    second_half = [-val for val in a[2*N:]]
    heapify(second_half)
    second_sum = sum(second_half)
    second_half_sums[0] = -second_sum

    for i in range(N):
        first_sum += a[i + N]
        first_sum -= heappushpop(first_half, a[i + N])
        first_half_sums[i + 1] = first_sum

        second_sum += -1 * a[2*N - (i+1)]
        second_sum -= heappushpop(second_half, -1 * a[2*N - (i+1)])
        second_half_sums[i+1] = -second_sum

    ans = - (1 << 60)
    for i in range(N+1):
        ans = max(ans, first_half_sums[i] - second_half_sums[N-i])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
f=a[0:n]
l=a[2*n:3*n]
for i in range(n):
    l[i]*=-1


mx=[0]*(n+1)
mn=[0]*(n+1)

import heapq

heapq.heapify(f)
heapq.heapify(l)

mx[0]=sum(f)
for i in range(n):
    x=f[0]
    if x<a[n+i]:
        mx[i+1]=mx[i]-x+a[n+i]
        heapq.heappop(f)
        heapq.heappush(f,a[n+i])
    else:
        mx[i+1]=mx[i]
mn[n]=sum(l)*-1

for i in range(n-1,-1,-1):
    x=l[0]
    if x<a[n+i]*-1:
        mn[i]=mn[i+1]+x+a[n+i]
        heapq.heappop(l)
        heapq.heappush(l,a[n+i]*-1)
    else:
        mn[i]=mn[i+1]

buf=float('inf')
buf*=-1
for i in range(n+1):
    buf=max(buf,mx[i]-mn[i])
    
print(buf)

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

    a1 = a[:N]
    heapq.heapify(a1)
    a2 = a[N:N*2]
    a3 = a[N*2:N*3]
    a3 = list(map(lambda x:x*(-1),a3))
    heapq.heapify(a3)
    s1 = [0 for _ in range(N+1)]
    s1[0] = sum(a1)
    for i in range(N):
        s1[i+1] = a2[i] - heapq.heappushpop(a1,a2[i]) + s1[i]
    s3 = [0 for _ in range(N+1)]
    s3[N] = sum(a3)
    for i in range(N,0,-1):
        s3[i-1] = -heapq.heappushpop(a3,a2[i-1]*(-1)) - a2[i-1] + s3[i]
    for i in range(N+1):
        s1[i] += s3[i]
    print(max(s1))   
resolve()

Solution (Python):
import heapq

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

pre = A[:N]
epi = A[2*N:]
epi = [epi[j]*(-1) for j in range(N)]
t_pre = sum(pre)
t_epi = sum(epi)

heapq.heapify(pre)
heapq.heapify(epi)

pre_sum = []
epi_sum = []

pre_sum.append(t_pre)

for i in range(N):
	t_push = A[N+i]
	heapq.heappush(pre, t_push)
	t_pop = heapq.heappop(pre)
	t_pre = t_pre + t_push - t_pop
	pre_sum.append(t_pre)


epi_sum.append(t_epi)

for i in range(N):
	t_push = A[-(N+i+1)] * (-1)
	heapq.heappush(epi, t_push)
	t_pop = heapq.heappop(epi)
	t_epi = t_epi + t_push - t_pop
	epi_sum.append(t_epi)

epi_sum = [epi_sum[-i] for i in range(1,N+2)]
ans = []

for i in range(N+1):
	ans.append(pre_sum[i]+epi_sum[i])

print(max(ans))

Solution (Python):
import sys
import heapq
input = sys.stdin.buffer.readline
def minus(x):
  return -x
N = int(input())
a = list(map(int, input().split()))
dpl = [0] * (N + 1)
dpr = [0] * (N + 1)
l = a[: N]
m = a[N: 2 * N]
r = list(map(minus, a[2 * N: ]))
heapq.heapify(l)
heapq.heapify(r)
dpl[0] = sum(l)
dpr[0] = sum(r)
for i in range(N):
  heapq.heappush(l, m[i])
  dpl[i + 1] = dpl[i] - heapq.heappop(l) + m[i]
  heapq.heappush(r, -m[-1 - i])
  dpr[i + 1] = dpr[i] - heapq.heappop(r) - m[-1 - i]
res = -float("inf")
for i in range(N + 1):
  j = N - i
  res = max(res, dpl[i] + dpr[j])
print(res)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int,input().split()))
    
    import heapq
    que = []
    S = sum(A[:N])
    S1 = [S]
    for i in range(N):
        heapq.heappush(que,A[i])
    for i in range(N):
        tmp = A[N+i]
        if que[0] < tmp:
            S -= que[0]
            S += tmp
            heapq.heappop(que)
            heapq.heappush(que,tmp)
        S1.append(S)
    
    S = sum(A[2*N:])
    que = []
    S2 = [S]
    for i in range(N):
        j = 3*N-1-i
        heapq.heappush(que,-A[j])
    for i in range(N):
        j = 2*N-1-i
        tmp = A[j]
        if -que[0] > tmp:
            S -= -que[0]
            S += tmp
            heapq.heappop(que)
            heapq.heappush(que,-tmp)
        S2.append(S)
    ans = -float("inf")
    for i in range(N+1):
        ans = max(ans, S1[i] - S2[N-i])
    print(ans)
    
    
main()

Solution (Python):
from heapq import heappush, heappop, heapify
N = int(input())
a = list(map(int, input().split()))
ans_list = []
def red_sum():
  red = sum(a[:N])
  pqr = a[:N]
  heapify(pqr)
  ans_list.append(red)
  for i in range(N, 2*N):
    heappush(pqr, a[i])
    red += a[i]-heappop(pqr)
    ans_list.append(red)

def blue_sum():
  blue = sum(a[2*N:])
  pqb = [-a[i] for i in range(2*N, 3*N)]
  heapify(pqb)
  ans_list[N] -= blue
  for i in range(2*N-1, N-1, -1):
    heappush(pqb, -a[i])
    tmp = heappop(pqb)
    blue += a[i]+tmp
    ans_list[i-N] -= blue

red_sum()
blue_sum()
print(max(ans_list))

Solution (Python):
import heapq as h
n = int(input())
l = list(map(int,input().split()))
ls = [0]*(n+1)
rs = [0]*(n+1)
ll = l[:n]
rl = list(map(lambda x:-x,l[2*n:]))
h.heapify(ll)
h.heapify(rl)
ls[0] = sum(ll)
rs[n] = sum(rl)
for i in range(n):
  c = h.heappushpop(ll,l[n+i])
  ls[i+1] = ls[i] + l[n+i] - c
  c = h.heappushpop(rl,-l[2*n-1-i])
  rs[-2-i] = rs[-1-i] - l[2*n-i-1] - c
ans = ls[0]+rs[0]
for i in range(n+1):
  if ans < ls[i]+rs[i]:
    ans = ls[i]+rs[i]
print(ans)

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10*5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

def main():
    n = INT()
    a = LIST()

    a1 = a[:2*n]
    a2 = a[n:]
    a2.reverse()
    for i in range(2*n):
        a2[i] = a2[i]*-1

    def searchmax(a):
        maxl = [0]*(n+1)
        left = a[:n]
        center = a[n:]
        heapq.heapify(left)
        maxl[0] = sum(left)
        for i in range(1,n+1):
            poped = heapq.heappushpop(left, center[i-1])
            maxl[i] = max(maxl[i-1], maxl[i-1]-poped+center[i-1])
        return maxl

    maxll = searchmax(a1)
    minrr = searchmax(a2)
    minrr.reverse()

    res = [INF *-1]*(n+1)
    for i in range(n+1):
        res[i] = maxll[i] + minrr[i]

    print(max(res)) 

if __name__ == '__main__':
    main()

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

first = []
second = []
for i in range(n):
    first.append(a[i])
for i in range(2*n, 3*n):
    second.append(-a[i])
heapq.heapify(first)
heapq.heapify(second)


sumfirst = [0]*(n+1)
sumsecond = [0]*(n+1)
sumfirst[0] = sum(first)
sumsecond[n] = -sum(second)

for i in range(1, n+1):
    k = 0
    k += a[n-1+i]
    heapq.heappush(first, a[n-1+i])
    k -= heapq.heappop(first)
    sumfirst[i] = sumfirst[i-1]+k

for i in range(n-1, -1, -1):
    k = 0
    k += a[n+i]
    heapq.heappush(second, -a[n+i])
    k -= -heapq.heappop(second)
    sumsecond[i] = sumsecond[i+1]+k

res = sumfirst[0]-sumsecond[0]
for i in range(n+1):
    res = max(res, sumfirst[i]-sumsecond[i])
print(res)

Solution (Python):
import heapq

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

left = [0] * (N + 1)
right = [0] * (N + 1)
lq = a[:N]
rq = [0] * N
for i in range(N):
    rq[i] = -a[2 * N + i]
heapq.heapify(lq)
heapq.heapify(rq)
left[0] = sum(lq)
right[-1] = -sum(rq)
for i in range(N):
    new = a[N + i]
    heapq.heappush(lq, new)
    old = heapq.heappop(lq)
    left[i + 1] = left[i] - old + new
for i in range(N):
    new = -a[2 * N - i - 1]
    heapq.heappush(rq, new)
    old = heapq.heappop(rq)
    right[N - i - 1] = right[N - i] + old - new
ans = - 10 ** 20
for i in range(N + 1):
    ans = max(left[i] - right[i], ans)
print(ans)

Solution (Python):


import heapq


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

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

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


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

fh_sum = 0
fh = []
sh_sum = 0
sh = MaxHeap([])
for i in range(n):
    heapq.heappush(fh, a[i])
    fh_sum += a[i]
    sh.push(a[-(i+1)])
    sh_sum += a[-(i+1)]

fh_sums = [fh_sum]
sh_sums = [sh_sum]
for k in range(n, 2 * n):
    fh_sum += a[k]
    heapq.heappush(fh, a[k])
    fh_sum -= heapq.heappop(fh)
    fh_sums.append(fh_sum)
    sh_sum += a[-(k+1)]
    sh.push(a[-(k+1)])
    sh_sum -= sh.pop()
    sh_sums.append(sh_sum)

sh_sums = sh_sums[::-1]

ans = -float("inf")
for fh_sum, sh_sum in zip(fh_sums, sh_sums):
    score = fh_sum - sh_sum
    ans = max(ans, score)

print(ans)

Solution (Python):


import heapq

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

fh_sum = 0
fh = []
sh_sum = 0
sh = []
for i in range(n):
    heapq.heappush(fh, a[i])
    fh_sum += a[i]
    heapq.heappush(sh, -a[-(i+1)])
    sh_sum += a[-(i+1)]

fh_sums = [fh_sum]
sh_sums = [sh_sum]
for k in range(n, 2 * n):
    fh_sum += a[k]
    heapq.heappush(fh, a[k])
    fh_sum -= heapq.heappop(fh)
    fh_sums.append(fh_sum)
    sh_sum += a[-(k+1)]
    heapq.heappush(sh, -a[-(k+1)])
    sh_sum += heapq.heappop(sh)
    sh_sums.append(sh_sum)

sh_sums = sh_sums[::-1]

ans = -float("inf")
for fh_sum, sh_sum in zip(fh_sums, sh_sums):
    score = fh_sum - sh_sum
    ans = max(ans, score)

print(ans)

Solution (Python):
n = int(input())
as_ =  list(map(int, input().split()))

l = [0]*n
m = [0]*n
r = [0]*n
for i in range(n):
  l[i] = as_[i]
  m[i] = as_[n+i]
  r[i] = (-1)*as_[2*n+i]

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

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

sl = sum(l)
sr = sum(r)

for i in range(n+1):
  if i != 0:
    j = i-1
    heapq.heappush(l, m[j])
    a = heapq.heappop(l)
    sl += m[j] -a
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    b = heapq.heappop(r)
    sr += m[k]*(-1) - b
    
  l_maxs[i] = sl
  r_mins[i] = sr




print(max([l_maxs[i] + r_mins[n-i] for i in range(n+1)]))

Solution (Python):
n = int(input())
as_ =  list(map(int, input().split()))

l = [0]*n
m = [0]*n
r = [0]*n
for i in range(n):
  l[i] = as_[i]
  m[i] = as_[n+i]
  r[i] = (-1)*as_[2*n+i]

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

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

sl = sum(l)
sr = sum(r)

for i in range(n+1):
  if i != 0:
    j = i-1
    heapq.heappush(l, m[j])
    a = heapq.heappop(l)
    sl += m[j] -a
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    b = heapq.heappop(r)
    sr += m[k]*(-1) - b
    
  l_maxs[i] = sl
  r_mins[i] = sr




print(max([l_maxs[i] + r_mins[n-i] for i in range(n+1)]))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = LI()
score = [0]  * (n + 1)
a_max = L[:n]
heapify(a_max)
max_sum = sum(a_max)
score[0] = max_sum
for i in range(n):
    heappush(a_max, L[n+i])
    max_sum += L[n + i]
    max_sum -= heappop(a_max)
    score[i+1] = max_sum



a_min = L[2 * n:]
min_sum = sum(a_min)
score[-1] -= min_sum


for i in range(len(a_min)):
    a_min[i] *= -1


heapify(a_min)


for i in range(n):
    min_sum += L[2*n-i-1]
    heappush(a_min, -L[2*n-i-1])
    min_sum += heappop(a_min)
    score[-2-i] -= min_sum



print(max(score))

Solution (Python):
import heapq
def main():

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

    A1 = sorted(A[:N])
    A2 = A[N:2*N]
    A3 = sorted([-a for a in A[2*N:]])

    tot1 = sum(A1)
    max_tot1 = [tot1]
    for i in range(N):
        heapq.heappush(A1, A2[i])
        v = heapq.heappop(A1)
        tot1 += A2[i] - v
        max_tot1.append(tot1)

    tot3 = -sum(A3)
    max_tot3 = [tot3]
    for i in range(N-1, -1, -1):
        heapq.heappush(A3, -A2[i])
        v = - heapq.heappop(A3)
        tot3 += A2[i]- v
        max_tot3.append(tot3)

    max_tot3 = max_tot3[::-1]

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

    return ans

if __name__ == '__main__':
    print(main())

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect

import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()

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

a_max = a[:N]
a_min = a[2*N:]

a_max_sum = sum(a_max)
score = [a_max_sum]
heapq.heapify(a_max)
for i in range(N):
	heapq.heappush(a_max, a[N + i])
	a_max_sum += a[N + i]
	a_max_sum -= heapq.heappop(a_max)
	score.append(a_max_sum)

a_min_sum = sum(a_min)
score[N] -= a_min_sum
for i in range(len(a_min)):
	a_min[i] *= -1
heapq.heapify(a_min)
for i in range(N):
	heapq.heappush(a_min, -a[2*N - 1 - i])
	a_min_sum += a[2*N - 1 - i]
	a_min_sum += heapq.heappop(a_min)
	score[N - i - 1] -=a_min_sum

print(max(score))

Solution (Python):
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:]

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

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

print(max(r + b for r, b in zip(red, reversed(blue))))

Solution (Python):
from heapq import heapify, heappushpop

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

Q = A[:N]
heapify(Q)

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

Q = [-a for a in A[2 * N:]]
heapify(Q)

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

print(max(r + b for r, b in zip(R, reversed(B))))

Solution (Python):
from heapq import heapify, heappop, heappush

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

Q = A[:N]
heapify(Q)

R = [sum(Q)]
for a in A[N:2 * N]:
    heappush(Q, a)
    R.append(R[-1] + a - heappop(Q))

Q = [-a for a in A[2 * N:]]
heapify(Q)

B = [sum(Q)]
for a in reversed(A[N:2 * N]):
    heappush(Q, -a)
    B.append(B[-1] - a - heappop(Q))

print(max(r + b for r, b in zip(R, reversed(B))))

Solution (Python):
from heapq import heapify, heappop, heappush

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

Q = A[:N]
heapify(Q)

R = [sum(Q)]
for k in range(N, 2 * N):
    heappush(Q, A[k])
    m = heappop(Q)
    R.append(R[-1] + A[k] - m)

Q = [-a for a in A[2 * N:]]
heapify(Q)

B = [sum(Q)]
for k in reversed(range(N, 2 * N)):
    heappush(Q, -A[k])
    m = heappop(Q)
    B.append(B[-1] - A[k] - m)

print(max(r + b for r, b in zip(R, reversed(B))))

Solution (Python):
import heapq

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

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

a = [-x for x in a][::-1]
minus = [0] * (3 * n)
tmp = a[:n]
s = sum(tmp)
heapq.heapify(tmp)
for i in range(n, 2*n):
    minus[i-1] = s
    heapq.heappush(tmp, a[i])
    s += a[i]
    s -= tmp[0]
    heapq.heappop(tmp)
minus[2*n-1] = s
minus = minus[::-1]
ans = plus[n-1] + minus[n]
for i in range(n-1, 2*n):
    ans = max(ans, plus[i] + minus[i+1])

print(ans)

Solution (Python):
from heapq import heapify, heappop as pop, heappush as push

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

l = a[:N]
m = a[N:N*2]
r = [x * -1 for x in a[N*2:]] 

heapify(l)
heapify(r)

ll = [sum(l)]
for em in m:
    l_min = pop(l)
    if l_min < em:
        ll.append(ll[-1] - l_min + em)
        push(l, em)
    else:
        ll.append(ll[-1])
        push(l, l_min)

rr = [sum(r)] 
for em in reversed(m):
    r_max = pop(r) * -1
    if r_max > em:
        rr.append(rr[-1] + r_max - em)
        push(r, em * -1)
    else:
        rr.append(rr[-1])
        push(r, r_max * -1)

print(max(a + b for a, b in zip(ll, reversed(rr))))

Solution (Python):
from collections import deque
from heapq import heapify, heappop as pop, heappush as push

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

l = a[:N]
m = deque(a[N:N*2])
r = [x * -1 for x in a[N*2:]] 

heapify(l)
heapify(r)

ll = [sum(l)]
for em in m:
    l_min = pop(l)
    if l_min < em:
        ll.append(ll[-1] - l_min + em)
        push(l, em)
    else:
        ll.append(ll[-1])
        push(l, l_min)

rr = [sum(r)] 
for em in reversed(m):
    r_max = pop(r) * -1
    if r_max > em:
        rr.append(rr[-1] + r_max - em)
        push(r, em * -1)
    else:
        rr.append(rr[-1])
        push(r, r_max * -1)

print(max(a + b for a, b in zip(ll, reversed(rr))))

Solution (Python):
from heapq import *
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    heappush(b,a[i])
s=sum(b)
d=[0]*(n+1)
d[0]=s
for i in range(n,2*n):
    t=heappop(b)
    if t>a[i]:
        heappush(b,t)
    else:
        s=s-t+a[i]
        heappush(b,a[i])
    d[i-n+1]=s
b=[]
for i in range(2*n,3*n):
    heappush(b,-a[i])
s=sum(b)
d[n]+=s
for i in range(2*n-1,n-1,-1):
    t=heappop(b)
    if t>-a[i]:
        heappush(b,t)
    else:
        s=s-t-a[i]
        heappush(b,-a[i])
    d[i-n]+=s
print(max(d))

Solution (Python):


import heapq as hq

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

hq.heapify(l)
hq.heapify(r)
ans = 0
suml =[0 for _ in range(n+1)]
suml[0] = sum(l)
sumr=[0 for _ in range(n+1)]
sumr[-1] = -1*sum(r)

for i in range(n,2*n):
    minl =hq.heappop(l)
    if a[i] >minl:
        suml[i+1-n] =suml[i-n]+ a[i] - minl
    else:
        suml[i+1-n] =suml[i-n]
    hq.heappush(l,max(a[i],minl))
for i in range(-1-n,-n-n-1,-1):
    maxr =-1*hq.heappop(r)
    if a[i] <maxr:
        sumr[i-1+n] =sumr[i+n]+ a[i] - maxr
    else:
        sumr[i-1+n] =sumr[i+n]
    hq.heappush(r,-1*min(a[i],maxr))

ans = max([x - y for x,y in zip(suml,sumr)])
print(ans)

Solution (Python):

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

a = []
for i in range(N):
    heapq.heappush(a,A[i])
B = []
for i in range(3*N):
    B.append(-A[3*N-1-i])
b = []
for i in range(N):
    heapq.heappush(b,B[i])

Red = [sum(a)]
Blue = [sum(b)]
inf = float("inf")
MAX = -inf
AR = []
BB = []
for i in range(N):
    AR.append(A[N+i])
    BB.append(B[N+i])
for i,(ar,r) in enumerate(zip(AR,Red)):
    l = heapq.heappushpop(a,ar)
    Red.append(r+(ar-l))
for i,(bb,bl) in enumerate(zip(BB,Blue)):
    m = heapq.heappushpop(b,bb)
    Blue.append(bl+(bb-m))
    
for i in range(N+1):
    
    MAX = max(MAX,Red[i]+Blue[N-i])


print(MAX)

Solution (Python):
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()

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = list(map(int, input().split()))

    
    front = []
    front_sum = 0
    for i in range(n):
        front_sum += al[i]
        heappush(front, al[i])

    front_sums = [front_sum]
    for i in range(n, n * 2):
        minimum = heappop(front)
        if minimum < al[i]:
            front_sum += al[i] - minimum
            heappush(front, al[i])
        else:
            heappush(front, minimum)
        front_sums.append(front_sum)

    
    back = []
    back_sum = 0
    for i in range(n * 2, n * 3):
        back_sum += al[i]
        heappush(back, -al[i])

    back_sums = [back_sum]
    for i in range(n * 2 - 1, n - 1, -1):
        maximum = -heappop(back)
        if maximum > al[i]:
            back_sum += al[i] - maximum
            heappush(back, -al[i])
        else:
            heappush(back, -maximum)
        back_sums.append(back_sum)

    back_sums.reverse()

    
    

    ans = -10**20
    for f, b in zip(front_sums, back_sums):
        ans = max(ans, f - b)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq


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

first = a[0: n]
latter = list(map(lambda x: x*-1, a[2*n: 3*n]))
heapq.heapify(first)
heapq.heapify(latter)

sum_first = []
sum_latter = []
sum_first.append(sum(first))
sum_latter.append(-sum(latter))

for i in range(0, n):
    new = a[n+i]
    heapq.heappush(first, new)
    old = heapq.heappop(first)
    sum_first.append(sum_first[i] + new - old)

for j in range(n):
    new = a[2*n-1-j]
    heapq.heappush(latter, -new)
    old = -heapq.heappop(latter)
    sum_latter.append(sum_latter[j] + new - old)

ans = sum_first[0] - sum_latter[n]
for k in range(n+1):
    x = sum_first[k] - sum_latter[n-k]
    if x > ans:
        ans = x

print(ans)

Solution (Python):
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])




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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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)