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

N = int(fin())
a_list = [int(elem) for elem in fin().split()]
left, right = a_list[:N], a_list[N:]

thrown_away = [False] * (2 * N)
discarded_items = []

# initialize
right_sum = sum(right)
for i, item in enumerate(right):
    if i < N:
        heappush(discarded_items, (item, i))
        thrown_away[i] = True
        right_sum -= item
    else:
        if item > discarded_items[0][0]:
            old_item, old_idx = heappop(discarded_items)
            thrown_away[old_idx] = False
            heappush(discarded_items, (item, i))
            thrown_away[i] = True
            right_sum += old_item - item


# move partitions and calculate a global maximum
left_sum = sum(left)
heapify(left)
# dirty trick
thrown_away.append(False)
max_score = left_sum - right_sum
for i, item in enumerate(right[:N]):
    if not thrown_away[i]:
        # update right
        updated_idx = -1
        # pick a item which has not moved to the left.
        while thrown_away[updated_idx] == False:
            updated_item, updated_idx = heappop(discarded_items)
        right_sum += updated_item - item
        thrown_away[updated_idx] = False
    else:
        # want to remove item from discarded_items, but it take O(N)
        # instead, set thrown_away[i] = False so as to know this is moved to the left.
        thrown_away[i] = False
    # update left
    if item > left[0]:
        old_item = heappop(left)
        heappush(left, item)
        left_sum += item - old_item
    max_score = max(max_score, left_sum - right_sum)

print(max_score)

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush, heapify

N = int(fin())
a_list = [int(elem) for elem in fin().split()]
left, right = a_list[:N], a_list[N:]

thrown_away = [False] * (2 * N)
discarded_items = []

# initialize
right_sum = sum(right)
for i, item in enumerate(right):
    if i < N:
        heappush(discarded_items, (item, i))
        thrown_away[i] = True
        right_sum -= item
    else:
        if item > discarded_items[0][0]:
            old_item, old_idx = heappop(discarded_items)
            thrown_away[old_idx] = False
            heappush(discarded_items, (item, i))
            thrown_away[i] = True
            right_sum += old_item - item


# move partitions and calculate a global maximum
left_sum = sum(left)
heapify(left)
moved_to_left = [False] * (2 * N + 1)
# dirty trick
moved_to_left[-1] = True
max_score = left_sum - right_sum
for i, item in enumerate(right[:N]):
    if not thrown_away[i]:
        # update right
        updated_idx = -1
        while moved_to_left[updated_idx] == True:
            updated_item, updated_idx = heappop(discarded_items)
        right_sum += updated_item - item
        thrown_away[updated_idx] = False
    else:
        # want to update discarded_items
        moved_to_left[i] = True
    # update left
    if item > left[0]:
        old_item = heappop(left)
        heappush(left, item)
        left_sum += item - old_item
    max_score = max(max_score, left_sum - right_sum)

print(max_score)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
import heapq
hq = a[:N]
fsum = [0]*(N+1)
fsum[0] = sum(hq)
heapq.heapify(hq)
for i in range(N):
    a_ = a[N+i]
    a_min = heapq.heappop(hq)
    if a_min < a_:
        fsum[i+1]=fsum[i]-a_min+a_
        a_min = a_
    else:
        fsum[i+1]=fsum[i]
    heapq.heappush(hq,a_min)
a = [-a[-i-1] for i in range(3*N)]
hq = a[:N]
lsum = [0]*(N+1)
lsum[0] = sum(hq)
heapq.heapify(hq)
for i in range(N):
    a_ = a[N+i]
    a_min = heapq.heappop(hq)
    if a_min < a_:
        lsum[i+1]=lsum[i]-a_min+a_
        a_min = a_
    else:
        lsum[i+1]=lsum[i]
    heapq.heappush(hq,a_min)
lsum.reverse()
ans = -float('inf')
for i in range(N+1):
    diff = fsum[i]+lsum[i]
    if ans < diff:
        ans = diff
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
from collections import deque

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

L = a[:n]
sum_l = [sum(L)]
heapify(L)

ML = a[n:2 * n]
ML = deque(ML)

R = list(map(lambda x: (-1) * x, a[2 * n:]))
sum_r = [sum(R)]  # あとでReverseする
heapify(R)

MR = list(map(lambda x: (-1) * x, a[n:2 * n]))
MR = deque(MR)

for i in range(n):
    add_to_l = ML.popleft()
    heappush(L, add_to_l)
    subtract_to_l = heappop(L)

    t = sum_l[-1] + add_to_l - subtract_to_l
    sum_l.append(t)

# print(sum_l)

for i in range(n):
    add_to_r = MR.pop()
    heappush(R, add_to_r)
    subtract_to_r = heappop(R)

    t = sum_r[-1] + add_to_r - subtract_to_r
    sum_r.append(t)

# print(sum_r)

sum_r = sum_r[::-1]

ans = sum_l[0] + sum_r[0]
for i in range(1, n + 1):
    t = sum_l[i] + sum_r[i]
    ans = max(ans, t)

print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = list(map(int, input().split()))
R = A[:N]
B = [-a for a in A[2 * N:]]
heapq.heapify(R)
heapq.heapify(B)
R_sum = [sum(R)]
B_sum = [sum(B)]

for i in range(N, 2 * N):
    heapq.heappush(R, A[i])
    q = heapq.heappop(R)
    R_sum.append(max(R_sum[-1], R_sum[-1] + A[i] - q))

for i in range(2 * N - 1, N - 1, -1):
    heapq.heappush(B, -A[i])
    q = heapq.heappop(B)
    B_sum.append(max(B_sum[-1], B_sum[-1] - A[i] - q))

num = -float("inf")
for p, q in zip(R_sum, B_sum[::-1]):
    num = max(num, p + q)

print(num)

Submission status: Accepted

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

sumLeft = [0] * (N+1) #A[:N+i]中のN要素の和の最大値のリスト
sumLeft[0] = sum(A[:N])
Aleft = A[:N]
heapq.heapify(Aleft)

sumRight = [0] * (N+1) #A[N+i:]中のN要素の和の最小値のリスト
sumRight[-1] = sum(A[2*N:]) 
Aright = [-1*i for i in A[2*N:]] #最大値をpopするために要素を-1倍しておく
heapq.heapify(Aright)

for i in range(1, N+1):
    a = A[N+i-1]
    b = -1 * A[2*N-i]
    sumLeft[i] = sumLeft[i-1] + a - heapq.heappushpop(Aleft, a)
    sumRight[-1-i] = sumRight[-i] + heapq.heappushpop(Aright, b) - b

score = sumLeft[0] - sumRight[0]
for i in range(1, N+1):
    score = max(score, sumLeft[i] - sumRight[i])
print(score)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappop, heappush

n = ni()
a = list(li())

first = []
second = []

for ai in a[:n]:
    heappush(first, ai)
    
for ai in a[2*n:]:
    heappush(second, -ai)
    
fsum = [sum(first)]
ssum = [sum(second)]
    
ans = fsum[0] + ssum[0]

for i in range(n,2*n):
    heappush(first, a[i])
    fmin = heappop(first)
    fsum.append(fsum[-1] - fmin + a[i])
    
    heappush(second, -a[3*n-i-1])
    smax = heappop(second)
    ssum.append(ssum[-1] - smax - a[3*n-i-1])
    
ssum = ssum[::-1]

for fs,ss in zip(fsum, ssum):
    ans = max(ans, fs+ss)
    
print(ans)

Submission status: Accepted

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

a1 = a[:n]
ax = a[n:2*n]
a2 = list(map(lambda x: -x, a[2*n:]))
#print('a2', a2)

sum_a1 = sum(a1)
fdif1 = [sum_a1]
heapq.heapify(a1)
for i in range(n):
    p = heapq.heappushpop(a1,ax[i])
    fdif1.append(fdif1[-1]+ax[i]-p)
    
sum_a2 = sum(a2)
fdif2 = [sum_a2]
heapq.heapify(a2)
#print('a2', a2)
for i in range(n):
    p = heapq.heappushpop(a2,-ax[-1-i])
    fdif2.append(fdif2[-1]-ax[-1-i]-p)
fdif2.reverse()

fdif = [fdif1[i]+fdif2[i] for i in range(n+1)]
print(max(fdif))

Submission status: Accepted

Solution code:
import heapq

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

ans = -10**15
h1 = a[:n]
h2 = [-a[i] for i in range(2*n, 3*n)]
heapq.heapify(h1)
heapq.heapify(h2)

h1sum = sum(a[:n])
h2sum = sum(a[2*n:])

box1 = [h1sum]
box2 = [h2sum]

for i in range(1, n+1):
    heapq.heappush(h1, a[n+i-1])
    h1sum += a[n+i-1] - heapq.heappop(h1)
    box1.append(h1sum)

for i in range(1, n+1):
    heapq.heappush(h2, -a[2*n-i])
    h2sum += a[2*n-i] - (-heapq.heappop(h2))
    box2.append(h2sum)

for i in range(n+1):
    ans = max(ans, box1[i] - box2[n-i])

print(ans)

Submission status: Accepted

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

lsum = sum(src[:N])
lmem = [lsum]
lq = src[:N][:]
heapq.heapify(lq)
for a in src[N:2*N]:
    if a <= lq[0]:
        lmem.append(lmem[-1])
    else:
        lsum += a - heapq.heappop(lq)
        heapq.heappush(lq, a)
        lmem.append(lsum)

rq = [-a for a in src[-N:]]
rsum = sum(rq)
rmem = [rsum]
heapq.heapify(rq)
for a in reversed(src[N:2*N]):
    if -a <= rq[0]:
        rmem.append(rmem[-1])
    else:
        rsum += -a - heapq.heappop(rq)
        heapq.heappush(rq, -a)
        rmem.append(rsum)

ans = -float('inf')
for l,r in zip(lmem, rmem[::-1]):
    ans = max(ans, l+r)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop
N, *A = map(int, open(0).read().split())
def f(L):
    q = L[:N]
    heapify(q)
    s = sum(q)
    yield s
    for e in L[N:2 * N]:
        s += e - heappushpop(q, e)
        yield s
print(max(map(sum, zip(f(A), list(f([-a for a in A[::-1]]))[::-1]))))

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop
N, *a = map(int, open(0).read().split())

hq1 = a[:N]
hq2 = [-ai for ai in a[-N:]]

heapify(hq1)
heapify(hq2)

sum1 = [sum(hq1)]
sum2 = [sum(hq2)]
for k in range(N, 2 * N):
    sum1.append(sum1[-1] + a[k] - heappushpop(hq1, a[k]))
    sum2.append(sum2[-1] - a[-k - 1] - heappushpop(hq2, -a[-k - 1]))

print(max(map(sum, zip(sum1, sum2[::-1]))))

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop
n, *a = map(int, open(0).read().split())
q = a[:n]
heapify(q)
x = [sum(q)]
for k in range(n, 2 * n):
    v = heappushpop(q, a[k])
    x.append(x[-1] + a[k] - v)
a = a[::-1]
q = [-v for v in a[:n]]
heapify(q)
y = [-sum(q)]
for k in range(n, 2 * n):
    v = -heappushpop(q, -a[k])
    y.append(y[-1] + a[k] - v)
print(max(v - w for v, w in zip(x, y[::-1])))

Submission status: Accepted

Solution code:
import heapq
N = int( input())
A = list( map( int, input().split()))
fsum = [0]*(N+1)
bsum = [0]*(N+1)
forward = A[:N]
back = A[2*N:]
back = list(map( lambda x:-x, back))
heapq.heapify(forward)
heapq.heapify(back)
fsum[0] = sum(forward)
fsumnow = fsum[0]
bsum[N] = -sum(back)
bsumnow = bsum[N]
for i in range(1,N+1):
    heapq.heappush(forward, A[N+i-1])
    fsumnow += A[N+i-1]
    fsumnow -= heapq.heappop(forward)
    fsum[i] = fsumnow
    heapq.heappush(back, -A[2*N-i])
    bsumnow += A[2*N-i]
    bsumnow += heapq.heappop(back)
    bsum[N-i] = bsumnow
ans = fsum[0] - bsum[0]
for i in range(1,N+1):
    ans = max(ans, fsum[i] - bsum[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = [int(x) for x in input().split()]
B = [[0, 0] for i in range(N + 1)]
A1 = A[:N]
B[0][0] = sum(A1)
heapq.heapify(A1)
for i in range(N):
  B[i + 1][0] = B[i][0]
  B[i + 1][0] += A[N + i]
  heapq.heappush(A1, A[N + i])
  B[i + 1][0] -= heapq.heappop(A1)
A2 = [-a for a in A[2 * N:]]
B[N][1] = -sum(A2)
heapq.heapify(A2)
for i in range(N):
  B[N - i - 1][1] = B[N - i][1]
  B[N - i - 1][1] += A[2 * N - i - 1]
  heapq.heappush(A2, -A[2 * N - i - 1])
  B[N - i - 1][1] += heapq.heappop(A2)
ans = - 10 ** 18
for b0, b1 in B:
  ans = max(b0 - b1, ans)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n = int(input())
a = list(map(int,input().split()))
aka = a[:n]
heapq.heapify(aka)
akasum = [0] * (n+1)
akasum[0] = sum(aka)
ao = a[2*n:]
aosum = [0] * (n+1)
aosum[-1] = sum(ao)
for i in range(len(ao)):
  ao[i] = -ao[i]
heapq.heapify(ao)
for i in range(n,2*n):
  b = heapq.heappop(aka)
  if b >= a[i]:
    heapq.heappush(aka, b)
    akasum[i-n+1] = akasum[i-n] 
  else:
    heapq.heappush(aka, a[i])
    akasum[i-n+1] = akasum[i-n] + a[i] - b
  b = heapq.heappop(ao)
  if b >=  -a[-i-1]:
    heapq.heappush(ao, b)
    aosum[-i+n-2] = aosum[-i+n-1]
  else:
    heapq.heappush(ao, -a[-i-1])
    aosum[-i+n-2] = aosum[-i+n-1] + a[-i-1] + b
ans = - float("inf")
for i in range(n+1):
  kota = akasum[i] - aosum[i]
  ans = max(kota,ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = a[n:2*n]

import heapq

q = a[:n]
heapq.heapify(q)

res = [0]*(n+1)
res[0] = sum(q)
for i, x in enumerate(b):
    heapq.heappush(q, x)
    y = heapq.heappop(q)
    res[i+1] = res[i]+x-y

b.reverse()
q = [-x for x in a[2*n:]]
heapq.heapify(q)
s = -sum(q)
res[-1] -= s

for i, x in enumerate(b):
    heapq.heappush(q, -x)
    y = heapq.heappop(q)
    s += x+y
    res[-2-i] -= s

print(max(res))

Submission status: Accepted

Solution code:
import heapq
N=int(input())
a=[int(i) for i in input().split()]
#ans[i]-> k=i+N,
red=[0 for i in range(N+1)]
blue=[0 for i in range(N+1)]
r=list(a[:N])
b=list([-i for i in a[2*N:]])
heapq.heapify(r)
heapq.heapify(b)
red[0]=sum(a[:N])
for i in range(N):
    k=i+N
    tmp1=a[k]
    heapq.heappush(r,a[k])
    tmp2=heapq.heappop(r)
    red[i+1]=red[i]-tmp2+tmp1
blue[-1]=sum(a[2*N:])
for i in range(N)[::-1]:
    k=i+N
    tmp1=a[k]
    heapq.heappush(b,-a[k])
    tmp2=-heapq.heappop(b)
    blue[i]=blue[i+1]-tmp2+tmp1
ans=[red[i]-blue[i] for i in range(N+1)]
print(max(ans))

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(N, A):
    q = []
    lc = [0]*(N+1)
    for i in range(N):
        heapq.heappush(q, A[i])
        lc[0] += A[i]
    for i in range(N, 2*N):

        a = heapq.heappushpop(q, A[i])
        lc[i-N+1] = lc[i-N] + A[i] - a

    q = []
    rc = [0] * (N+1)
    for i in range(3*N-1, 2*N-1, -1):
        heapq.heappush(q, -A[i])
        rc[N] += A[i]
    for i in range(2*N-1, N-1, -1):
        a = -heapq.heappushpop(q, -A[i])
        rc[i-N] = rc[i-N+1] + A[i] - a

    return max(map(lambda x: x[0]-x[1], zip(lc, rc)))


def main():
    N = read_int()
    A = read_int_n()

    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a1 = a[:n]
heapq.heapify(a1)
a1_sum = sum(a1)
a1_sums = [a1_sum]
for i in range(n, 2*n):
    a1_min = heapq.heappop(a1) # pop the smallest value from a1
    if a[i] > a1_min:
        heapq.heappush(a1, a[i])
        a1_sum = a1_sum - a1_min + a[i]
    else:
        heapq.heappush(a1, a1_min)
    a1_sums.append(a1_sum)

a2 = a[-n:]
a2_sum = sum(a2)
a2_sums = [a2_sum]
a2_inv = [-aa for aa in a2]
heapq.heapify(a2_inv)
for i in range(2*n-1, n-1, -1):
    a2_max = -heapq.heappop(a2_inv) # pop the largest value from a2
    if a[i] < a2_max:
        heapq.heappush(a2_inv, -a[i])
        a2_sum = a2_sum - a2_max + a[i]
    else:
        heapq.heappush(a2_inv, -a2_max)
    a2_sums.append(a2_sum)
a2_sums = a2_sums[::-1] # reverse order

ans = a1_sums[0] - a2_sums[0]
for a1_s, a2_s in zip(a1_sums, a2_sums):
    ans = max(ans, a1_s-a2_s)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

q_b = aa[:N]
q_a = list(map(lambda x: -x, aa[2*N:]))

sum_b = [sum(q_b)]
sum_a = [sum(q_a)]

heapq.heapify(q_b)
heapq.heapify(q_a)

sum = sum_b[0]
for i in range(N,2*N):
	push = aa[i]
	pop = heapq.heappushpop(q_b,push)
	sum = sum - pop + push
	sum_b.append(sum)

sum = sum_a[0]
for i in range(2*N-1,N-1,-1):
	push = -aa[i]
	pop = heapq.heappushpop(q_a,push)
	sum = sum - pop + push
	sum_a.append(sum)

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

print(ans)

Submission status: Accepted

Solution code:
#3Nのうち前半部Nはどのような選択をしても前半部にしか所属できない
#3Nのうち後半部2N->3Nはどのような選択をしても後半部にしか所属できない。
#3Nのうち中盤部のN->2Nについて、前半に加えるか、後半に加えるか、加えないかの選択が発生する。
#中盤部をリストとする数列のどこまでをそれぞれに加えるかを考える。
#つまりそれぞれN~2NまでN通りの前後半部を作り、差分を調べる。
#それぞれについて最大最小部分をソート計算ではTLEだが、heapqを使えばO(N log N)？で実現できそう
#N->2Nまでを使った前半部の最大値リスト生成O(NlogN)
#N->2Nまでを使った後半部の最小値リスト生成O(NlogN)
#それぞれの差分を取って最大値となる答えを算O(N)なので、間に合いそう。

import heapq

N=int(input())
A=[int(x) for x in input().split()]

#前半部のheapqを生成
H=A[:N]
heapq.heapify(H)

#N->2Nを使った前半部の最大値計算
S=sum(A[:N])
F=[S]
for i in range(N,2*N):
  a=heapq.heappop(H)
  if a < A[i]:
    heapq.heappush(H, A[i])
    S+=(A[i]-a)
  else:
    heapq.heappush(H, a)
  F.append(S)

#後半部のheapqを生成
H=[int(x)*-1 for x in A[2*N:]]
heapq.heapify(H)

#同様にN->2Nを使った後半部の最小値計算
S=sum(A[2*N:])
F2=[S]
for i in range(2*N-1,N-1,-1):
  a=heapq.heappop(H)*(-1)
  if a > A[i]:
    heapq.heappush(H, A[i]*(-1))
    S+=(A[i]-a)
  else:
    heapq.heappush(H, -a)
  F2.append(S)
  
#差分計算
F2=F2[:][::-1]
ans=(10**14)*(-1)

for i in range(N+1):
  ans=max(ans,F[i]-F2[i])
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify,heappush, heappop

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

q=A[:N]
heapify(q)
q_sum=sum(q)

B=[ float("-inf") for i in range(3*N)]
B[N-1]=q_sum

for i in range(N,2*N):
	x=A[i]
	if x>q[0]:
		tmp=heappop(q)
		q_sum-=tmp
		q_sum+=x
		heappush(q,x)
	B[i]=q_sum

q=map(lambda x: x*-1, A[2*N:] )
heapify(q)

q_sum=sum(q)*-1
B[2*N-1]-=q_sum

for i in range(2*N-1,N-1,-1):
	x=A[i]*-1
	if q[0]<x:
		tmp=heappop(q)
		q_sum-=tmp*-1
		q_sum+=x*-1
		heappush(q,x)
	B[i-1]-=q_sum

print max(B)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
n=int(input())
a=list(map(int,input().split()))
l=[]
for v in a[:n]:
  heappush(l,v)
suml=[sum(a[:n])]
for i in range(n):
  suml.append(suml[i]+a[n+i])
  heappush(l,a[n+i])
  suml[i+1]-=heappop(l)
r=[]
for v in a[2*n:]:
  heappush(r,(10**10-v,v))
sumr=[sum(a[2*n:])]
for i in range(n):
  sumr.append(sumr[i]+a[2*n-i-1])
  heappush(r,(10**10-a[2*n-i-1],a[2*n-i-1]))
  _,t=heappop(r)
  sumr[i+1]-=t
ans=-10**20
for i in range(n+1):
  ans=max(ans,suml[i]-sumr[n-i])
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = list(map(int, input().split()))
L = sorted(A[:2*N])
sumL = sum(L[N:])
R = sorted(A[N:])
sumR = sum(R[:N])
AL = [sumL]
p = N
BL = [False] * (2*N)
for a in reversed(A[N:2*N]):  # sumLはだんだん減る
    ind = bisect.bisect_left(L, a)
    if BL[ind] != False:
        BL[ind] += 1
        ind += BL[ind] - 1
    if ind >= p:
        sumL -= L[ind]
        p -= 1
        while BL[p] != False:
            p -= 1
        sumL += L[p]
    AL.append(sumL)
    BL[ind] = 1
AR = [sumR]
p = N-1
BR = [False] * (2*N)
for a in A[N:2*N]:  # sumRはだんだん増える
    ind = bisect.bisect_left(R, a)
    if BR[ind] != False:
        BR[ind] += 1
        ind += BR[ind] - 1
    if ind <= p:
        sumR -= R[ind]
        p += 1
        while BR[p] != False:
            p += 1
        sumR += R[p]
    AR.append(sumR)
    BR[ind] = 1
AL.reverse()
C = [AL[i] - AR[i] for i in range(N+1)]
print(max(C))

Submission status: Accepted

Solution code:
import heapq
n = int(input())
a,b = [int(i) for i in input().split()],[]
for i in a: b.append(-i)
x,y = a[:n],b[2*n:]
heapq.heapify(x)
heapq.heapify(y)
num,num2 = sum(a[:n]),sum(a[2*n:])
a2,b2 = [num],[num2]
for i in range(n+1,2*n+1):
	j = 3*n+1-i
	num += a[i-1]-heapq.heappushpop(x,a[i-1])
	num2 += a[j-1]+heapq.heappushpop(y,b[j-1])
	a2.append(num)
	b2.append(num2)
b2,ans = b2[::-1],-float("inf")
for i in range(n+1): ans = max(ans,a2[i]-b2[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

# 準備
left, right = A[:N], A[-N:]

right = list(map(lambda x: -x, right))
left_sum, right_sum = [sum(left)], [-sum(right)]
heapq.heapify(left)
heapq.heapify(right)

# left処理
for i in range(N, 2*N):
    heapq.heappush(left, A[i])
    low = heapq.heappop(left)
    left_sum.append(left_sum[-1] + A[i] - low)

# right処理
for i in range(2*N-1, N-1, -1):
    heapq.heappush(right, -A[i])
    high = -heapq.heappop(right)
    right_sum.append(right_sum[-1] + A[i] - high)

# rightを逆順にしてleftの挙動と合わせる
right_sum = right_sum[::-1]

ans = max([l-r for l, r in zip(left_sum, right_sum)])
print(ans)

Submission status: Accepted

Solution code:
import heapq

N=int(input())
A=[int(x) for x in input().split()]

a=A[:N]
b=A[-N:]
c=A[N:-N]
res=[sum(a)]


heapq.heapify(a)
for i in range(N):
  heapq.heappush(a,c[i])
  k=heapq.heappop(a)
  res.append(res[-1]+c[i]-k)

cnt=sum(b)
for i in range(N):
  b[i]*=-1

max_ans=res[N]-cnt

heapq.heapify(b)
for i in range(N-1,-1,-1):
  heapq.heappush(b,-c[i])
  k=heapq.heappop(b)
  res[i]-=(cnt+c[i]+k)
  cnt=cnt+c[i]+k
  max_ans=max(max_ans,res[i])

print(max_ans)

Submission status: Accepted

Solution code:
def d_3N_Numbers(N, A):
    import heapq
    left = A[:N]
    heapq.heapify(left)
    # heappopがキューの最小値を取り出す一方、rightからは最大値を取り出してほしいので、
    # -1を掛ける
    right = [-i for i in A[2 * N:]]
    heapq.heapify(right)
    left_sum = [sum(left)]
    right_sum = [-sum(right)]  # 定義で-1を付けた都合上

    # 同じ要素をleftとrightで取り合っても、相殺されるので問題ない
    for k in range(N, 2 * N):
        heapq.heappush(left, A[k])
        v = heapq.heappop(left)
        left_sum.append(left_sum[-1] + A[k] - v)
    for k in range(2 * N - 1, N - 1, -1):
        # -1をかけるのは、rightの定義の都合上
        heapq.heappush(right, -A[k])
        v = heapq.heappop(right)
        right_sum.append(right_sum[-1] + A[k] - (-v))
    right_sum = right_sum[::-1]
    ans = []
    for a, b in zip(left_sum, right_sum):
        ans.append(a - b)
    return max(ans)

N = int(input())
A = [int(i) for i in input().split()]
print(d_3N_Numbers(N, A))

Submission status: Accepted

Solution code:
n=int(input())
import heapq
a=map(int, raw_input().split())
q=a[:n]
heapq.heapify(q)
x=[sum(q)]
for k in range(n,2*n):
    v=heapq.heappushpop(q,a[k])
    x.append(x[-1]+a[k]-v)
a=a[::-1]
q=[-v for v in a[:n]]
heapq.heapify(q)
y=[-sum(q)]
for k in range(n,2*n):
    v=-heapq.heappushpop(q,-a[k])
    y.append(y[-1]+a[k]-v)
print(max(v-w for v,w in zip(x,y[::-1])))

Submission status: Accepted

Solution code:
import itertools
import datetime
from heapq import heapify,heappush,heappop



N=input()
a=[]
a=map(int, raw_input().split())
a1=a[:N]
#print a1


heapify(a1)

l1=[]
sum_a1=sum(a1)
l1.append(sum_a1)



# Max
for i in range(N,2*N):
	if a[i]>a1[0]:
		sum_a1=sum_a1+a[i]-a1[0]
		heappop(a1)
		heappush(a1, a[i])

	l1.append(sum_a1)

 

l2=[]
a2=[ -x for x in a[2*N:]]
heapify(a2)
sum_a2=-1*sum(a2)
l2.append(sum_a2)

# Min
for i in reversed(range(N,2*N)):
	if a[i]<-1*a2[0]:
		sum_a2=sum_a2+a[i]-(-1*a2[0])
		heappop(a2)
		heappush(a2,-1*a[i])
	l2.append(sum_a2)


ans=[]
for i in range(N+1):
	heappush(ans, -1*(l1[i]-l2[N-i]))

print ans[0]*-1

Submission status: Accepted

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

N=input()
a=[]
a=map(int, raw_input().split())
a1=a[0:N]
#print a1

heapify(a1)

l1=[]
sum_a1=sum(a1)
l1.append(sum_a1)

# Max
for i in range(N,2*N):
	if a[i]>a1[0]:
		sum_a1=sum_a1+a[i]-a1[0]
		heappop(a1)
		heappush(a1, a[i])

	l1.append(sum_a1)


l2=[]
a2=[ -x for x in a[2*N:3*N]]
heapify(a2)
sum_a2=-1*sum(a2)
l2.append(sum_a2)

# Min
for i in reversed(range(N,2*N)):
	if a[i]<-1*a2[0]:
		sum_a2=sum_a2+a[i]-(-1*a2[0])
		heappop(a2)
		heappush(a2,-1*a[i])
	l2.append(sum_a2)


ans=[]
for i in range(N+1):
	ans.append(l1[i]-l2[N-i])

print max(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc062.contest.atcoder.jp/tasks/arc074_b

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


def solve(A, N):
    red_pq = []
    blue_pq = []

    for a in A[:N]:
        heappush(red_pq, a)
    red_total = sum(A[:N])

    blue_total = 0
    for a in A[2*N:]:
        heappush(blue_pq, -a)
        blue_total += a

    blue_lut = [0] * (3*N)
    blue_lut[2*N] = blue_total
    for k in range(2*N - 1, N - 1, -1):
        t1 = A[k]
        heappush(blue_pq, -t1)
        t2 = heappop(blue_pq)
        blue_total += (t1 + t2)
        blue_lut[k] = blue_total

    best_ans = red_total - blue_total

    for k in range(N, 2*N):
        t1 = A[k]
        heappush(red_pq, t1)
        t2 = heappop(red_pq)
        red_total += (t1 - t2)

        ans = red_total - blue_lut[k+1]
        best_ans = max(best_ans, ans)

    return best_ans


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    result = solve(A, N)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import heapq

N = int(input())
a = [int(n) for n in input().split()]
former = a[:N]

heapq.heapify(former)

former_sum = [sum(former)]


for k in range(N):
  heapq.heappush(former, a[N+k])
  former_sum.append(former_sum[k]+a[N+k]-heapq.heappop(former))

a = [n * (-1) for n in a]
latter = a[2*N:]
heapq.heapify(latter)
latter_sum = [sum(latter)]

for k in range(N):
  heapq.heappush(latter, a[2*N-k-1])
  latter_sum.append(latter_sum[k] + a[2*N-k-1] - heapq.heappop(latter))

res = [former_sum[k] + latter_sum[N-k] for k in range(N+1)]

print(max(res))

Submission status: Accepted

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

a1h = a[:N]
a2h = [-ai for ai in a[2 * N:]]

import heapq
heapq.heapify(a1h)
heapq.heapify(a2h)

sum1 = [sum(a1h)]
sum2 = [sum(a2h)]
for k in range(N, 2 * N):
    sum1.append(sum1[-1] + a[k] - heapq.heappushpop(a1h, a[k]))
    sum2.append(sum2[-1] + -a[-k - 1] - heapq.heappushpop(a2h, -a[-k - 1]))

print(max(map(sum, zip(sum1, sum2[::-1]))))

Submission status: Accepted

Solution code:
import heapq

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

q = a[:N]
heapq.heapify(q)
x = [sum(q)]

for k in range(N, 2*N):
    ## in : a[k], out : v
    out = heapq.heappushpop(q, a[k])
    x.append(x[-1]+a[k]-out)
    
a = a[::-1]    
q = [-v for v in a[:N]]
heapq.heapify(q)
y = [-sum(q)]
for k in range(N, 2*N):
    out = -heapq.heappushpop(q, -a[k])
    y.append(y[-1]+a[k]-out)
    
print(max(v-w for v,w in zip(x, y[::-1])))

Submission status: Accepted

Solution code:
import heapq

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

red, blue = a[:n], [-1*i for i in a[2*n:]]
sr, sb = sum(red), sum(blue)

results = [0] * (n + 1)
results[0] = sr
results[-1] = sb

heapq.heapify(red)
heapq.heapify(blue)

for k in range(n, 2*n):
    v = a[k]
    p = heapq.heappushpop(red, v)
    sr += v - p
    results[k-n+1] += sr

for k in range(2*n-1, n-1, -1):
    v = -1 * a[k]
    p = heapq.heappushpop(blue, v)
    sb += v - p
    results[k-n] += sb

print(max(results))

Submission status: Accepted

Solution code:
import heapq

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

red = a[:n]
sr = sum(red)
sum_red = {n: sr}
heapq.heapify(red)
# print(red)

blue = [-1 * i for i in a[2*n:]]
sb = sum(blue)
sum_blue = {2 * n: sb}
heapq.heapify(blue)
# print(blue)

for k in range(n, 2 * n):
    popped_red = heapq.heappushpop(red, a[k])
    sr += a[k] - popped_red
    sum_red[k + 1] = sr
    # print(popped_red, red, sr, sum_red)

for k in range(2 * n - 1, n - 1, -1):
    popped_blue = heapq.heappushpop(blue, -1  * a[k])
    sb += -1 * a[k] - popped_blue
    sum_blue[k] = sb
    # print(popped_blue, blue, sb, sum_blue)

ans = -1 * float('inf')
for k in range(n, 2 * n + 1):
    ans = max(ans, sum_red[k] + sum_blue[k])
    

print(ans)

Submission status: Accepted

Solution code:
import heapq
N=int(input())
a=list(map(int,input().split()))
earl=[]
late=[]
for i in range(N):
  heapq.heappush(earl,a[i])
  heapq.heappush(late,-a[2*N+i])
E=0
L=0
for i in range(N):
  E+=a[i]
  L-=a[2*N+i]
e=[E]*(N+1)
l=[L]*(N+1)
for i in range(N):
  e[i+1]=e[i]+a[N+i]-heapq.heappushpop(earl,a[N+i])
  l[N-1-i]=l[N-i]-a[2*N-1-i]-heapq.heappushpop(late,-a[2*N-1-i])

ans=e[N]+l[N]
for i in range(N):
  ans=max(ans,e[i]+l[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
array = [int(n) for n in input().split()]
import copy
import heapq
lst = [None for i in range(N + 1)]
left_lst = copy.deepcopy(lst)
right_lst = copy.deepcopy(lst)
left_array = array[:N]
right_array= [-n for n in array[-N:]]
l_sum = sum(left_array)
r_sum = sum(right_array)
heapq.heapify(left_array)
heapq.heapify(right_array)
left_lst[0] = l_sum
right_lst[0] = r_sum

for k in range(N, 2 * N):
    new_a, new_b = array[k], array[-k - 1]*-1
    heapq.heappush(left_array,new_a)
    heapq.heappush(right_array,new_b)
    old_a = heapq.heappop(left_array)
    l_sum += (new_a - old_a)
    left_lst[k - N + 1] = l_sum
    old_b = heapq.heappop(right_array)
    r_sum += (new_b - old_b)
    right_lst[k - N + 1] = r_sum
lst = [ a + b for a, b in zip(left_lst, list(reversed(right_lst)))]
print(max(lst))