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:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from heapq import heapify, heapreplace 

N = int(input())
A = inpl()
L = A[:N]
M = A[N:2*N]
R = [-a for a in A[2*N:]]
ans = sum(L) + sum(R)
heapify(L)
heapify(R)


i = 0
j = N+1

S = [0]*(N+1)

s = 0
for i, m in enumerate(M):
    if m > L[0]:
        s += m - heapreplace(L, m)
    S[i+1] += s

s = 0
for i, m in enumerate(M[::-1]):
    if m < -R[0]:
        s += -m - heapreplace(R, -m)
    S[-i-2] += s

ans += max(S)
print(ans)

Submission status: Accepted

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

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

'''
方針
N/3から2N/3まで動かして、その時の差分の最大値を返す
前半では、要素を追加して、最小値を取り出す
後半では、要素を
'''


import heapq
q = [] # プライオリティキュー minヒープ
heapq.heappush(q, 1) # 1をpush
#q
#[1]
heapq.heappush(q, 2) # 2をpush
#q
#[1, 2] # 1より2の方が優先度が低いので先頭以外に追加される
heapq.heappush(q, 0) # 0をpush

q1 = []
sum_q1 = 0
sum_q1s = []

for i in range(0,N,1):
    heapq.heappush(q1, As[i])
    sum_q1 += As[i]
sum_q1s.append(sum_q1)
for i in range(N,2*N,1):
    heapq.heappush(q1, As[i])
    pop_q1 = heapq.heappop(q1)
    sum_q1 = sum_q1 - pop_q1 + As[i]
    sum_q1s.append(sum_q1)

q2 = []
sum_q2 = 0
sum_q2s = []

for i in range(2*N,3*N,1):
    heapq.heappush(q2, -As[i])
    sum_q2 += -As[i]
sum_q2s.append(sum_q2)
for i in range(2*N-1,N-1,-1):
    heapq.heappush(q2, -As[i])
    pop_q2 = heapq.heappop(q2)
    sum_q2 = sum_q2 - pop_q2 - As[i]
    sum_q2s.append(sum_q2)

max_value = -float('inf')
for i in range(0,N+1,1):
    max_value = max(max_value, sum_q1s[i] + sum_q2s[N-i])

print(max_value)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from heapq import heapify, heappop, heappush
from copy import deepcopy

N = int(input())
A = inpl()

before = deepcopy(A[:N])
heapify(before)
middle = A[N:-N]
after = [-a for a in A[-N:]]
heapify(after)

sb = sum(A[:N])
sa = -sum(A[-N:])

SB = [sb]
SA = [sa]

for m in middle:
    b = heappop(before)
    if b < m:
        heappush(before, m)
        sb += m - b
    else:
        heappush(before, b)
    SB.append(sb)    

for m in middle[::-1]:
    m = -m
    a = heappop(after)
    if a < m:
        heappush(after, m)
        sa += m - a
    else:
        heappush(after, a)
    SA.append(sa) 

    
print(max([b+a for b, a in zip(SB, SA[::-1])]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from heapq import heappush, heappushpop

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

pq1 = []
pq2 = []
for i in range(N):
    heappush(pq1, A[i])
    heappush(pq2, -A[-i - 1])

acc1 = [sum(pq1)] * (N + 1)     # acc1 > 0
acc2 = [sum(pq2)] * (N + 1)     # acc2 < 0
for (i, a) in enumerate(A[N:2 * N]):
    acc1[i + 1] = acc1[i] + a - heappushpop(pq1, a)
for (i, a) in enumerate(A[N:2 * N][::-1]):
    acc2[-i - 2] = acc2[-i - 1] + (-a) - heappushpop(pq2, -a)

ans = float('-inf')
for x, y in zip(acc1, acc2):
    ans = max(ans, x - (-y))

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**9
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    b = []
    c = []
    for i in range(n):
        heapq.heappush(b, a[i])
        heapq.heappush(c, -a[i+n*2])
    sb = sum(b)
    sc = sum(c)
    ba = {}
    ba[n-1] = sb
    for i in range(n):
        t = heapq.heappop(b)
        if a[n+i] > t:
            sb -= t
            heapq.heappush(b, a[n+i])
            sb += a[n+i]
        else:
            heapq.heappush(b, t)
        ba[n+i] = sb

    ca = {}
    ca[n*2-1] = sc
    for i in range(n-1,-1,-1):
        t = heapq.heappop(c)
        if -a[n+i] > t:
            sc -= t
            heapq.heappush(c, -a[n+i])
            sc -= a[n+i]
        else:
            heapq.heappush(c, t)
        ca[n+i-1] = sc


    r = -inf
    for k in ba.keys():
        tr = ba[k] + ca[k]
        if tr > r:
            r = tr

    return r



print(main())

Submission status: Accepted

Solution code:
import sys, heapq

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = na()

ln = a[0:n]
rn = [-x for x in a[2*n: 3*n]]
heapq.heapify(ln)
heapq.heapify(rn)
ls = sum(ln)
rs = sum(rn)

lb = [ls]
rb = [rs]
for i in range(1, n+1):
    heapq.heappush(ln, a[n-1+i])
    vl = heapq.heappop(ln)
    ls = ls - vl + a[n-1+i]
    lb.append(ls)

    heapq.heappush(rn, -a[2*n-i])
    vr = heapq.heappop(rn)
    rs = rs - vr - a[2*n-i]
    rb.append(rs)

ans = -float('inf')
for i in range(n+1):
    ans = max(ans, lb[i] + rb[n-i])

print (ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop

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

former = aa[:n]
latter = [-a for a in aa[2 * n:]]
fs = sum(former)
ls = sum(latter)
heapify(former)
heapify(latter)

results = [0] * (n + 1)
results[0] = fs
results[-1] = ls

for i in range(n, 2 * n):
    a = aa[i]
    k = heappushpop(former, a)
    fs += a - k
    results[i - n + 1] += fs

for i in range(2 * n - 1, n - 1, -1):
    a = -aa[i]
    k = heappushpop(latter, a)
    ls += a - k
    results[i - n] += ls

print(max(results))

Submission status: Accepted

Solution code:
import heapq
n = int(input())
xs = list(map(int, input().split()))
head = [(x, x) for x in xs[:n]]
heapq.heapify(head)
body = xs[n:-n]
tail = [(-x, x) for x in xs[-n:]]
heapq.heapify(tail)

def f(heap, body, sign, initial):
    answer = [initial]
    acc = initial
    for b in body:
        heapq.heappush(heap, (sign*b, b))
        _, x = heapq.heappop(heap)
        acc = acc + b - x
        answer.append(acc)
    return answer
 
print(max(x - y for x, y in zip(
    f(head, body, 1, sum(xs[:n])),
    f(tail, body[::-1], -1, sum(xs[-n:]))[::-1])))

Submission status: Accepted

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

inf = 1<<60

def solve():
    n = int(input())
    a = [int(i) for i in input().split()]

    ps = [sum(a[:n])]
    minhp = a[:n]
    heapify(minhp)

    for i in range(n):
        heappush(minhp, a[n + i])
        x = heappop(minhp)
        ps.append(ps[-1] + a[n + i] - x)

    ss = [sum(a[2*n:])]
    maxhp = [-ai for ai in a[2*n:]]
    heapify(maxhp)

    for i in range(n):
        heappush(maxhp, -a[2*n - 1 - i])
        x = -heappop(maxhp)
        ss.append(ss[-1] + a[2*n - 1 - i] - x)

    ans = -inf

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

    print(ans)

if __name__ == '__main__':  
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    a = ILI()
    return (N, a)


def solve(N, a):
    a_lef = a[0: N]
    a_rig = [-i for i in a[2 * N: 3 * N]]
    heapq.heapify(a_lef)
    heapq.heapify(a_rig)
    sum_lef = sum(a_lef)
    sum_rig = sum(a_rig)
    l_sum_lef = [sum_lef]
    l_sum_rig = [sum_rig]
    
    for i in range(1, N + 1):
        heapq.heappush(a_lef, a[N - 1 + i])
        lef_pop = heapq.heappop(a_lef)
        sum_lef += a[N - 1 + i] - lef_pop
        l_sum_lef.append(sum_lef)
        
        heapq.heappush(a_rig, -a[2 * N - i])
        rig_pop = heapq.heappop(a_rig)
        sum_rig += -a[2 * N - i] - rig_pop
        l_sum_rig.append(sum_rig)

    ans = -INF

    for i in range(N + 1):
        num_dif = l_sum_lef[i] + l_sum_rig[N - i]
        ans = max(ans, num_dif)

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#coding:utf-8

from heapq import *

def score(input_list):
    s = sum(input_list[:N])
    score_list = [s]
    l = input_list[:N]
    heapify(l)

    for val in input_list[N:2 * N]:
        s -= heappushpop(l, val)
        s += val
        score_list.append(s)

    return score_list

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split(" ")))
    B = list(map(lambda x : -x, reversed(A)))

    max_score = 0
    left_score = score(A)
    right_score = reversed(score(B))
    score_list = map(lambda x,y : x + y, left_score, right_score)
    print (max(score_list))

Submission status: Accepted

Solution code:
from heapq import *
r=reversed
N=int(input())
A=list(map(int,input().split()))
def w(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(w(A),r(list(w([-a for a in r(A)])))))))

Submission status: Accepted

Solution code:
from heapq import *
 
N = int(input())
A = list(map(int, input().split()))
B = list(map(lambda x: -x, reversed(A)))

def left_scores(L):
  s = sum(L[:N])
  scores = [s]
  q = L[:N]
  heapify(q)

  for e in L[N:2*N]:
    s -= heappushpop(q, e)
    s += e
    scores.append(s)
  return scores

print(max(map(lambda x: x[0]+x[1], zip(left_scores(A), reversed(left_scores(B))))))

Submission status: Accepted

Solution code:
import os
import sys
import heapq


def solve(n, a):
    res = -10 ** 20
    for i in range(n, 2 * n + 1):
        l = a[0:i]
        r = a[i:3 * n]
        l.sort(reverse=True)
        r.sort()
        res0 = sum(l[0:n]) - sum(r[0:n])
        if res0 > res:
            res = res0
    return res


def find_best(n, a):
    h = list()
    s = 0
    best_s = -10**20
    res = list()
    for i in range(0, 2 * n):
        heapq.heappush(h, a[i])
        s += a[i]
        if len(h) > n:
            m = heapq.heappop(h)
            s -= m
        if len(h) == n:
            if best_s < s:
                best_s = s
            res.append(best_s)
    return res


def solve_large(n, a):
    res = -10 ** 20
    max_l = find_best(n, a)
    b = [-x for x in reversed(a)]
    max_r = find_best(n, b)
    max_r.reverse()
    for l, r in zip(max_l, max_r):
        res0 = l + r
        if res < res0:
            res = res0
    return res


input_file = 'd1.in'
if os.path.exists(input_file):
    sys.stdin = open(input_file)
n = int(input())
a = list(map(int, input().split()))
print(solve_large(n, a))

Submission status: Accepted

Solution code:
# coding: utf-8

import heapq


def calc_l_score(N, a):
    scores = [None] * (N + 1)
    queue = a[:N]
    heapq.heapify(queue)
    scores[0] = sum(queue)
    for i in range(N):
        na = a[N + i]
        heapq.heappush(queue, na)
        m = heapq.heappop(queue)
        scores[i + 1] = scores[i] + na - m
    return scores


def calc_r_score(N, a):
    scores = [None] * (N + 1)
    queue = []
    for i in range(1, N + 1):
        heapq.heappush(queue, -a[-i])
    scores[-1] = - sum(queue)
    for i in range(1, N + 1):
        na = a[-N - i]
        heapq.heappush(queue, -na)
        m = - heapq.heappop(queue)
        scores[-i - 1] = scores[-i] + na - m
    return scores


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

    ls = calc_l_score(N, a)
    rs = calc_r_score(N, a)
    return max([l - r for l, r in zip(ls, rs)])


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

Submission status: Accepted

Solution code:
import heapq

n = int(input())
a = list(map(int, input().split()))
hl = a[0: n]
hr = [-x for x in a[2*n: 3*n]]
heapq.heapify(hl)
heapq.heapify(hr)
sl = sum(hl)
sr = sum(hr)

bl = [sl]
br = [sr]
for i in range(1, n+1):
    heapq.heappush(hl, a[n-1+i])
    vl = heapq.heappop(hl)
    sl += a[n-1+i] - vl
    bl.append(sl)

    heapq.heappush(hr, -a[2*n-i])
    vr = heapq.heappop(hr)
    sr += -a[2*n-i] - vr
    br.append(sr)

max_score = -float('inf')
for i in range(n+1):
    max_score = max(max_score, bl[i]+br[n-i])


print(max_score)

Submission status: Accepted

Solution code:
import heapq
n=int(raw_input())
a=map(int,raw_input().split())
su=[0]*(3*n+1)
hp1=[]
hp2=[]
for i in xrange(3*n):
    su[i+1]+=su[i]+a[i]
for i in xrange(n):
    heapq.heappush(hp1,a[i])
    heapq.heappush(hp2,-a[i+2*n])
ans=-float("inf")
ta1=0
ta2=0
p=[]
b=[]
for i in xrange(n+1):
    p.append(su[n+i]-ta1)
    b.append(su[3*n]-su[2*n-i]-ta2)
    heapq.heappush(hp1,a[i+n])
    heapq.heappush(hp2,-a[2*n-i-1])
    ta1+=heapq.heappop(hp1)
    ta2+=-heapq.heappop(hp2)
    #print hp1,hp2
#print p,b
for i in xrange(n+1):
    ans=max(ans,p[i]-b[n-i])
print ans

Submission status: Accepted

Solution code:
# D
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

# pop from left
popleft = [0]*(N+1)
A_LEFT = np.argsort(A[:(2*N)])
ind_left = 1
for i in range(N):
    while popleft[ind_left] > 0:
        ind_left += 1
    if A_LEFT[i] < N:
        popleft[ind_left] = A[A_LEFT[i]]
    else:
        popleft[max(ind_left, A_LEFT[i] - (N-1))] = A[A_LEFT[i]]
left_sum = np.cumsum(A)[(N-1):(2*N)] - np.cumsum(np.array(popleft))

# pop from right
popright = [0]*(N+1)
A_RIGHT = np.argsort(-A[::-1][:(2*N)])
ind_right = 1
for i in range(N):
    while popright[ind_right] > 0:
        ind_right += 1
    if A_RIGHT[i] < N:
        popright[ind_right] = A[3*N - 1 - A_RIGHT[i]]
    else:
        popright[max(ind_right, A_RIGHT[i] - (N-1))] = A[3*N - 1 - A_RIGHT[i]]
right_sum = np.cumsum(A[::-1])[(N-1):(2*N)] - np.cumsum(np.array(popright))

# print(popleft)
# print(popright)
res = (left_sum - right_sum[::-1]).max()
# extreme case
res1 = (np.sort(A[:2*N])[N:]).sum() - A[2*N:].sum()
res2 = A[:N].sum() - (np.sort(A[N:])[:N]).sum()
print(max(res, res1, res2))

Submission status: Accepted

Solution code:
from heapq import *

N = int(input())

A = list(map(int, input().split()))
A_indexed = [(a, i) for i, a in enumerate(A)]

def scores():
  # initial N:2N
  selected_left = A[:N] # min heap
  heapify(selected_left)
  l_score = sum(selected_left)

  temp = sorted(A_indexed[N:])
  selected_right_set = set(temp[:N])
  unselected_right = temp[N:] # min heap
  del temp
  r_score = sum(map(lambda x: x[0], selected_right_set))

  yield l_score,r_score

  for i in range(N, 2*N):
    a = A[i]
    # left 使うものを減らす, right 使うものを増やす
    if selected_left[0] < a:
      l_score -= heapreplace(selected_left, a)
      l_score += a
      
    if (a,i) in selected_right_set:
      r_score -= a
      selected_right_set.remove((a,i))

      n_element = heappop(unselected_right)
      while n_element[1] <= i:
        n_element = heappop(unselected_right)
      selected_right_set.add(n_element)
      r_score += n_element[0]

    yield l_score,r_score

# print(list(scores()))
print(max(map(lambda x: x[0]-x[1],scores())))

Submission status: Accepted

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

inf = 1<<100

def solve():
    N = int(input())
    a = [int(i) for i in input().split()]
    ps = [0] + list(accumulate(a))

    psmin = [0] * (N + 1)
    minhp = a[:N]
    heapify(minhp)

    for i in range(1, N + 1):
        heappush(minhp, a[N - 1 + i])
        x = heappop(minhp)
        psmin[i] = psmin[i - 1] + x

    psmax = [0] * (N + 1)
    maxhp = [-ai for ai in a[2*N:]]
    heapify(maxhp)

    for i in range(1, N + 1):
        heappush(maxhp, -a[2*N - i])
        x = -heappop(maxhp)
        psmax[i] = psmax[i - 1] + x

    # print(psmin)
    # print(psmax)

    ans = -inf

    for i in range(0, N + 1):
        # print(ps[N + i], psmin[i], ps[3*N] - ps[N + i], psmax[N - i])
        v = (ps[N + i] - psmin[i]) - (ps[3*N] - ps[N + i] - psmax[N - i])
        ans = max(ans, v)

    print(ans)
    pass

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

l = a[:n]
heapq.heapify(l)
memo_l = [0 for _ in range(n+1)]
memo_l[0] = sum(a[:n])

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


r = [-a[-i] for i in range(1, n+1)]
heapq.heapify(r)
memo_r = [0 for _ in range(n+1)]
memo_r[0] = sum(a[-n:])

for i in range(1, n+1):
    memo_r[i] = memo_r[i-1]
    if abs(x) > a[-n-i]:
        x = heapq.heappop(r)
        heapq.heappush(r, -a[-n-i])
        memo_r[i] += x + a[-n-i]


ans = - 10 ** 20
for i in range(n+1):
    ans = max(ans, memo_l[i] - memo_r[n-i])

print(ans)

Submission status: Runtime Error

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
B1 = []
for i in range(N):
    heapq.heappush(B1,(A[i],i))
C = []
for i in range(N,3*N):
    heapq.heappush(C,(A[i],i))
B2 = []
for _ in range(N):
    a,i = heapq.heappop(C)
    B2.append((-a,i))
dmax = 0
for i in range(N):
    dmax += B1[i][0]+B2[i][0]
C = []
for i in range(N,2*N):
    heapq.heappush(C,(A[i],i))
d = dmax
for i in range(N,2*N):
    a = A[i]
    if B1[0][0]<a:
        d += a-B1[0][0]
        heapq.heappop(B1)
        heapq.heappush(B1,(a,i))
    while C[0][1]<=i:
        heapq.heappop(C)
    while B2 and B2[0][1]<=i:
        b,i = heapq.heappop(B2)
        b = -b
        d += b
        a,i = heapq.heappop(C)
        heapq.heappush(B2,(-a,i))
        d -= a
    dmax = max(dmax,d)
print(dmax)

Submission status: Runtime Error

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
B1 = []
for i in range(N):
    heapq.heappush(B1,(A[i],i))
C = []
for i in range(N,3*N):
    heapq.heappush(C,(A[i],i))
B2 = []
for _ in range(N):
    a,i = heapq.heappop(C)
    B2.append((-a,i))
dmax = 0
for i in range(N):
    dmax += B1[i][0]+B2[i][0]
C = []
for i in range(N,2*N):
    heapq.heappush(C,(A[i],i))
d = dmax
for i in range(N,2*N):
    a = A[i]
    if B1[0][0]<a:
        d += a-B1[0][0]
        heapq.heappop(B1)
        heapq.heappush(B1,(a,i))
    while C[0][1]<=i:
        heapq.heappop(C)
    while B2[0][i]<=i:
        b,i = heapq.heappop(B2)
        b = -b
        d += b
        a,i = heapq.heappop(C)
        heapq.heappush(B2,(-a,i))
        d -= a
    dmax = max(dmax,d)
print(dmax)

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop
from copy import deepcopy
def main():
    n = int(input())
    a = list(map(int, input().split()))


    a_mae = deepcopy(a[:n * 2])
    a_ushiro = deepcopy(a[n:])
    a_ushiro = [i * -1 for i in a_ushiro]
    #print(a_mae, a_ushiro)
    a_ave = sum(a_mae) / (n * 2)
    ar_ave = sum(a_ushiro) / (n * 2)
    heapify(a_mae)
    heapify(a_ushiro)
    cnt = 0
    cnt_u = 0
    mae_koho = heappop(a_mae)
    ushiro_koho = heappop(a_ushiro)
    mae_del = 0
    ushiro_del = 0
    for _ in range(n):
        if abs(a_ave - mae_koho) > abs(ar_ave - ushiro_koho):
            cnt += 1
            mae_del += mae_koho
            #print("mae:", mae_koho)
            mae_koho = heappop(a_mae)
            a_ave = sum(a_mae) / len(a_mae)
            #print(a_mae)
        else:
            cnt_u += 1
            ushiro_del += ushiro_koho * -1
            #print("ushiro:", ushiro_koho)
            ushiro_koho = heappop(a_ushiro)
            ar_ave = sum(a_ushiro) / len(a_ushiro)
            #print(a_ushiro)
    mae = sum(a[:n + cnt]) - mae_del
    ushiro = sum(a[n + cnt:]) - ushiro_del
    r = mae - ushiro
    print(r)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:


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

A = (a[0:N])
A = deque(sorted(A))
B = deque(a[N:2*N])
C = a[2*N:3*N]
C = deque(sorted(C, reverse = True))

original_score = 0
for i in range(N):
    original_score += A[i] - C[i]

left = 0
right = 0

for i in range(N):
    left_candidate = B[left] - A[left]
    right_candidate = C[right] - B[-1-right]
    
    if left_candidate >= right_candidate:
        left+=1
        original_score+=left_candidate
    else:
        right+=1
        original_score+=right_candidate
print(original_score)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from heapq import heapify, heappop, heappush
from collections import deque
from copy import deepcopy

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

p = a[:n]
m = list(map(lambda x: int(x) * (-1), a[2 * n:]))
a = deque(a[n:2 * n])
b = deepcopy(a)

heapify(p)
heapify(m)
for i in range(n):
    print(p, m, a)
    pv = heappop(p)
    apv = a.popleft()
    mv = heappop(m) * (-1)
    amv = b.pop()
    pp = apv - pv
    mm = mv - amv
    if pp < 0 and mm < 0:
        heappush(m, mv * (-1))
        heappush(p, pv)
    elif pp > mm:
        heappush(m, mv * (-1))
        heappush(p, apv)
        b.append(amv)
        b.popleft()
    else:
        heappush(p, pv)
        heappush(m, amv * (-1))
        a.appendleft(apv)
        a.pop()
print(sum(p) + sum(m))

Submission status: Runtime Error

Solution code:
import heapq
n=int(input())
a=list(map(int,input().split()))
q=a[0:n]
heapq.heapify(q)
p=list(map(lambda x: x*(-1),a[2*n:3*n]))
heapq.heapify(p)
sums=sum(q)+[0]*(n-1)+sum(p)
am=a[n:2*n]
for i in range(0,n):
    heapq.heappush(q,am[i])
    heapq.heappop(q)
    sums[i+1]=sum(q)
for i in range(n-1,-1,-1):
    heapq.heappush(p,(-1)*am[i])
    heapq.heappop(p)
    sums[i]+=sum(p)
print(max(sums))

Submission status: Runtime Error

Solution code:
import heapq

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

bound = N # 前後の境
h_pre = []
h_post = []
for i in range(N):
    heapq.heappush(h_pre,a_list[i])
    heapq.heappush(h_post,-1*a_list[-(i+1)])
pre_sum = [sum(h_pre)]
post_sum = [sum(h_post)]

for i in range(N):
    a = a_list[N+i]
    heapq.heappushpop(h_pre,a)
    pre_sum.append(sum(h_pre))
    
    b = -1 * a_list[-(i+N+1)]
    heapq.heappushpop(h_post,b)
    post_sum.append(sum(h_post))

ans = -1000_000_000_000_000_000
for i in range(N):
    s = pre_sum[i] + post_sum[-(i+1)]
    if s > ans:
        ans = s

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop, heappush
N=int(input())
A=list(map(int, input().split()))

class MaxHeap:
    def __init__(self, li):
        self.hp = []
        for e in li:
            heappush(self.hp, -e)

    def push(self, x):
        heappush(self.hp, -x)

    def pop(self):
        ret = heappop(self.hp)
        ret *= -1
        return ret

    def seak(self):
        return -self.hp[0]

    def sum(self):
        return -sum(self.hp)

A1=A[:N]
A2=A[N:2*N]
A3=A[2*N:]

heapify(A1)
A1_sum=sum(A1)
A1_li=[A1_sum]
for a in A2:
  heappush(A1, a)
  p=heappop(A1)
  A1_sum+=a-p
  A1_li.append(A1_sum)
  
A3=MaxHeap(A3)
A3_sum=sum(A3)
A3_li=[A3_sum]
for a in A3[::-1]:
  A3.push(a)
  A3_sum+=a
  p=A3.pop()
  A3_sum-=p
  A3_li.append(A3_sum)
  
A3_li=A3_li[::-1]  
ans=False
for a1, a3 in zip(A1_li, A3_li):
  if not ans:
    ans=a1-a3
  else:
    ans=max(ans, a1-a3)
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop, heappush
N=int(input())
A=list(map(int, input().split()))

class MaxHeap:
    def __init__(self, li):
        self.hp = []
        for e in li:
            heappush(self.hp, -e)

    def push(self, x):
        heappush(self.hp, -x)

    def pop(self):
        ret = heappop(self.hp)
        ret *= -1
        return ret

    def seak(self):
        return -self.hp[0]

    def sum(self):
        return -sum(self.hp)

A1=A[:N]
A2=A[N:2*N]
A3=A[2*N:]

heapify(A1)
A1_sum=sum(A1)
A1_li=[A1_sum]
for a in A2:
  heappush(A1, a)
  p=heappop(A1)
  A1_sum+=a-p
  A1_li.append(A1_sum)
  
A3=MaxHeap(A3)
A3_sum=sum(A3)
A3_li=[A3_sum]
for a in A3[::-1]:
  A3.heappush(a)
  A3_sum+=a
  p=A3.heappop()
  A3_sum-=p
  A3_li.append(A3_sum)
  
A3_li=A3_li[::-1]  
ans=False
for a1, a3 in zip(A1_li, A3_li):
  if not ans:
    ans=a1-a3
  else:
    ans=max(ans, a1-a3)
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop, heappush
N=int(input())
A=list(map(int, input().split()))

class MaxHeap:
    def __init__(self, li):
        self.hp = []
        for e in li:
            heappush(self.hp, -e)

    def push(self, x):
        heappush(self.hp, -x)

    def pop(self):
        ret = heappop(self.hp)
        ret *= -1
        return ret

    def seak(self):
        return -self.hp[0]

    def sum(self):
        return -sum(self.hp)

A1=A[:N]
A2=A[N:2*N]
A3=A[2*N:]

heapq.heapify(A1)
A1_sum=sum(A1)
A1_li=[A1_sum]
for a in A2:
  p=heapq.heappushpop(A1,a)
  A1_sum+=a-p
  A1_li.append(A1_sum)
  
A3=MaxHeap(A3)
A3_sum=sum(A3)
A3_li=[A3_sum]
for a in A3[::-1]:
  A3.push(a)
  A3_sum+=a
  p=A3.pop()
  A3_sum-=p
  A3_li.append(A3_sum)
  
A3_li=A3_li[::-1]  
ans=False
for a1, a3 in zip(A1_li, A3_li):
  if not ans:
    ans=a1-a3
  else:
    ans=max(ans, a1-a3)
print(ans)

Submission status: Runtime Error

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

class MaxHeap:
    def __init__(self, li):
        self.hp = []
        for e in li:
            heappush(self.hp, -e)

    def push(self, x):
        heappush(self.hp, -x)

    def pop(self):
        ret = heappop(self.hp)
        ret *= -1
        return ret

    def seak(self):
        return -self.hp[0]

    def sum(self):
        return -sum(self.hp)

A1=A[:N]
A2=A[N:2*N]
A3=A[2*N:]

heapq.heapify(A1)
A1_sum=sum(A1)
A1_li=[A1_sum]
for a in A2:
  p=heapq.heappushpop(A1,a)
  A1_sum+=a-p
  A1_li.append(A1_sum)
  
A3=MaxHeap(A3)
A3_sum=sum(A3)
A3_li=[A3_sum]
for a in A3[::-1]:
  A3.push(a)
  A3_sum+=a
  p=A3.pop()
  A3_sum-=p
  A3_li.append(A3_sum)
  
A3_li=A3_li[::-1]  
ans=False
for a1, a3 in zip(A1_li, A3_li):
  if not ans:
    ans=a1-a3
  else:
    ans=max(ans, a1-a3)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math

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

lst=A[:N]
_sum=sum(lst)
heapify(lst)

sumlst=[0 for i in range(N*3)]
sumlst[0]=_sum
for i in range(N,2*N):
    heappush(lst,A[i])
    a=heappop(lst)
    _sum+=A[i]-a
    sumlst[i-N+1]=_sum
lst=A[N*2:]
_sum=sum(lst)
lst=[-i for i in lst]
heapify(lst)
sumlst[-1]=_sum
for i in range(2*N-1,N-1,-1):
    heappush(lst,-A[i])
    a=heappop(lst)
    _sum-=-a
    _sum+=A[i]
    sumlst[i+N-1]=_sum

print(max([sumlst[i]-sumlst[2*N-1+i] for i in range(3*N//2)]))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())

mnr = 10**9
for a in range(1, W//2 + 1):
    b1 = (H*W)//(a + W)
    b2 = b1+1
    mc = max(abs((W-a)*b1-a*b1), abs(b1*(a+W) - H*W))
    mc2 = max(abs((W-a)*b2-a*b2), abs(b2*(a+W) - H*W))
    mnr = min([mnr, mc, mc2])
H, W = W, H
for a in range(1, W//2 + 1):
    b1 = (H*W)//(a + W)
    b2 = b1+1
    mc = max(abs((W-a)*b1-a*b1), abs(b1*(a+W) - H*W))
    mc2 = max(abs((W-a)*b2-a*b2), abs(b2*(a+W) - H*W))
    mnr = min([mnr, mc, mc2])
if H % 3 == 0 or W % 3== 0:
    mnr = 0
elif H % 3:
    mnr = min(W, mnr)
else:
    mnr = min(H, mnr)
print(mnr)

Submission status: Runtime Error

Solution code:
import bisect
import heapq
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
a_left = sorted(a[:N])
a_right = sorted(a[N:])
sum_left = sum(a_left)
sum_right = sum(a_right[:N])
res = sum_left - sum_right

heapq.heapify(a_left)

len_left = N
for elem in a[N:2*N]:
    le = bisect.bisect_left(a_right, elem)
    a_right[le:] = a_right[le+1:]
    if le < N:
        sum_right -= elem
        sum_right += a_right[N-1]
    now = heapq.heappop(a_left)
    if now < elem:
        heapq.heappush(a_left, elem)
        sum_left += (elem-now)
    else:
        heapq.heappush(a_left, now)
    res = max(res, sum_left-sum_right)
print(res)

"""

Submission status: Runtime Error

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

ans = 1-10**10
for i in range(n, 2*n+1):
    ll = a[:i]
    heapq.heapify(ll)
    for j in range(i-n):
        heapq.heappop(ll)
    rl = a[i:]
    heapq.heapify(rl)
    rsum = [heapq.heappop(rl) for _ in range(n)]
    ans = max(ans, sum(ll)-rsum)
    #print(ll, rsum, sum(ll)-rsum)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
for i in range(N+1):
    P = A[:(N+i)]
    Q = A[(N+i):]
    for l in range(len(Q)):
        Q[l] *= -1
    heapq.heapify(P)
    heapq.heapify(Q)
    j = 0
    k = 0
    while j < i:
        heapq.heappop(P)
    while k < N-i:
        heapq.heappop(Q)
    s = sum(P) + sum(Q)
    S.append(s)
ans = min(S)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import heapq

n=int(input())
s=list(map(int,input().split()))
l=(s[:n])
heapq.heapify(l)
r=[-i for i in s[2*n:]]
heapq.heapify(r)
c=deque(s[n:2*n])
x=l[0]
y=r[0]
while len(c)>0:
    a,b=c[0],-c[-1]
    if a-x>b-y:
        heappop(l)
        heappush(l,c.popleft())
        x=l[0]
    else:
        heappop(r)
        heappush(r,-c.pop())
        y=r[0]
print(sum(l)+sum(r))

Submission status: Runtime Error

Solution code:
import numpy as np
from heapq import heapreplace, heapify
N=int(input())
A=np.array([int(a) for a in input().split(" ")])
lheap, rheap = list(A[:N]), list(-A[2*N:])
heapify(lheap)
heapify(rheap)
Lsum, Rsum = sum(lheap), sum(rheap)
left = [Lsum]
right = [Rsum]

for i in range(N):
    if A[N+i] > lheap[0]:
        Lsum += (A[N+i]-lheap[0])
        heapreplace(lheap, A[N+i])
    
    if -A[2*N-i-1] > rheap[0]:
        Rsum += (-A[2*N-i-1]-rheap[0])
        heapreplace(rheap, -A[2*N-i-1])
    
    left.append(Lsum)
    right.append(Rsum)
print(max(np.array(left)+np.array(right)[::-1]))

Submission status: Runtime Error

Solution code:
def f(a):q=a[:n];heapify(q);return sum(q)+cumsum([e-heappushpop(q,e)for e in a[n:n-~n]]);from heapq import*;from numpy import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),f([-e for e in a[::-1]])[::-1]))))

Submission status: Runtime Error

Solution code:
def f(a):
	q=a[:n];s=sum(q);heapify(q)
	for e in a[n:n-~n]:yield s;s+=e-heappushpop(q,e)
from heapq import*;r=raw_input;n,a=r(),map(int,r());print max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1])))