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: Time Limit Exceeded

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
lst=[]
left_array=array[:N] 
right_array=array[-N:]
l_sum=sum(left_array)
r_sum=sum(right_array)
left_lst=[l_sum]
right_lst=[r_sum]
for k in range(N,2*N):
    new_a=array[k]
    new_b=array[-k-1]
    left_array.append(new_a)
    old_a=min(left_array)
    left_array.remove(old_a)
    l_sum+=(new_a-old_a)
    left_lst.append(l_sum)
    right_array.append(new_b)
    old_b=max(right_array)
    right_array.remove(old_b)
    r_sum+=(new_b-old_b)
    right_lst.append(r_sum)
lst = [a-b for a,b in zip(left_lst,list(reversed(right_lst)))]
print(max(lst))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
lst=[]
left_array=array[:N] 
right_array=array[-N:]
left_lst=[sum(left_array)]
right_lst=[sum(right_array)]
for k in range(N,2*N):
    new_a=array[k]
    new_b=array[-k-1]
    left_array.append(new_a)
    left_array.remove(min(left_array))
    left_lst.append(sum(left_array))
    right_array.append(new_b)
    right_array.remove(max(right_array))
    right_lst.append(sum(right_array))
lst = [a-b for a,b in zip(left_lst,list(reversed(right_lst)))]
print(max(lst))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
lst=[]
for i in range(N+1):
    left_array=array[:N+i]
    l = sorted(left_array)[-N:]
    right_array=array[N+i:]
    r = sorted(right_array)[:N]
    ans = sum(l)-sum(r)
    if lst ==[] or ans>lst:
        lst=ans
print(lst)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
lst=[]
for i in range(N+1):
    left_array=array[:N+i]
    l = sorted(left_array)[-N:]
    right_array=array[N+i:]
    r = sorted(right_array)[:N]
    ans = sum(l)-sum(r)
    lst.append(ans)
print(max(lst))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
S=-10**14
for i in range(N+1):
  b=a[0:N+i]
  c=a[N+i:3*N]
  b.sort(reverse=1)
  c.sort()
  B=0
  C=0
  for j in range(N):
    B+=b[j]
    C+=c[j]
  S=max(S,B-C)
print(S)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
N = int(input())
a = [int(n) for n in input().split()]

score_list = []

for i in range(N + 1):
    a_copy = deepcopy(a)
    first_a = a_copy[:N + i]
    last_a = a_copy[N + i:]
    score_list.append(sum(sorted(first_a, reverse=True)[:N]) - sum(sorted(last_a)[:N]))

print(max(score_list))

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
a = map(int, raw_input().split())

left = sorted(a[:N])
middle = a[N:2*N]
right = sorted(a[N:])

m = sum(left) - sum(right[:N])
for i in middle:
    if (i > left[0]):
        left.remove(left[0])
        for j, l in enumerate(left):
            if (i < left[j]):
                left.insert(j, i)
                break
        if len(left) < N:
            left.append(i)
    right.remove(i)
    score = sum(left) - sum(right[:N])
    if m < score:
        m = score
print m

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(raw_input())
a = map(int, raw_input().split())

m = -sys.maxint - 1
for i in range(N+1):
    left = sorted(a[:N+i])
    right = sorted(a[N+i:])
    score = sum(left[i:]) - sum(right[:N])
    if m < score:
        m = score
print m

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp

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

sm = -float('inf')
for i in range(N, 2 * N + 1):
    left = a[:i]
    right = [-a[n] for n in range(i, 3 * N)]
    hp.heapify(left)
    hp.heapify(right)
    for j in range(i - N):
        hp.heappop(left)
    for k in range(2 * N - i):
        hp.heappop(right)
    sm = max(sm, sum(left) - sum(right) * -1)

print(sm)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappushpop

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

max_score = float('-inf')
a_list_1_init = []
a_list_2_init = []
for i in a[0:N]:
    heappush(a_list_1_init, i)
for i in list(reversed(a))[0:N]:
    heappush(a_list_2_init, -i)

sum_1_init = sum(a_list_1_init)
sum_2_init = sum(a_list_2_init)
for i in range(N, 2 * N + 1):
    a_list_1 = list(a_list_1_init)
    a_list_2 = list(a_list_2_init)
    sum_1 = sum_1_init
    sum_2 = sum_2_init
    for k in a[N:i]:
        l = heappushpop(a_list_1, k)
        sum_1 += k - l
    for k in a[i:2*N]:
        l = heappushpop(a_list_2, -k)
        sum_2 += -k - l
    score = sum_1 + sum_2
    if score > max_score:
        max_score = score

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappushpop

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

max_score = float('-inf')
for i in range(N, 2 * N + 1):
    rm_count_1 = i - N
    rm_count_2 = N - rm_count_1
    a_list_1 = []
    a_list_2 = []
    for k in a[0:i]:
        if len(a_list_1) >= N:
            heappushpop(a_list_1, k)
        else:
            heappush(a_list_1, k)
    for k in a[i:3*N]:
        if len(a_list_2) >= N:
            heappushpop(a_list_2, -k)
        else:
            heappush(a_list_2, -k)
    sum_1 = sum(a_list_1)
    sum_2 = sum(a_list_2)
    score = sum_1 + sum_2
    if score > max_score:
        max_score = score

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
N=int(raw_input())
a=map(int,raw_input().split(' '))

def argmax(a):
    m=max(a)
    for i in range(len(a)-1,-1,-1):
        if a[i]==m:
            return i
        
    return None

def argmin(a):
    return a.index(min(a))

s_max=float('-inf')
for i in range(N+1):
    a_head=a[0:N+i]
    a_tail=a[N+i:]
    for _ in range(i):
        del(a_head[argmin(a_head)])
    for _ in range(N-i):
        del(a_tail[argmax(a_tail)])

    #print a_head,a_tail
    #a_res=a_head+a_tail
    #print a_res[0:len(a_res)/2],a_res[len(a_res)/2:]
    #s=sum(a_res[0:len(a_res)/2])-sum(a_res[len(a_res)/2:])
    s=sum(a_head)-sum(a_tail)
    if s_max<s:
        s_max=s

print s_max

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
r = []
b = a[:n]
bs = sum(b)
c = sorted(a[n:])
cs = sum(c[:n])
r.append(bs-cs)
for k in range(n,2*n):
  b.append(a[k])
  bm = min(b)
  b.remove(bm)
  bs = bs + a[k] - bm
  ci = c.index(a[k])
  if ci < n:
    cs = cs - a[k] + c[n]
  c.pop(ci)
  r.append(bs-cs)
print(max(r))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
r = []
b = a[:n]
c = sorted(a[n:])
r.append(sum(b)-sum(c[:n]))
for k in range(n,2*n):
  b.append(a[k])
  b.remove(min(b))
  c.remove(a[k])
  r.append(sum(b)-sum(c[:n]))
print(max(r))

Submission status: Time Limit Exceeded

Solution code:

def cal(lst, n):
    return sum(lst[:n])-sum(lst[-n:])


n = int(input())
a = list(map(int, input().split(' ')))
max_ = float('-inf')
for k in range(n+1):
    t = a[:]
    for i in range(k):
        t.pop(t[:n+k-i].index(min(t[:n+k-i])))

    for i in range(n-k):
        t.pop(n+t[-(2*n-k)+i:].index(max(t[-(2*n-k)+i:])))

    if max_ < cal(t, n):
        max_ = cal(t, n)

print(max_)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
a = [int(n) for n in input().split()]
score = 10**9 * 10**5 * -3
for n in range(N+1):
    before = a[:N + n]
    after = a[N+n:]

    b_max = sum(sorted(before, reverse=True)[:N])
    a_min = sum(sorted(after)[:N])
    
    score = max(score, b_max - a_min)
print(score)

Submission status: Time Limit Exceeded

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

max_score = float('-inf')
for i in range(N, 2 * N + 1):
    rm_count_1 = i - N
    rm_count_2 = N - rm_count_1
    a_list_1 = sorted(a[0:i])
    a_list_2 = sorted(a[i:3 * N])
    sum_1 = sum(a_list_1[rm_count_1:i])
    sum_2 = sum(a_list_2[0:N])
    score = sum_1 - sum_2
    if score > max_score:
        max_score = score

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
DB = dict()
B = set([(a[i],i) for i in range(n)])
mB = min(B)
DB[n-1] = sum(a[:n])
for i in range(n,2*n):
  DB[i] = DB[i-1]
  if a[i] > mB[0]:
    DB[i] += a[i] - mB[0]
    B.remove(mB)
    B.add((a[i],i))
    mB = min(B)
DE = dict()
E = set([(a[i],i) for i in range(2*n,3*n)])
mE = max(E)
DE[2*n] = sum(a[2*n:])
for i in range(2*n-1,n-1,-1):
  DE[i] = DE[i+1]
  if a[i] < mE[0]:
    DE[i] += a[i] - mE[0]
    E.remove(mE)
    E.add((a[i],i))
    mE = max(E)
ret = DB[n-1] - DE[n]
for i in range(n,2*n):
  ret = max(ret,DB[i]-DE[i+1])
print(ret)

Submission status: Time Limit Exceeded

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

import sys
import os

N = int(input())

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

max_score = float("-inf")
for cut_i in range(N, 2 * N + 1):
    B = A[:cut_i]
    B.sort(reverse=True)
    C = A[cut_i:]
    C.sort()

    score = sum(B[:N]) - sum(C[:N])
    if score > max_score:
        max_score = score
        
print(max_score)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
h1=A[:N]
L=[0 for i in range(N+1)]
L[0]=sum(h1)
sum1=sum(h1)
import heapq
heapq.heapify(h1)
for i in range(N):
  heapq.heappush(h1,A[N+i])
  a=heapq.heappop(h1)
  sum1=sum1+A[N+i]-a
  L[i+1]=sum1
h=A[2*N:]
h2=[-i for i in h]
R=[0 for i in range(N+1)]
R[N]=-sum(h2)
sum2=-sum(h2)
heapq.heapify(h2)
for i in range(N):
  heapq.heappush(h2,-A[2*N-1-i])
  a=heapq.heappop(h2)
  sum2=sum2+A[2*N-1-i]+a
  R[N-i-1]=sum2
import math
ans=-math.inf
for i in range(N+1):
  ans=max(ans,L[i]-R[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq
N=int(input())
A=list(map(int, input().split()))
A_rev = [-x for x in A[::-1]] #逆順にして各要素を-1倍する
left, right = A[:N], A_rev[:N]
sum_left_list, sum_right_list = [0]*(N+1), [0]*(N+1)
sum_left, sum_right = sum(left), sum(right)
sum_left_list[0], sum_right_list[0]=sum_left, sum_right
heapq.heapify(left)
heapq.heapify(right)
#left: k=N, N+1,..., 2N-1まで動かして大きい方からN個の和を求める
for k in range(N, 2*N):
	val=A[k]
	heapq.heappush(left, val)
	min_val = heapq.heappop(left)
	sum_left += val
	sum_left -= min_val
	sum_left_list[k-N+1] = sum_left

#right: k=N, N+1,..., 2N-1まで動かして大きい方からN個の和を求める
for k in range(N, 2*N):
	val = A_rev[k]
	heapq.heappush(right, val)
	min_val = heapq.heappop(right)
	sum_right += val
	sum_right -= min_val
	sum_right_list[k-N+1] = sum_right
sum_right_list=sum_right_list[::-1]

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

Submission status: Accepted

Solution code:
#########################ABC解説実装#########################
import heapq
N=int(input())
A=list(map(int, input().split()))

left, right = A[:N], [-1 * i for i in A[2*N:]]
sum_left, sum_right = sum(left), sum(right)

results = [0] * (N+1)
results[0] = sum_left
results[N] = sum_right

heapq.heapify(left)
heapq.heapify(right)

for i in range(N, 2*N):
    v = A[i]
    p = heapq.heappushpop(left, v)
    sum_left += v - p
    results[i-N+1] += sum_left
    
for i in range(2*N-1, N-1, -1):
    v = -1 * A[i]
    p = heapq.heappushpop(right, v)
    sum_right += v - p
    results[i-N] += sum_right
print(max(results))

Submission status: Accepted

Solution code:
import heapq

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

lq=[]
lsum=0
for i in range(n):
    heapq.heappush(lq,a[i])
    lsum+=a[i]

l=[0]*(3*n)
l[n-1]=lsum
for i in range(n,2*n):
    lsum+=a[i]
    heapq.heappush(lq,a[i])
    lsum-=heapq.heappop(lq)
    l[i]=lsum

rq=[]
rsum=0
for i in range(3*n-1,2*n-1,-1):
    heapq.heappush(rq,-a[i])
    rsum+=a[i]

r=[0]*(3*n)
r[2*n]=rsum
for i in range(2*n-1,n-1,-1):
    rsum+=a[i]
    heapq.heappush(rq,-a[i])
    rsum+=heapq.heappop(rq)
    r[i]=rsum

ans=-10**15

for i in range(n-1,2*n):
    ans=max(ans,l[i]-r[i+1])

print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

mae = A[:N]
heapq.heapify(mae)
mae_score = [sum(mae)]

for i in range(N):
  a = A[i+N]
  if a > mae[0]:
    mae_score.append(mae_score[-1]+a-heapq.heappop(mae))
    heapq.heappush(mae,a)
  else:
    mae_score.append(mae_score[-1])

ushiro = [-i for i in A[2*N:]]
heapq.heapify(ushiro)
ushiro_score = [sum(ushiro)]

for i in range(N):
  a = -A[2*N-1-i]
  if a > ushiro[0]:
    ushiro_score.append(ushiro_score[-1]+a-heapq.heappop(ushiro))
    heapq.heappush(ushiro,a)
  else:
    ushiro_score.append(ushiro_score[-1])

ans = -INF
for i in range(N+1):
  ans = max(ans,mae_score[i]+ushiro_score[N-i])

print(ans)

Submission status: Accepted

Solution code:
with open(0) as f:
    N, *a = map(int, f.read().split())
F = [x for x in a[:N]] #Fの要素は加えるか取り除くかの2択
C = [x for x in a[N:2*N]] 
B = [-x for x in a[2*N:]] #Bの要素は引くか取り除くかの二択
import heapq as hq
#ヒープにして常に最小値を追跡
hq.heapify(F)
hq.heapify(B)

#Cを二分し、前半はFと、後半はBとで演算を行う
#演算方法(c in C)
#前半：cがF[0]より大きければF[0]を取り除くN個の一つとし、cをスコアに加える
#後半：-cがB[0]より大きければB[0]を取り除くN個の一つとし、cをスコアから引く
#どちらも場合も条件を満たさない場合はそのｃを取り除くN個の一つとする
#計算量：O(N*N*logN)
#途中計算をメモして計算量軽減
from copy import deepcopy
memoF = [0] * (N+1) #C[:i]を前半としたときのFとの演算結果の要素和
memoF[0] = sum(F)
memoB = [0] * (N+1) #C[i:]を後半としたときのBとの演算結果の要素和
memoB[N] = sum(B)
for i in range(N):
    if C[i] > F[0]:
        memoF[i+1] = memoF[i] + C[i] - hq.heapreplace(F, C[i])
    else:
        memoF[i+1] = memoF[i]

    if -C[N-1-i] > B[0]:
        memoB[N-1-i] = memoB[N-i] - C[N-1-i] - hq.heapreplace(B, -C[N-1-i])
    else:
        memoB[N-1-i] = memoB[N-i]

Scores = [memoF[i]+memoB[i] for i in range(N+1)]
ans = max(Scores)
print(ans)

Submission status: Accepted

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

    from heapq import heapify, heappushpop

    # first half
    fh = []
    l = a[:n]
    fh.append(sum(l))
    heapify(l)
    for i in a[n:2*n]:
        if l[0] < i:
            fh.append(fh[-1] + i - heappushpop(l, i))
        else:
            fh.append(fh[-1])

    # latter half
    lh = []
    l = [-i for i in a[2*n:]]
    lh.append(sum(l))
    heapify(l)
    for i in a[2*n-1:n-1:-1]:
        if l[0] < -i:
            lh.append(lh[-1] - i - heappushpop(l, -i))
        else:
            lh.append(lh[-1])

    ans = fh[0] + lh[n]
    for i in range(1, n+1):
        if ans < fh[i] + lh[n-i]:
            ans = fh[i] + lh[n-i]

    print(ans)

main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

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

ll = al[0:n]
cl = al[n:2*n]
rl = al[2*n:3*n]
rl = list(map(lambda x: -x, rl))


heapify(ll)
heapify(rl)

ll_vals = []
ll_vals.append(sum(ll))
c_sum = sum(ll)
c_max = c_sum
for i in range(n):
    poped = heappop(ll)
    c_sum -= poped
    heappush(ll,cl[i])
    c_sum += cl[i]
    c_max = max(c_max, c_sum)
    ll_vals.append(c_max)


rl_vals = []
rl_vals.append(-sum(rl))
c_sum = -sum(rl)
c_min = c_sum
for i in range(n):
    poped = -heappop(rl)
    c_sum -= poped
    heappush(rl,-cl[n-1-i])
    c_sum += cl[n-1-i]
    c_min = min(c_min, c_sum)
    rl_vals.append(c_min)


ans = -1*(10**18)
for i in range(n+1):
    v = ll_vals[i] - rl_vals[n-i]
    ans = max(ans,v)

print(ans)

Submission status: Accepted

Solution code:
from heapq import *
N = int(input())
A = list(map(int,input().split()))
L,C,R = A[:N],A[N:2*N],A[2*N:]
F = [sum(L)]
heapify(L)

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

R = [-r for r in R]
B = [sum(R)]
heapify(R)

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

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
n=int(input())
a=list(map(int,input().split()))
p=sum(a[2*n:])
right_min=[p]
hq=[]
for i in range(2*n,2*n+n):
	heappush(hq,-a[i])
for i in range(n):
	p+=a[-n-i-1]
	heappush(hq,-a[-n-i-1])
	p+=heappop(hq)
	right_min.append(p)
l=sum(a[:n])
hq=[]
for i in range(n):
	heappush(hq,a[i])
right_min.reverse()
ans=l-right_min[0]
for i in range(n):
	l+=a[n+i]
	heappush(hq,a[n+i])
	l-=heappop(hq)
	ans=max(ans,l-right_min[i+1])
print(ans)

Submission status: Accepted

Solution code:
import  heapq

N = int(input())
a = list(map(int, input().split()))
c_que = list(map(lambda x:x*(-1), a[2*N:]))
a_que = a[:N]

a_sum = sum(a_que)
c_sum = -sum(c_que)

heapq.heapify(a_que)
heapq.heapify(c_que)

ans = -(10**15)

score = [[0, 0] for _ in range(N+1)]
score[0][0] = a_sum
score[N][1] = c_sum

for i in range(N):
    heapq.heappush(a_que, a[N+i])
    heapq.heappush(c_que, -a[2*N-1-i])
    
    a_sum = a_sum + a[N+i] - heapq.heappop(a_que)
    c_sum = c_sum + a[2*N-1-i] + heapq.heappop(c_que)
    
    score[i+1][0] = a_sum
    score[N-1-i][1] = c_sum
    
for i in range(N+1):
    ans = max(ans, score[i][0]-score[i][1])
print(ans)

Submission status: Accepted

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


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

    af = a[:n]
    ab = [-v for v in a[2*n:]]
    af_sum = sum(af)
    ab_sum = -sum(ab)

    heapify(af)
    heapify(ab)
    judge = [0]*(n+1)
    judge[0] += af_sum
    judge[n] -= ab_sum
    
    for i in range(n):
        if a[n+i] > af[0]:
            af_sum -= heappop(af)
            heappush(af, a[n+i])
            af_sum += a[n+i]
        judge[i+1] += af_sum
        
        if -a[2*n-1-i] > ab[0]:
            ab_sum += heappop(ab)
            heappush(ab, -a[2*n-1-i])
            ab_sum += a[2*n-1-i]
        judge[n-1-i] -= ab_sum
    

    ans = max(judge)
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    S = list(accumulate(A))

    # small[i] = A[1],A[2],...,A[N + i]から小さい順にi個選んだときの和
    small = [0] * (N + 1)
    q = []
    for i in range(1, N + 1): heappush(q, A[i])
    for i in range(1, N + 1):
        heappush(q, A[N + i])
        v = heappop(q)
        small[i] = small[i - 1] + v

    # large[i] = A[3N],A[3N-1],...,A[2N+1-i]から大きい順にi個選んだときの和
    large = [0] * (N + 1)
    q = []
    for i in range(2 * N + 1, 3 * N + 1): heappush(q, -A[i])
    for i in range(1, N + 1):
        heappush(q, -A[2 * N + 1 - i])
        v = -heappop(q)
        large[i] = large[i - 1] + v

    ans = -10**18
    for i in range(N, 2 * N + 1):
        """
        A[1],A[2],...,A[i]から小さい順に(i - N)個除いたものが前半
        A[i+1],A[i+2],...,A[3N]から大きい順に(2N - i)個除いたものが後半
        """
        pre = S[i] - small[i - N]
        post = (S[-1] - S[i]) - large[2 * N - i]
        ans = max(ans, pre - post)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop

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

    front = A[:n]
    fsum = [0] * (3*n)
    fsum[n-1] = sum(front)
    heapify(front)
    for i in range(n, 2*n):
        fmin = heappushpop(front, A[i])
        fsum[i] = fsum[i-1] + A[i] - fmin

    back = [-1*a for a in A[2*n:]]
    bsum = [0] * (3*n)
    bsum[2*n] = -1 * sum(back)
    heapify(back)
    for i in range(2*n-1, n-1, -1):
        bmax = -1 * heappushpop(back, -1*A[i])
        bsum[i] = bsum[i+1] + A[i] - bmax

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

if __name__ == '__main__':
    abc062_d()

Submission status: Accepted

Solution code:
import heapq

n = int(input())
a = list(map(int, input().split()))
score = [[0, 0] for _ in range(n + 1)]
h1 = a[0 : n]
h2 = [-a[2 * n + i] for i in range(n)]
maxscore = sum(h1)
minscore = -sum(h2)
heapq.heapify(h1)
heapq.heapify(h2)
score[0][0] = maxscore
score[n][1] = minscore
for i in range(n):
    heapq.heappush(h1, a[n + i])
    heapq.heappush(h2, -a[2 * n - 1 - i])
    maxscore = maxscore + a[n + i] - heapq.heappop(h1)
    minscore = minscore + a[2 * n - 1 - i] + heapq.heappop(h2)
    score[i + 1][0] = maxscore
    score[n - 1 - i][1] = minscore
ans = -pow(10, 15)
for i in range(n + 1):
    ans = max(ans, score[i][0] - score[i][1])
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

L = A[:N]
heapq.heapify(L)
Lmax = [0] * (N + 1)
Lsum = sum(L)
Lmax[0] = Lsum
for i in range(N, 2 * N):
    m = heapq.heappushpop(L, A[i])
    Lsum += A[i] - m
    Lmax[i - N + 1] = Lsum

R = [-x for x in A[2 * N:]]
heapq.heapify(R)
Rmin = [0] * (N + 1)
Rsum = -sum(R)
Rmin[N] = Rsum
for i in range(2 * N - 1, N - 1, -1):
    M = -heapq.heappushpop(R, -A[i])
    Rsum -= M - A[i]
    Rmin[i - N] = Rsum

print(max(Lmax[i] - Rmin[i] for i in range(N + 1)))

Submission status: Accepted

Solution code:
# 解説を確認、このような、最大（最小値）の出し入れが頻繁にあるデータでは、
# 「優先度付きキュー」というデータ構造を用いると容易になるようだ。
# 新規要素の Push & Pop が O(N log N) でできるとのこと。

from heapq import heapify,heappush,heappop

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

a1=a[0:n]
a_m=a[n:2*n]
a2=[ -x for x in a[2*n:3*n] ] # nega_list

a1_sums=[sum(a1)]
a2_sums=[sum(a2)]
heapify(a1)
heapify(a2)

# 左のシマに真ん中のシマを徐々に追加し、都度最小値を取り出す
for aa in a_m:
  heappush(a1,aa)
  p=heappop(a1)
  a1_sums.append(a1_sums[-1]+aa-p)

# 右のシマは都度最大値を取り出す
a_m.reverse()
for aa in a_m:
  heappush(a2,-aa)
  p=heappop(a2)
  a2_sums.append(a2_sums[-1]-aa-p)

max_val=-float("inf")
for i in range(0,n+1):
  max_val=max(max_val,a1_sums[i]+a2_sums[n-i])

print(max_val)

Submission status: Accepted

Solution code:
import heapq
n = int(input())
A = list(map(int,input().split()))
L = A[:n]
R = A[2*n:]
R = list(map(lambda x:-x,R))
sum_l = [sum(L)]
sum_r = [sum(R)]
heapq.heapify(L)
heapq.heapify(R)
for i in range(n):
    elem = A[n+i]
    heapq.heappush(L,elem)
    sum_l.append(sum_l[-1] + elem -heapq.heappop(L))
for i in range(n):
    elem = -A[2*n-1-i]
    heapq.heappush(R,elem)
    sum_r.append(sum_r[-1] + elem -heapq.heappop(R))
ans = -float('inf')
sum_r = sum_r[::-1]
for i in range(len(sum_l)):
    ans = max(ans,sum_l[i] + sum_r[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify,heappushpop

def main():
    rl=sys.stdin.readline
    n=int(rl().strip())
    a=list(map(int,rl().strip().split()))
    b=[-x for x in a]
    b.reverse()
    fl=a[:n]
    fs=sum(fl)
    ll=b[:n]
    ls=sum(ll)
    fdl=[0]*(n+1)
    ldl=[0]*(n+1)
    heapify(fl)
    heapify(ll)
    for i in range(1,n+1):
        fmn=heappushpop(fl,a[n+i-1])
        lmn=heappushpop(ll,b[n+i-1])
        fdl[i]=fdl[i-1]+a[n+i-1]-fmn
        ldl[i]=ldl[i-1]+b[n+i-1]-lmn
    ldl.reverse()
    dif=max([x+y for x,y in zip(fdl,ldl)])
    print(fs+ls+dif)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq

def main():
    rl=sys.stdin.readline
    n=int(rl().strip())
    a=list(map(int,rl().strip().split()))
    b=[-x for x in a]
    b.reverse()
    fl=a[:n]
    fs=sum(fl)
    ll=b[:n]
    ls=sum(ll)
    fdl=[0]*(n+1)
    ldl=[0]*(n+1)
    heapq.heapify(fl)
    heapq.heapify(ll)
    for i in range(1,n+1):
        fmn=heapq.heappushpop(fl,a[n+i-1])
        lmn=heapq.heappushpop(ll,b[n+i-1])
        fdl[i]=fdl[i-1]+a[n+i-1]-fmn
        ldl[i]=ldl[i-1]+b[n+i-1]-lmn
    ldl.reverse()
    dif=max([x+y for x,y in zip(fdl,ldl)])
    print(fs+ls+dif)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop
n = int(input())
a = list(map(int, input().split()))
a1 = a[:n]
heapify(a1)
a2 = a[n:2*n]
a3 = [-i for i in a[2*n:]]
heapify(a3)
b1 = [sum(a1)]
b2 = [sum(a3)]
for i in range(n):
    b1.append(b1[-1]+a2[i]-heappushpop(a1, a2[i]))
    b2.append(b2[-1]-heappushpop(a3, -a2[n-i-1])-a2[n-i-1])
ans = b1[0]+b2[n]
for i in range(n+1):
    ans = max(ans, b1[i]+b2[n-i])
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heapreplace
n = int(input())
a = list(map(int, input().split()))
a1 = a[:n]
heapify(a1)
a2 = a[n:2*n]
a3 = [-i for i in a[2*n:]]
heapify(a3)
b1 = [sum(a1)]
b2 = [sum(a3)]
for i in range(n):
    b1.append(a2[i]-heapreplace(a1, a2[i]))
    b2.append(-heapreplace(a3, -a2[n-i-1])-a2[n-i-1])
for i in range(n):
    b1[i+1] += b1[i]
    b2[i+1] += b2[i]
accu = []
mx = b1[0]
for i in b1:
    mx = max(mx, i)
    accu.append(mx)
ans = -10**16
mx = b2[0]
for i in range(n+1):
    mx = max(mx, b2[i])
    ans = max(ans, mx+accu[n-i])
print(ans)

Submission status: Accepted

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

h1 = copy.deepcopy(A[:N])
x = sorted(A[N:])
h2 = x[N:]
x = x[:N]

now_w = sum(h1) - sum(x)
ans = now_w
used = []
heapq.heapify(h1)
heapq.heapify(h2)
heapq.heapify(used)

for i in range(N):
  now = A[N+i]
  heapq.heappush(h1, now)
  left = heapq.heappop(h1)
  while True:
    right_cand = heapq.heappop(h2)
    if len(used) > 0:
      x = heapq.heappop(used)
      if x == right_cand:
        continue
      else:
        heapq.heappush(used, x)
    break
      
  if right_cand >= now:
    right = right_cand
  else:
    right = now
    heapq.heappush(h2, right_cand)
    heapq.heappush(used, now)
  now_w = now_w - left + 2*now - right
  #print(ans, i, now_w, left, now, right)
  ans = max(ans, now_w)
  
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
N=int(input())
a=list(map(int,input().split()))
ans=-10**18
a_neg=[-x for x in a]
af=a[:N]
ae=a_neg[2*N:]
f_sum=[sum(af)]
e_sum=[sum(ae)]

heapify(af)
for aa in a[N:2*N]:
  heappush(af,aa)
  t=heappop(af)
  f_sum.append(f_sum[-1]+aa-t)

heapify(ae)
for aa in reversed(a[N:2*N]):
  heappush(ae,-aa)
  t=heappop(ae)
  e_sum.append(e_sum[-1]-aa-t)

for f,e in zip(f_sum,reversed(e_sum)):
  ans=max(ans,f+e)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = 10**20
from heapq import heapify, heappop, heappush


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

    L = A[:n]
    R = A[2*n:]
    R = list(map(lambda x:x*(-1), R))
    sum_l = [sum(L)]
    sum_r = [sum(R)]
    heapify(L)
    heapify(R)
    for i in range(n):
        elem = A[n+i]
        heappush(L, elem)
        sum_l.append(sum_l[-1] + elem - heappop(L))
    for i in range(n):
        elem = -A[2*n-1-i]
        heappush(R,elem)
        sum_r.append(sum_r[-1] + elem - heappop(R))
    ans = -INF
    sum_r = sum_r[::-1]
    for i in range(len(sum_l)):
        ans = max(ans, sum_l[i]+sum_r[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n=int(input())
A=list(map(int,input().split()))
A_l=A[:n]
heapq.heapify(A_l)
A_l_sum=[sum(A_l)]
A_m=A[n:2*n]
for i in range(n):
    p=A_m[i]
    heapq.heappush(A_l,p)
    q=heapq.heappop(A_l)
    A_l_sum.append(A_l_sum[-1]+p-q)
A_r=A[2*n:3*n]
for i in range(n):
    A_r[i]*=-1
for i in range(n):
    A_m[i]*=-1
A_m=A_m[::-1]
heapq.heapify(A_r)
A_r_sum=[sum(A_r)]
for i in range(n):
    p=A_m[i]
    heapq.heappush(A_r,p)
    q=heapq.heappop(A_r)
    A_r_sum.append(A_r_sum[-1]+p-q)
ans=-float("INF")
for i in range(n+1):
    ans=max(ans,A_l_sum[i]+A_r_sum[-i-1])
print(ans)