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: Wrong Answer

Solution code:
import heapq

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

l_s = alst[:n]
r_s = [-1 * num for num in alst[2 * n:]]
heapq.heapify(l_s)
heapq.heapify(r_s)
l_total = [sum(l_s)]
r_total = [sum(r_s)]

for num in alst[n:2*n]:
    if l_s[0] > num:
        l_total.append(l_total[-1])
    else:
        minus = heapq.heappop(l_s)
        heapq.heappush(l_s, num)
        l_total.append(l_total[-1] + num - minus)
        
for num in alst[n:2*n][::-1]:
    if r_s[0] > num * -1:
        r_total.append(r_total[-1])
    else:
        minus = heapq.heappop(r_s)
        heapq.heappush(r_s, -1 * num)
        r_total.append(r_total[-1] - num - minus)

ans = -1 * 10 ** 10
for num, num2 in zip(l_total, r_total[::-1]):
    ans = max(ans, num + num2)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

l_s = alst[:n]
r_s = [-1 * num for num in alst[2 * n:]]
heapq.heapify(l_s)
heapq.heapify(r_s)
l_total = [sum(l_s)]
r_total = [sum(r_s)]

for num in alst[n:2*n]:
    if l_s[0] > num:
        l_total.append(l_total[-1])
    else:
        minus = heapq.heappushpop(l_s, num)
        l_total.append(l_total[-1] + num - minus)
        
for num in alst[n:2*n][::-1]:
    if r_s[0] > num * -1:
        r_total.append(r_total[-1])
    else:
        minus = heapq.heappushpop(r_s, -1 * num)
        r_total.append(r_total[-1] - num - minus)

ans = -1 * 10 ** 10
for num, num2 in zip(l_total, r_total[::-1]):
    ans = max(ans, num + num2)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

l_s = alst[:n]
r_s = [-1 * num for num in alst[2 * n:]]
heapq.heapify(l_s)
heapq.heapify(r_s)

l = n
r = 2 * n - 1
while r - l != -1:
    ll = alst[l] - l_s[0]
    rr = -1 * r_s[0] - alst[r]
    if ll < 0:
        l += 1
    elif rr < 0:
        r -= 1
    elif rr > ll:
        heapq.heappushpop(r_s, -1 * alst[r])
        r -= 1
    else:
        heapq.heappushpop(l_s, alst[l])
        l += 1

print(sum(l_s) + sum(r_s))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
def solve():
  ans = -float('inf')
  N = int(input())
  A = list(map(int, input().split()))
  before = A[:N]
  after = list(map(lambda x:-x,A[-N:]))
  heapify(before)
  heapify(after)
  b = [sum(before)]*(3*N)
  a = [sum(after)]*(3*N)
  for i in range(N,2*N):
    p = heappop(before)
    if p<A[i]:
      b[i] = b[i-1]-p+A[i]
      heappush(before,A[i])
    else:
      b[i] = b[i-1]
      heappush(before,p)
  for i in range(2*N-1,N-1,-1):
    p = heappop(after)
    if p<-A[i]:
      a[i] = a[i+1]-p-A[i]
      heappush(after,-A[i])
    else:
      a[i] = a[i+1]
      heappush(after,p)
  for i in range(N,2*N):
    ans = max(ans,a[i+1]+b[i])
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
import heapq
from typing import Dict, Generic, List, Optional, Tuple, TypeVar


T = TypeVar("T")


class PriorityQueue(Generic[T]):
    def __init__(self):
        self.DONE = -10000
        self.heap: List[Tuple[int, T]] = []
        self.priorities: Dict[T, int] = {}  # Map from state to priority

    # Insert |state| into the heap with priority |newPriority| if
    # |state| isn't in the heap or |newPriority| is smaller than the existing
    # priority.
    # Return whether the priority queue was updated.
    def update(self, state: T, newPriority: int) -> bool:
        oldPriority = self.priorities.get(state)
        if oldPriority is None or newPriority < oldPriority:
            self.priorities[state] = newPriority
            heapq.heappush(self.heap, (newPriority, state))
            return True
        return False

    # Returns (state with minimum priority, priority)
    # or (None, None) if the priority queue is empty.
    def removeMin(self) -> Tuple[Optional[T], Optional[int]]:
        while len(self.heap) > 0:
            (priority, state) = heapq.heappop(self.heap)
            if self.priorities[state] == self.DONE:
                continue  # Outdated priority, skip
            self.priorities[state] = self.DONE
            return (state, priority)
        return (None, None)  # Nothing left...

    def is_empty(self):
        return len(self.heap) == 0

    def __len__(self):
        return len(self.heap)


def main():
    N = int(input())
    A = [int(x) for x in input().split(" ")]
    left = A[: 2 * N]

    right = A[2 * N :]

    left_q = PriorityQueue()
    right_q = PriorityQueue()
    for i, a in enumerate(left):
        left_q.update((i, a), a)
    for i, a in enumerate(right):
        right_q.update((i, a), -a)

    border = 2 * N - 1
    while len(left_q) != N:
        i, min_ = left_q.removeMin()[0]

        if i == border:
            right_q.update((i, min_), -min_)
            right_q.removeMin()
            border -= 1
    res = 0
    while not left_q.is_empty():
        res += left_q.removeMin()[0][1]

    while not right_q.is_empty():
        res -= right_q.removeMin()[0][1]
    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

l = sorted(a[:N])
r = sorted(a[N:])

lsum = sum(l)
rsum = sum(r[:N])

import bisect

ans = lsum - rsum
for i in range(N):
    c = a[N+i]
    li = bisect.bisect_left(l, c)
    ri = bisect.bisect_left(r, c)
    if li > 0: 
        lsum = lsum + c - l[0]
        l = l[1:li] + [c] + l[li+1:]
    if ri < N:
        rsum = rsum - c + r[N]
    r = r[:ri] + r[ri+1:]
    ans = max(ans, lsum - rsum)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque
from heapq import *

def main():
	n=II()
	A=LI()

	X=A[:n]
	Y=[-i for i in A[2*n:]]
	M=A[n:2*n]

	heapify(X)
	heapify(Y)
	M=deque(M)

	while M:
		if M[0]-X[0]>=-Y[0]-M[-1]:
			heappop(X)
			a=M.popleft()
			heappush(X,a)
		else:
			heappop(Y)
			a=M.pop()
			heappush(Y,-a)

	print(sum(X)+sum(Y))




if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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):
    x = heapq.heappop(l)
    heapq.heappush(l, a[n+i-1])
    memo_l[i] = memo_l[i-1] - x + a[n+i-1]


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

for i in range(1, n+1):
    x = heapq.heappop(r)
    heapq.heappush(r, -a[-n-i])
    memo_r[i] = memo_r[i-1] + 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: Wrong Answer

Solution code:
import heapq

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


right = [0] * 3 * n


def build_prefix(arr):
    left = [0] * 3 * n
    h = []
    s = 0
    for i in range(len(arr)):
        if len(h) < n:
            heapq.heappush(h, arr[i])
            s += arr[i]
        else:
            removed = heapq.heappop(h)
            heapq.heappush(h, arr[i])
            s = s - removed + arr[i]
        left[i] = s
    return left

left = build_prefix(arr)
right = build_prefix([-v for v in arr][::-1])[::-1]

ans = -sum(arr)
for i in range(n - 1, 2 * n):
    ans = max(ans, left[i] + right[i + 1])
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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


right = [0] * 3 * n


def build_prefix(arr):
    left = [0] * 3 * n
    h = []
    s = 0
    for i in range(len(arr)):
        if len(h) < n:
            heapq.heappush(h, arr[i])
            s += arr[i]
        else:
            removed = heapq.heappop(h)
            heapq.heappush(h, arr[i])
            s = s - removed + arr[i]
        left[i] = s
    return left

left = build_prefix(arr)
right = build_prefix([-v for v in arr][::-1])[::-1]

ans = -sum(arr)
for i in range(n, 2 * n):
    ans = max(ans, left[i] + right[i + 1])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==1:
  ans=-10**18
  for i in range(3*n):
    t=a[:]
    t.pop(i)
    t=a[0]-a[1]
    ans=max(t,ans)
  print(ans)
  exit(0)

a_front=a[:n]
a_mid_mn=a[n:2*n]
a_end=a[2*n:]
a_end=[-x for x in a_end]
a_mid_mx=[-x for x in a_mid_mn]

from heapq import heapify,heappop,heappush
from collections import deque
heapify(a_front)
heapify(a_mid_mn)
heapify(a_mid_mx)
heapify(a_end)

for i in range(n//2):
  heappop(a_front)
  heappop(a_end)
  t_front=-heappop(a_mid_mx)
  t_end=-heappop(a_mid_mn)
  heappush(a_front,t_front)
  heappush(a_end,t_end)
print(sum(a_front)+sum(a_end))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
import bisect

def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)

    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

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

    one_third = a[0:n]
    one_third.sort(reverse=True)
    three_third = a[2*n:3*n]
    three_third.sort()

    score = sum(one_third) - sum(three_third)
    first, end = n, 2*n-1
    while first <= end:
        f_num, e_num = a[first], a[end]
        score_a = score - one_third[-1] + f_num
        score_b = score + three_third[-1] - e_num
        if score_a >= score_b:
            first += 1
            one_third.pop()
            if len(one_third) == 0:
                one_third.append(f_num)
            else:
                index = bisect_left_reverse(one_third, f_num)
                one_third.insert(index, f_num)
            score = score_a
        else:
            end -= 1
            three_third.pop()
            if len(three_third) == 0:
                three_third.append(e_num)
            else:
                index = bisect.bisect_left(three_third, e_num)
                three_third.insert(index, e_num)
            score = score_b

    print(score)        
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Wrong Answer

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

    a_ave = sum(a) / (n * 3)
    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)
    ar_ave = a_ave * - 1
    heapify(a_mae)
    heapify(a_ushiro)
    cnt = 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)
            #print(a_mae)
        else:
            ushiro_del += ushiro_koho * -1
            #print("ushiro:", ushiro_koho)
            ushiro_koho = heappop(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: Wrong Answer

Solution code:
import heapq
N = int(input())
A = list(map(int, input().split()))
R = [a for a in A[:N]]
M = [a for a in A[N:2*N]]
B = [-a for a in A[2*N:3*N]]
res_R = [0] * (N + 1)
res_B = [0] * (N + 1)
res_R[0] = sum(R)
res_B[N] = -sum(B)
heapq.heapify(R)
heapq.heapify(B)
for i in range(N):
    heapq.heappush(R, M[i])
    a = heapq.heappop(R)
    res_R[i+1] = res_R[i] + M[i] - a
    heapq.heappush(B, -M[N-i-1])
    a = heapq.heappop(B)
    res_B[N-i-1] = res_B[N-i] + M[N-i-1] + a
print(max(r - b for r, b in zip(res_R, res_B)))
print(res_R)
print(res_B)

Submission status: Wrong Answer

Solution code:
import heapq

def solve(n,a):
    res = -float('inf')
    for k in range(n,2*n):
        a1 = a[:k]
        a2 = [-a[i] for i in range(k,3*n)]

        heapq.heapify(a1)
        heapq.heapify(a2)

        while len(a1) > n:
            heapq.heappop(a1)
        while len(a2) > n:
            heapq.heappop(a2)
        
        tmp = sum(a1) + sum(a2)

        res = max(res,tmp)

    return res

if __name__ == '__main__':
    n = int(input())
    a = list(map(int,input().split()))
    print(solve(n,a))

Submission status: Wrong Answer

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

def pq1(m):
  pq1 = [x for x in a[:m]]
  heapq.heapify(pq1)
  while len(pq1) > N:
    heapq.heappop(pq1)

  return sum(pq1)

def pq2(m):
  pq2 = [-x for x in a[m:]]
  heapq.heapify(pq2)
  while len(pq2) > N:
    heapq.heappop(pq2)

  return sum([-i for i in pq2])

res = 0
for k in range(N, 2*N+1):
  res = max(res, pq1(k) - pq2(k))

print(res)

Submission status: Wrong Answer

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

m = len(a) // 2
# 3になるように調整
pq1 = a[:m]
heapq.heapify(pq1)
while len(pq1) != N:
  heapq.heappop(pq1)

pq2 = [-i for i in a[m:] ]
heapq.heapify(pq2)
while len(pq2) != N:
  heapq.heappop(pq2)

print(sum(pq1) - sum([-i for i in pq2]))

Submission status: Wrong Answer

Solution code:
import heapq

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

First = A[:N]
FirstSum = sum(First)
FirstSumDict = {N-1:FirstSum}
heapq.heapify(First)
for k in range(N,2*N):
    heapq.heappush(First,A[k])
    FirstSum += A[k]-heapq.heappop(First)
    FirstSumDict[k] = FirstSum

Latter = []
for i in range(3*N-1,2*N-1,-1):
    Latter.append(A[i]*-1)
LatterSum = sum(Latter)*-1
LatterSumDict = {2*N-1:LatterSum}
heapq.heapify(Latter)
for k in range(2*N-1,N-1,-1):
    heapq.heappush(Latter,A[k]*-1)
    LatterSum += A[k] - heapq.heappop(Latter)*-1
    LatterSumDict[k-1] = LatterSum

maxList = []
for k in range(N,2*N):
    maxList.append(FirstSumDict[k]-LatterSumDict[k])
print(max(maxList))

Submission status: Wrong Answer

Solution code:
import heapq

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

First = A[:N]
FirstSum = sum(First)
FirstSumDict = {N-1:FirstSum}
heapq.heapify(First)
for k in range(N,2*N):
    heapq.heappush(First,A[k])
    FirstSum += A[k]-heapq.heappop(First)
    FirstSumDict[k] = FirstSum

Latter = []
for i in range(3*N-1,2*N-1,-1):
    Latter.append(A[i]*-1)
LatterSum = sum(Latter)*-1
LatterSumDict = {2*N-1:LatterSum}
heapq.heapify(Latter)
for k in range(2*N-1,N-1,-1):
    heapq.heappush(Latter,A[k]*-1)
    LatterSum += A[k] - heapq.heappop(Latter)*-1
    LatterSumDict[k-1] = LatterSum

ans = -1*float("INF")
for k in range(N,2*N):
    ans = max(ans,FirstSumDict[k]-LatterSumDict[k])
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) #左側にAの左側からN個を追加
  heapq.heappush(R,-A[-1-i]) #右側数列にAの右側からN個を追加。多いほうから取り出すので-1倍
  
#print(L,R,C)

lp = 0 #Cの左から取り除いた数
rp = 0
for i in range(N):
  #print(i,lp,rp)
  if C[lp] - L[0] >= -C[-1-rp] - R[0]: #左側を交換したほうが効率が良い場合
    heapq.heappush(L, C[lp]) #左側に加えてから一番小さいものを消す。
    temp = heapq.heappop(L)
    lp += 1
  else:
    heapq.heappush(R, -C[-1-rp])
    temp = heapq.heappop(R)    
    rp += 1
#print(L,R,lp,rp)
ans = sum(L) + sum(R)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) #左側にAの左側からN個を追加
  heapq.heappush(R,-A[-1-i]) #右側数列にAの右側からN個を追加。多いほうから取り出すので-1倍
  
#print(L,R,C)

lp = 0 #Cの左から取り除いた数
rp = 0
for i in range(N):
  #print(i,lp,rp)
  if C[lp] - L[0] >= -C[-1-rp] - R[0]: #左側を交換したほうが効率が良い場合
    heapq.heappush(L, C[lp]) #左側に加えてから一番小さいものを消す。
    temp = heapq.heappop(L)
    lp += 1
  else:
    heapq.heappush(R, -C[-1-rp])
    temp = heapq.heappop(R)    
    rp += 1
print(L,R,lp,rp)
ans = sum(L) + sum(R)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) #左側にAの左側からN個を追加
  heapq.heappush(R,-A[-1-i]) #右側数列にAの右側からN個を追加。多いほうから取り出すので-1倍
  
#print(L,R,C)

lp = 0 #Cの左から取り除いた数
rp = 0
for i in range(N):
  #print(i,lp,rp)
  if C[lp] - L[0] >= -C[-1-rp] - R[0]: #左側を交換したほうが効率が良い場合
    temp = heapq.heappop(L)
    heapq.heappush(L, C[lp])
    lp += 1
  else:
    temp = heapq.heappop(R)
    heapq.heappush(R, -C[-1-rp])
    rp += 1
#print(L,R)
ans = sum(L) + sum(R)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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


L = a[:N]
R = a[(N*2):]
L_sum_list = [sum(L)]
R_sum_list = [sum(R)]

R = [-elem for elem in R]

heapq.heapify(L)
heapq.heapify(R)

for k in range(N):
    #L側
    L.append(a[N+k])
    rem = a[N+k] - heapq.heappop(L)
    L_sum_list.append(L_sum_list[-1]+rem)

    #R側
    R.append(-(a[N*2-k-1]))
    rem = -(a[N*2-k-1]) - heapq.heappop(R)
    R_sum_list.append(R_sum_list[-1]-rem)

res = []
for k in range(N+1):
    res.append(L_sum_list[k] - R_sum_list[-k-1])


print(max(res))

Submission status: Wrong Answer

Solution code:
import heapq

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


L = a[:N]
R = a[(N*2):]
L_sum_list = [sum(L)]
R_sum_list = [sum(R)]

R = [-elem for elem in R]

heapq.heapify(L)
heapq.heapify(R)

for k in range(N):
    #L側
    rem = a[N+k] - heapq.heappop(L)
    L_sum_list.append(L_sum_list[-1]+rem)

    #R側
    rem = -(a[N*2-k-1]) - heapq.heappop(R)
    R_sum_list.append(R_sum_list[-1]-rem)

res = []
for k in range(N+1):
    res.append(L_sum_list[k] - R_sum_list[-k-1])

print(max(res))

Submission status: Wrong Answer

Solution code:
import heapq

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


L = a[:N]
R = a[(N*2):]
L_sum_list = [sum(L)]
R_sum_list = [sum(R)]

R = [-elem for elem in R]

heapq.heapify(L)
heapq.heapify(R)

for k in range(N):
    #L側
    rem = a[N+k] - heapq.heappop(L)
    L_sum_list.append(L_sum_list[-1]+rem)

    #R側
    rem = -(a[N*2-k-1]) - heapq.heappop(R)
    R_sum_list.append(R_sum_list[-1]-rem)

res = -float('inf')
for k in range(N+1):
    res = max(res, L_sum_list[k] - R_sum_list[-k-1])

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
import heapq
que1 = [a for a in A[:N]]
heapq.heapify(que1)
frontMax = sum(A[:N])
memo1 = [frontMax]
for j in range(N):
    heapq.heappush(que1,A[N+j])
    out = heapq.heappop(que1)
    frontMax += A[N+j] - out
    memo1.append(frontMax)


tmp = []
for i in range(1,3*N+1):
    tmp.append(A[-i]*-1)
A = tmp
que2 = [a for a in A[:N]]
heapq.heapify(que2)
frontMax = sum(A[:N])
memo2 = [frontMax*-1]
for j in range(N):
    heapq.heappush(que2,A[N+j])
    out = heapq.heappop(que2)
    frontMax += A[N+j] - out
    memo2.append(frontMax*-1)

memo2 = memo2[::-1]
ans = memo1[0]-memo2[0]
for i in range(N):
    ans = max(ans,memo1[i]-memo2[i])

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n+1):
  m=0
  b1=a[:n+i]
  b2=a[n+i:]
  heapq.heapify(b1)
  heapq.heapify(b2)
  for j in range(i):
    b=heapq.heappop(b1)
  for j in range(n-i):
    b=heapq.heappop(b2)
  m=sum(b1)-sum(b2)
  if ans<m or i==0:
    ans=m
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 18:58:46 2020

@author: naoki
"""
from heapq import heappush, heappop
import sys

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

hq = []
hq_r = []
for i in range(N):
    heappush(hq,a[i])
    heappush(hq_r,-1*a[-1-i])


max_A = [0 for _ in range(N+1)]
max_A[0] = sum(hq)

min_C = [0 for _ in range(N+1)]
min_C[0] = sum(hq_r) * (-1)

for i in range(N):
    heappush(hq, a[N+i])
    heappush(hq_r, -1*a[-N-1-i])
    minus = heappop(hq)
    minus_r = heappop(hq_r)
    max_A[i+1] = max_A[i] + a[N+i] - minus
    min_C[i+1] = min_C[i] + a[-N-1-i] + minus_r
    
max_val = -10e+100
print(max_val)
for i in range(N+1):
    kari = max_A[i] - min_C[-1-i]
    if max_val < kari:
        max_val =kari
print(max_val)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 18:58:46 2020

@author: naoki
"""
from heapq import heappush, heappop

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

hq = []
hq_r = []
for i in range(N):
    heappush(hq,a[i])
    heappush(hq_r,-1*a[-1-i])


max_A = [0 for _ in range(N+1)]
max_A[0] = sum(hq)

min_C = [0 for _ in range(N+1)]
min_C[0] = sum(hq_r) * (-1)

for i in range(N):
    heappush(hq, a[N+i])
    heappush(hq_r, -1*a[-N-1-i])
    minus = heappop(hq)
    minus_r = heappop(hq_r)
    max_A[i+1] = max_A[i] + a[N+i] - minus
    min_C[i+1] = min_C[i] + a[-N-1-i] + minus_r
    
max_val = -10e+100
for i in range(N):
    kari = max_A[i] - min_C[-1-i]
    if max_val < kari:
        max_val =kari
print(max_val)

Submission status: Wrong Answer

Solution code:


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

A = (a[0:N])
A = sorted(A)
B = a[N:2*N]
C = a[2*N:3*N]
C = 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: Wrong Answer

Solution code:
import heapq

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

#仕切りが左はじのとき
sum_left=sum(As[:N])
left_heap  = As[:N]
right_heap  = As[N:]
heapq.heapify(left_heap)
heapq.heapify(right_heap)

#右側のヒープから小さい順にN個値を取り出す
selected_from_left = []
for i in range(N):
    poped = heapq.heappop(right_heap)
    selected_from_left.append(poped)

sum_right = sum(selected_from_left)

max_score = sum_left-sum_right

record_dict = {}
for i in range(N):
    #仕切りを一つずつ動かしていく
    #左側の集合について、最小値よりも新しい値が大きければそれを追加する
    discarded = heapq.heappushpop(left_heap,As[N+i])
    sum_left += As[N+i]-discarded

    #右側の集合について、右側ヒープの最小値よりも値が小さければ新たに値を取得して、それを追加する
    if As[N+i]<right_heap[0]:
        while(True):
            obtained = heapq.heappop(right_heap) #最小値を取得して、それをを集合に追加する
            if "{}".format(obtained) in record_dict.keys():
                if record_dict["{}".format(obtained)]>0:
                    record_dict["{}".format(obtained)] -=1
                else:
                    break
            else:
                break
        sum_right += obtained- As[N+i]
    else: #As[N+i]>=right_heap[0]
        #この場合、As[N+i]は戦力外に入っていた。
        #こいつだけヒープから削除したいけれど、そういうわけにはいかないので、それを記録しないといけない。
        if "{}".format(As[N+i]) in record_dict.keys():
            record_dict["{}".format(As[N+i])] += 1
        else:
            record_dict["{}".format(As[N+i])] = 1


    new_score = sum_left - sum_right
    if max_score<new_score:
        max_score=new_score

print(max_score)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

import heapq
from collections import deque

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

heapq.heapify(p)
heapq.heapify(m)

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

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    L, R, p = [], [], A[:N]
    L.append(sum(p))
    heapq.heapify(p)

    for i in range(N, 2*N):
        heapq.heappush(p, A[i])
        x = heapq.heappop(p)
        L.append(L[i-N]+A[i]-x)

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

    ret = -10 ** 10
    for x, y in zip(L, R):
        ret = max(ret, x- y)
    print(ret)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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=[0]*(n+1)
sums[0]=sum(q)
sums[n]=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: Wrong Answer

Solution code:
INF=10**30
from heapq import heapify,heappop,heappush
N=int(input())
a=list(map(int,input().split()))

right=list(map(lambda x:-x,a[2*N:]));heapify(right)
rmin=[INF]*(3*N);rmin[2*N]=sum(right)*-1

for i in reversed(range(N,2*N)):
    p=heappop(right)*-1
    b=min(p,a[i])
    d=0 if b==p else b-p
    heappush(right,b*-1)
    rmin[i]=rmin[i+1]-d

left=a[:N];heapify(left)
lmax=[-INF]*(3*N);lmax[N-1]=sum(left)
for i in range(N,2*N):
    p=heappop(left)
    b=max(p,a[i])
    d=0 if b==p else b-p
    heappush(left,b)
    lmax[i]=lmax[i-1]+d
res=-INF
for i in range(N,2*N+1):
    res=max(res,lmax[i-1]-rmin[i])
print(res)

Submission status: Wrong Answer

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

b = a[:N]
c = a[-N:]
L = [0]*(N+1)
R = [0]*(N+1)

L[0] = sum(b)


heapq.heapify(b)

R[-1] = sum(c)
c = list(map(lambda x: -x, c))
heapq.heapify(c)

for i in range(N):
    k = a[i+N]
    x = heapq.heappop(b)
    if x < k:
        L[i+1] = L[i] + k - x
        heapq.heappush(b, k)
    else:
        L[i+1] = L[i]
        heapq.heappush(b, x)

for i in range(N-1, -1, -1):
    k = a[i+N]
    x = heapq.heappop(c)
    if -x > k:
        heapq.heappush(c, -k)
        R[i] = R[i+1] + x + k
    else:
        R[i] = R[i+1]
        heapq.heappush(c, x)
ans = 0
for i in range(N+1):
    ans = max(ans, L[i]-R[i])
#print(L, R)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappushpop, heappop
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
first = [a[0]]
first_sum = [0] * (3*N)
first_sum[0] = a[0]
for i in range(1, 3*N):
    if i < N:
        first_sum[i] = first_sum[i-1] + a[i]
        heappush(first, a[i])
    else:
        first_sum[i] = first_sum[i-1] + a[i] - heappushpop(first, a[i])

second = [-a[-1]]
second_sum = [0] * (3*N)
second_sum[-1] = a[-1]
for i in range(3*N-1)[::-1]:
    if i >= 2*N:
        second_sum[i] = second_sum[i+1] + a[i]
        heappush(second, -a[i])
    else:
        heappush(second, -a[i])
        x = -heappop(second)
        second_sum[i] = second_sum[i+1] + a[i] - x
ans = max(first_sum[i] - second_sum[i+1] for i in range(N, 2*N))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
n = int(input())
a = [int(i) for i in input().split()]
a_l = [];a_r = []
sum_a_l = 0;sum_a_r = 0
a = tuple(a)
heapq.heapify(a_l);heapq.heapify(a_r)

for i in range(n):
  heapq.heappush(a_l,a[i])
  heapq.heappush(a_r,-a[3*n-1-i])
  sum_a_l += a[i]
  sum_a_r += a[3*n-1-i]
chk_1 = [sum_a_l]
chk_2 = [sum_a_r]
import collections
chk_1 = collections.deque(chk_1)
chk_2 = collections.deque(chk_2)
ans = -float('inf')
for i in range(n):
  #print(a_l,a_r)
  heapq.heappush(a_l,a[n+i])
  heapq.heappush(a_r,-a[2*n-1-i])
  x = heapq.heappop(a_l)
  y = heapq.heappop(a_r)
  chk_1_append=chk_1.append
  chk_2_append=chk_2.append
  sum_a_l += a[n+i]-x
  sum_a_r += y+a[2*n-1-i]
  chk_1_append(sum_a_l)
  chk_2_append(sum_a_r)

#print(chk_1,chk_2)
for i in range(n):
  ans = max(chk_1.pop()-chk_2.popleft(),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
n = int(input())
a = [int(i) for i in input().split()]
a_l = [];a_r = []
sum_a_l = 0;sum_a_r = 0
a = tuple(a)
heapq.heapify(a_l);heapq.heapify(a_r)

for i in range(n):
  heapq.heappush(a_l,a[i])
  heapq.heappush(a_r,-a[3*n-1-i])
  sum_a_l += a[i]
  sum_a_r += a[3*n-1-i]
chk_1 = [sum_a_l]
chk_2 = [sum_a_r]
import collections
chk_1 = collections.deque(chk_1)
chk_2 = collections.deque(chk_2)
ans = -10**15
for i in range(n):
  #print(a_l,a_r)
  heapq.heappush(a_l,a[n+i])
  heapq.heappush(a_r,-a[2*n-1-i])
  x = heapq.heappop(a_l)
  y = heapq.heappop(a_r)
  chk_1_append=chk_1.append
  chk_2_append=chk_2.append
  sum_a_l += a[n+i]-x
  sum_a_r += -y+a[2*n-1-i]
  chk_1_append(sum_a_l)
  chk_2_append(sum_a_r)

#print(chk_1,chk_2)
for i in range(n):
  ans = max(chk_1.pop()-chk_2.popleft(),ans)
print(ans)