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


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

fa = A[:N]
max_l = [0] * (N + 1)
s = sum(fa)
max_l[0] = s
heapq.heapify(fa)
for i, a in enumerate(A[N:2*N]):
    if a > fa[0]:
        s -= heapq.heappop(fa)
        s += a
        heapq.heappush(fa, a)
    max_l[i+1] = s

la = [-i for i in A[2*N:]]
min_r = [0] * (N + 1)
s = sum(la)
min_r[N] = s
heapq.heapify(la)
for i, a in enumerate(reversed(A[N:2*N])):
    if a < -la[0]:
        s -= heapq.heappop(la)
        s += -a
        heapq.heappush(la, -a)
    min_r[N-i-1] = s

print(max([l + r for l, r in zip(max_l, min_r)]))

Submission status: Accepted

Solution code:
import heapq

n = int(input())
a = list(map(int, input().split()))
first = a[:n]
second = a[n:2*n]
third = [ -1*i for i in a[2*n:3*n]]
sum_first = sum(first)
sum_third = sum(third)
results = [0]*(n+1)
results[0] = sum_first
results[n] = sum_third
heapq.heapify(first)
heapq.heapify(third)

for i in range(n):
    x = second[i]
    p = heapq.heappushpop(first, x)
    sum_first = sum_first + x - p
    results[i+1] += sum_first

for i in reversed(range(n)):
    x = -1*second[i]
    p = heapq.heappushpop(third,x)
    sum_third = sum_third + x - p
    results[i] += sum_third

print(max(results))

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n = int(input())
    aa = LI()
    #どこかで2つに区切って、左の上位n項の和と右の下位n項の和を求め、その差を最大にすればいい
    # 左からn+i項のうち上位n項の和をmax_Lに記録
    max_L = [0] * (n + 1)
    hp = []
    s = 0
    for a in aa[:n]:
        heappush(hp, a)
        s += a
    max_L[0] = s
    for i, a in enumerate(aa[n:2 * n], 1):
        if a > hp[0]:
            s -= heappop(hp)
            s += a
            heappush(hp, a)
        max_L[i] = s

    # 右からn+i項のうち下位n項の和をmin_Rに記録
    min_R = [0] * (n + 1)
    hp = []
    s = 0
    for a in aa[:-n - 1:-1]:
        heappush(hp, -a)
        s += a
    min_R[n] = s
    for i, a in enumerate(aa[-n - 1:-2 * n - 1:-1]):
        if a > hp[0]:
            s -= -heappop(hp)
            s += a
            heappush(hp, -a)
        min_R[n - 1 - i] = s
    # print(max_L)
    # print(min_R)
    #各区切り方にのうち、左ー右が最大のものが答え
    print(max(s0 - s1 for s0, s1 in zip(max_L, min_R)))

main()

Submission status: Accepted

Solution code:
import heapq

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

suma = sum(a[:N])
maxr = [suma] * (N + 1)
hq = a[:N]
heapq.heapify(hq)

for i in range(N, 2*N):
  mina = heapq.heappushpop(hq, a[i])
  suma = suma - mina + a[i]
  maxr[i - N + 1] = suma

suma = sum(a[2 * N : 3 * N])
minr = [suma] * (N + 1)
hq = list(map(lambda x: -x, a[2*N:3*N]))
heapq.heapify(hq)

for i in range(2 * N - 1, N - 1, -1):
  maxa = heapq.heappushpop(hq, -a[i])
  suma = suma + maxa + a[i]
  minr[i - N] = suma

print(max([maxr[i] - minr[i] for i in range(N + 1)]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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) #; print(Hl)
suml = sum(Hl)
sumL = [suml]

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

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

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

Submission status: Accepted

Solution code:
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]:  # h2:最大値
		sum_h2 -= heapq.heappop(h2)
		sum_h2 += -a[i]
		heapq.heappush(h2, -a[i])
	min_h2[i-N] = sum_h2
# print(max_h)
# print(min_h2)
ans = -INF
for i in range(N+1):
	ans = max(ans, max_h[i]+min_h2[i])
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
#print(mx,mn)
buf=float('inf')
buf*=-1
for i in range(n+1):
    buf=max(buf,mx[i]-mn[i])
    
print(buf)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)
# print(ls)
# print(rs)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

Submission status: Accepted

Solution code:
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(l_maxs)
#print(r_mins)

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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]

    # print(max_tot1)
    # print(max_tot3)
    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())

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
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))

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

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

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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)

Submission status: Accepted

Solution code:
#C問題
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):
    #print(Red[i],Blue[N-i])
    MAX = max(MAX,Red[i]+Blue[N-i])

#print(A,B)
print(MAX)

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:
# https://atcoder.jp/contests/arc074/tasks/arc074_b

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 = []
    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 = []
    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()

    # print(front_sums)
    # print(back_sums)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)