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:
# 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[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-1)])
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[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))


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

Solution code:
N=int(raw_input())
a=map(int,raw_input().split())
b=a[:3*N/2];c=a[3*N/2:]

if N%2!=0:c.remove(max(c))
for i in range(N/2):
	b.remove(min(b))
	c.remove(max(c))

print sum(b)-sum(c)

Submission status: Wrong Answer

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-1)])
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[A_LEFT[i] - (N-1) + 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-1)])
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[A_RIGHT[i] - (N-1) + 1] = A[3*N - 1 - A_RIGHT[i]]
right_sum = np.cumsum(A[::-1])[(N-1):2*N] - np.cumsum(np.array(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: Wrong Answer

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)

# li = n
# ri = 2*n-1
# score = sum(a[0: n]) - sum(a[2*n: 3*n])
al = sorted(a[0: n], reverse=True)
ar = sorted(a[2*n: 3*n])
scorel = [0]
scorer = [0]
scorem = [0]
for i in range(n):
    scorel.append(scorel[i] + al[i])
    scorer.append(scorer[i] + ar[i])
    scorem.append(scorem[i] + a[n+i])
# print(scorel)
# print(scorer)
# print(scorem)
max_score = -float('inf')
for i in range(n+1):
    for j in range(n-i, n+1):
        max_score = max(max_score, scorel[i] + scorem[n-i] - scorer[j]  - (scorem[n] - scorem[j]))
        # print(i, j, max_score, scorel[i] , scorem[n-i] , scorer[j]  , (scorem[n] - scorem[j]))


print(max_score)

Submission status: Wrong Answer

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

INF=-1000000000

#前方Nと後方2Nで分割かつソート
before=sorted(a[:N])
after=sorted(a[N:])
#print(before)
#print(after)

ans=INF
for i in range(N):
	left=sum(before)
	right=sum(after[:N])
	ans=max(ans,left-right)
	
	after.remove(a[N+i])
	if before[0]<a[N+i]:
		before.pop(0)
		before.append(a[N+i])
		before.sort()
	after.sort()
	
	#print(before)
	#print(after)
	#print()
left=sum(before)
right=sum(after[:N])
ans=max(ans,left-right)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
a = list(map(int, input().split()))
ql = a[:n]
qr = list(map(lambda x: -x, a[2 * n:]))
sl = [sum(ql) for _ in range(3 * n)]
sr = [sum(qr) for _ in range(3 * n)]
heapq.heapify(ql)
heapq.heapify(qr)

ans = sl[n - 1] + sr[2 * n]
for i in range(n, 2 * n):
    ai = a[i]
    al = heapq.heappop(ql)
    if ai < al:
        sl[i] = sl[i - 1]
    else:
        sl[i] = sl[i - 1] - min(al, ai) + max(al, ai)
    heapq.heappush(ql, max(al, ai))

for i in range(2 * n - 1, n - 1, -1):
    ai = -a[i]
    ar = heapq.heappop(qr)
    if ai < ar:
        sr[i - 1] = sr[i]
    else:
        sr[i - 1] = sr[i] - min(ar, ai) + max(ar, ai)
    heapq.heappush(qr, max(ar, ai))

for i in range(n, 2 * n + 1):
    ans = max(ans, sl[i] + sr[i])

print(ans)

Submission status: Wrong Answer

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-1)])
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[A_LEFT[i] - (N-1) + 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-1)])
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[A_RIGHT[i] - (N-1) + 1] = A[3*N - 1 - A_RIGHT[i]]
right_sum = np.cumsum(A[::-1])[(N-1):2*N] - np.cumsum(np.array(popright))

# print(left_sum)
# print(right_sum)
print((left_sum - right_sum[::-1]).max())

Submission status: Wrong Answer

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-1)])
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[A_LEFT[i] - (N-1) + 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[(N+1):])
ind_right = 1
for i in range(N):
    while popright[ind_right] > 0:
        ind_right += 1
    if A_RIGHT[i] > N-2:
        popright[ind_right] = A[A_RIGHT[i] + N + 1]
    else:
        popright[2*N - (A_RIGHT[i] + N + 1) + 1] = A[A_RIGHT[i] + N + 1]
right_sum = np.cumsum(A[::-1])[(N-1):2*N] - np.cumsum(np.array(popright))

# print(left_sum)
# print(right_sum)
print((left_sum - right_sum[::-1]).max())

Submission status: Wrong Answer

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

INF=-100000000000000000000000000

#前方Nと後方2Nで分割かつソート
before=sorted(a[:N])
after=sorted(a[N:])
#print(before)
#print(after)

ans=INF
for i in range(N):
	left=sum(before)
	right=sum(after[:N])
	ans=max(ans,left-right)
	
	after.remove(a[N+i])
	if before[0]<a[N+i]:
		del before[0]
		before.append(a[N+i])
		before.sort()
	
	#print(before)
	#print(after)
	#print()
ans=max(ans,left-right)
print(ans)

Submission status: Wrong Answer

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

INF=-10000000000000000

#前方Nと後方2Nで分割かつソート
before=sorted(a[:N])
after=sorted(a[N:])
#print(before)
#print(after)

ans=INF
for i in range(N):
	left=sum(before)
	right=sum(after[:N])
	ans=max(ans,left-right)
	
	after.remove(a[N+i])
	if before[0]<a[N+i]:
		del before[0]
		before.append(a[N+i])
		before.sort()
	
	#print(before)
	#print(after)
	#print()
ans=max(ans,left-right)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xs = list(map(int, input().split()))
ans = -100000000000000000000000000000000000000
for i in range(n):
    head = sorted(xs[:n+i+1])
    tail = sorted(xs[n+i+1:])
    ans = max(ans, sum(head[-n:])-sum(tail[:n]))
print(ans)

Submission status: Wrong Answer

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

INF=-10000000000

#前方Nと後方2Nで分割かつソート
before=sorted(a[:N])
after=sorted(a[N:])
#print(before)
#print(after)

ans=INF
for i in range(N):
	left=sum(before)
	right=sum(after[:N])
	ans=max(ans,left-right)
	
	temp=a[N+i]
	after.remove(temp)
	if before[0]<temp:
		del before[0]
		before.append(temp)
		before.sort()
	
	#print(before)
	#print(after)
	#print()
ans=max(ans,left-right)
print(ans)

Submission status: Wrong Answer

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)

li = n
ri = 2*n-1
score = sum(a[0: n]) - sum(a[2*n: 3*n])
for i in range(n):
    vl = heapq.heappop(hl)
    vr = -heapq.heappop(hr)
    if (a[li] - vl) >= (vr - a[ri]):
        score += (a[li] - vl)
        heapq.heappush(hl, a[li])
        li += 1
        heapq.heappush(hr, -vr)
    elif (a[li] - vl) < (vr - a[ri]):
        score += (vr - a[ri])
        heapq.heappush(hr, a[ri])
        ri -= 1
        heapq.heappush(hl, vl)

print(score)

Submission status: Wrong Answer

Solution code:
n = int(input())
xs = list(map(int, input().split()))
ans = -100000000000000000000000000000000000000
for i in range(n):
    head = sorted(xs[:n+i])
    tail = sorted(xs[n+i:])
    ans = max(ans, sum(head[-n:])-sum(tail[:n]))
print(ans)

Submission status: Wrong Answer

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

INF=-100000000

#前方Nと後方2Nで分割かつソート
before=sorted(a[:N])
after=sorted(a[N:])
#print(before)
#print(after)

ans=INF
for i in range(N):
	left=sum(before)
	right=sum(after[:N])
	if left-right>ans:
		ans=left-right
	temp=a[N+i]
	after.remove(temp)
	if before[0]<temp:
		before.pop(0)
		before.append(temp)
		before.sort()
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xs = list(map(int, input().split()))
ans = -10000000000
for i in range(n):
    head = sorted(xs[:n+i])
    tail = sorted(xs[n+i:])
    ans = max(ans, sum(head[-n:])-sum(tail[:n]))
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
n = input()
A = map(int, raw_input().split())
left = [0]*(3*n+1)
right = [0]*(3*n+1)
lsum = rsum = 0
que = []
for i in xrange(3*n):
    lsum += A[i]
    heappush(que, A[i])
    if len(que) > n:
        v = heappop(que)
        lsum -= v
    left[i] = lsum
que = []
for i in xrange(3*n-1, -1, -1):
    rsum += A[i]
    heappush(que, -A[i])
    if len(que) > n:
        v = heappop(que)
        rsum += v
    right[i] = rsum
ans = -10**18
for i in xrange(n, 2*n):
    ans = max(ans, left[i] - right[i+1])
print ans

Submission status: Time Limit Exceeded

Solution code:
import heapq 
# よく使うメソッドは以下
# q=heapq.heapify(List)：リスト→プライオリティキュー
# heapq.heappop(q)：プライオリティキュー q から最小要素を取り出す(O(log n))
# heapq.heappop(q,a)：プライオリティキュー q に要素を追加 O(log n))

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

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

res=[]
for k in range(N+1):
    qA=A1+A2[:k]
    heapq.heapify(qA)
    sumA=sum(qA)

    qB=A2[k:]+A3
    heapq.heapify(qB)
    sumB=0
    
    for n in range(N):
        sumB+=heapq.heappop(qB)
    for n in range(k):
        sumA-=heapq.heappop(qA)
    res.append(sumA-sumB)
print(max(res))

Submission status: Time Limit Exceeded

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.insert(li, c)
        del l[0]
    if ri < N:
        rsum = rsum - c + r[N]
    del r[ri]
    ans = max(ans, lsum - rsum)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

total = (-1) * 10 ** 14
for i in range(n,2*n+1):
    b = a[0:i]
    c = a[i:]
    heapq.heapify(b)
    c = list(map(lambda x: x*(-1),c))
    heapq.heapify(c)
    for j in range(i-n):
        heapq.heappop(b)
    for j in range(2 * n - i):
        heapq.heappop(c)

    total = max(total, sum(b) - sum(c) * (-1))

print(total)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def solve(n,a):
    res = -float('inf')
    for k in range(n,2*n+1):
        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: Time Limit Exceeded

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

cumsumA = []
prefix = [x for x in a[:N]]
heapq.heapify(prefix)
cumsumA.append(sum(prefix))
for k in range(N, 2*N):
  heapq.heappush(prefix, a[k])
  heapq.heappop(prefix)
  cumsumA.append(sum(prefix))

cumsumB = []
suffix = [-x for x in a[2*N:]]
heapq.heapify(suffix)
cumsumB.append(-sum(suffix))
for k in range(2*N-1, N-1, -1):
  heapq.heappush(suffix, -a[k])
  heapq.heappop(suffix)
  cumsumB.append(-sum(suffix))

res = -float('inf')
for i in range(0, len(cumsumA)):
  res = max(res, cumsumA[i] - cumsumB[len(cumsumA)-i-1])

print(res)

Submission status: Time Limit Exceeded

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倍

#左側の総和を求める。
ansL = [sum(L)]
for i in range(N):
  heapq.heappush(L,C[i])
  heapq.heappop(L)
  ansL.append(sum(L))

ansR = [sum(R)]
for i in range(N):
  heapq.heappush(R,-C[-1-i])
  heapq.heappop(R)
  ansR.append(sum(R))

ans = -float('inf')
for i in range(N+1):
  temp = ansL[i]+ansR[-1-i]
  ans = max(ans,temp)
#print(ansL,ansR)
print(ans)

Submission status: Time Limit Exceeded

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]
for k in range(N):
    #L側
    L.append(a[N+k])
    heapq.heapify(L)
    rem = a[N+k] - heapq.heappop(L)
    L_sum_list.append(L_sum_list[-1]+rem)

    #R側
    R.append(-(a[N*2-k-1]))
    heapq.heapify(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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
ans=0
for i in range(n+1):
  m=0
  b1=np.sort(a[:n+i])[i:]
  b2=np.sort(a[n+i:])[:n]
  m=np.sum(b1)-np.sum(b2)
  if ans<m or i==0:
    ans=m
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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):
    b=heapq.heappop(b2)
    m-=b
  m+=sum(b1)
  if ans<m or i==0:
    ans=m
print(ans)

Submission status: Time Limit Exceeded

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:]
  for j in range(len(b1)):
    b1[j]=-b1[j]
  heapq.heapify(b1)
  heapq.heapify(b2)
  for j in range(n):
    b=-heapq.heappop(b1)
    m+=b
    b=heapq.heappop(b2)
    m-=b
  if ans<m or i==0:
    ans=m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
a = list(map(int,input().split()))
fa = a[:N:]
ba = list(map(lambda x: x*(-1), a[2*N::]))
heapq.heapify(fa)
heapq.heapify(ba)
suml = [sum(fa)]
k = -2

for i in range(N, 2*N):
    heapq.heappush(fa, a[i])
    heapq.heappop(fa)
    suml.append(sum(fa))

suml[-1] += sum(ba)

for j in range(2*N-1, N-1, -1):
        heapq.heappush(ba, -a[j])
        heapq.heappop(ba)
        suml[k] += sum(ba)
        k -= 1
    


print(max(suml))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
a = list(map(int,input().split()))
fa = a[:N:]
ba = list(map(lambda x: x*(-1), a[2*N::]))
heapq.heapify(fa)
heapq.heapify(ba)
suml = [sum(fa)]
k = -2

for i in range(N, 2*N):
    heapq.heappush(fa, a[i])
    heapq.heappop(fa)
    suml.append(sum(fa))

suml[-1] += sum(ba)

for j in range(2*N-1, N-1, -1):
        heapq.heappush(ba, -a[j])
        heapq.heappop(ba)
        suml[k] += sum(ba)
        k -= 1
    


print(max(suml))

Submission status: Time Limit Exceeded

Solution code:
import heapq
n=int(input())
a=list(map(int,input().split()))
q=a[0:n]
sums=[0]*(n+1)
sums[0]=sum(q)
heapq.heapify(q)
am=a[n:2*n]
for i in range(0,n):
    heapq.heappush(q,am[i])
    heapq.heappop(q)
    sums[i+1]=sum(q)
p=a[2*n:3*n]
p=list(map(lambda x: x*(-1),p))
sums[n]+=sum(p)
heapq.heapify(p)
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: Time Limit Exceeded

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)):
    b=min(heappop(right)*-1,a[i])
    heappush(right,b*-1)
    rmin[i]=sum(right)*-1

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())
a = list(map(int,input().split()))
ans = -float("inf")
for k in range(n, 2 * n + 1):
    b = list()
    c = list()
    heapq.heappush(b, a[:k])
    heapq.heappush(c,a[k:])
    b = b[0]
    heapq.heapify(b)
    for i in range(k-n):
        heapq.heappop(b)
    c = list(map(lambda x: x*(-1),c[0]))
    heapq.heapify(c)
    for i in range(2*n-k):
        heapq.heappop(c)
    c = list(map(lambda x: x*(-1),c))
    heapq.heapify(c)
    ans = max(ans, sum(b)-sum(c))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from copy import deepcopy
from sys import stdin

N = int(stdin.readline())
a = list(map(int, stdin.readline().split()))

# 前半と後半
first, second = [], []
heapq.heapify(first)
heapq.heapify(second)

first_sum, second_sum = 0, 0

for i in range(N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]


first_tmp = deepcopy(first)
second_tmp = deepcopy(second)
first_sum_tmp = first_sum
second_sum_tmp = second_sum
ans = -10 ** 15

# first側からk個を取り除き、second側からN - k個を取り除く
for k in range(N + 1):
    first = deepcopy(first_tmp)
    second = deepcopy(second_tmp)
    first_sum = first_sum_tmp
    second_sum = second_sum_tmp
    cnt = 0

    while cnt < k:
        heapq.heappush(first, a[N + cnt])
        first_sum += a[N + cnt]
        first_sum -= heapq.heappop(first)
        cnt += 1

    while cnt < N:
        heapq.heappush(second, -a[N + cnt])
        second_sum += a[N + cnt]
        second_sum -= -heapq.heappop(second)
        cnt += 1

    ans = max(ans, first_sum - second_sum)
    # print(first_sum, second_sum)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from copy import deepcopy

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

# 前半と後半
first, second = [], []
heapq.heapify(first)
heapq.heapify(second)

first_sum, second_sum = 0, 0

for i in range(N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]


first_tmp = deepcopy(first)
second_tmp = deepcopy(second)
first_sum_tmp = first_sum
second_sum_tmp = second_sum
ans = -10 ** 15

# first側からk個を取り除き、second側からN - k個を取り除く
for k in range(N + 1):
    first = deepcopy(first_tmp)
    second = deepcopy(second_tmp)
    first_sum = first_sum_tmp
    second_sum = second_sum_tmp
    cnt = 0

    while cnt < k:
        heapq.heappush(first, a[N + cnt])
        first_sum += a[N + cnt]
        first_sum -= heapq.heappop(first)
        cnt += 1

    while cnt < N:
        heapq.heappush(second, -a[N + cnt])
        second_sum += a[N + cnt]
        second_sum -= -heapq.heappop(second)
        cnt += 1

    ans = max(ans, first_sum - second_sum)
    # print(first_sum, second_sum)

print(ans)

Submission status: Time Limit Exceeded

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

que1 = []
S = [0] * (2*N + 1)
for i in range(N):
    S[i + 1] = S[i] + a[i]
    que1.append(a[i])
    
que2 = []
T = [0] * (2*N + 1)
for i in range(N):
    T[i + 1] = T[i] + a[3*N - i - 1]
    que2.append(a[3*N - i - 1])

for i in range(N, 2*N):
    mi = min(que1)
    if a[i] > mi:
        S[i + 1] = S[i] - mi + a[i]
        que1.remove(mi)
        que1.append(a[i])
    else:
        S[i + 1] = S[i]
        
for i in range(N, 2*N):
    ma = max(que2)
    if a[3*N - i - 1] < ma:
        T[i + 1] = T[i] - ma + a[3*N - i - 1]
        que2.remove(ma)
        que2.append(a[3*N - i - 1])
    else:
        T[i + 1] = T[i]

res = -float('Inf')
for i in range(N, 2*N + 1):
    res = max(res, S[i] - T[3*N - i])
print(res)

Submission status: Time Limit Exceeded

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左側A[:k] (N<=k<=2*N)までの最大値を求める
# 同様に右側も求める
N = ir()
A = lr()
left_sum = [0] * (N+1)
right_sum = [0] * (N+1)
left = A[:N]; heapify(left)
right = A[-N:]
right = [-x for x in right]
heapify(right)
left_sum[0] = sum(left)
center = A[N:-N]
for i in range(N):
    heappush(left, center[i])
    heappop(left)
    left_sum[i+1] = sum(left)

right_sum[N] = sum(right)
for i in range(N):
    heappush(right, -center[N-1-i])
    heappop(right)
    right_sum[N-1-i] = sum(right)

answer = -10 ** 15
for i in range(N+1):
    temp = left_sum[i] + right_sum[i]
    if temp > answer:
        answer = temp

print(answer)
# 05

Submission status: Time Limit Exceeded

Solution code:
import heapq
import numpy as np 

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

bound = N # 前後の境
h_pre = a_list[:N]
h_post = [-1 * a for a in a_list[2*N:]]
heapq.heapify(h_pre ) 
heapq.heapify(h_post ) 

pre_sum = np.zeros((N+1,1))
post_sum = np.zeros((N+1,1))
pre_sum[0] = sum(h_pre)
post_sum[-1] = -1 *  sum(h_post)

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


ans = np.max(pre_sum - post_sum)

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import numpy as np 

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

bound = N # 前後の境
h_pre = a_list[:N]
h_post = [-1 * a for a in a_list[2*N:]]
heapq.heapify(h_pre ) 
heapq.heapify(h_post ) 

pre_sum = np.zeros((N+1,1))
post_sum = np.zeros((N+1,1))
pre_sum[0] = sum(h_pre)
post_sum[-1] = sum(h_post)

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


ans = np.max(pre_sum + post_sum)

print(int(ans))

Submission status: Time Limit Exceeded

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

ans = -float('inf')
for i in range(n+1):
  fh = list(map(lambda x:x, a[:n+i]))
  sh = a[n+i:]
  heapq.heapify(fh)
  heapq.heapify(sh)
  ans = max(ans, sum(heapq.nlargest(n, fh))-sum(heapq.nsmallest(n, sh)))

print(ans)

Submission status: Time Limit Exceeded

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

Solution code:
import bisect
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

len_left = N
for elem in a[N:2*N]:
    le = bisect.bisect_left(a_right, elem)
    a_right.remove(elem)
    if le < N:
        sum_right -= elem
        sum_right += a_right[N-1]
    ri = bisect.bisect_left(a_left, elem)
    if ri >= len_left - N:
        a_left.insert(ri, elem)
        len_left += 1
        sum_left -= a_left[len_left-N-1]
        sum_left += elem
    res = max(res, sum_left-sum_right)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect
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

len_left = N
for elem in a[N:2*N]:
    le = bisect.bisect_left(a_right, elem)
    a_right.remove(elem)
    if le < N:
        sum_right = sum(a_right[:N])
    ri = bisect.bisect_left(a_left, elem)
    if ri >= len_left - N:
        a_left.insert(ri, elem)
        len_left += 1
        sum_left = sum(a_left[len_left-N:])
    res = max(res, sum_left-sum_right)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import copy


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


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

sum_h1 = [0] * (N+1)
sum_h2 = [0] * (N+1)

'''
N=2
0 1 2 3 4 5 6
3 1 4 1 5 9
'''

h1 = A[0:N]
h2 = A[N*2:N*3]

heapq.heapify(h1)
heapq._heapify_max(h2)

#print("h1", h1)
#print("h2", h2)
sum_h1[0] = sum(h1)
sum_h2[N] = sum(h2)

for k in range(N):
    #print("A[N+k]", A[N+k])
    #print("k+1", k+1)
    heapq.heappushpop(h1, A[N+k])
    sum_h1[k+1] = sum(h1)

    #print("A[2*N-k-1]", A[2*N-k-1])
    #print("N-k-1", N-k-1)
    _heappush_max(h2, A[2*N-k-1])
    _heappop_max(h2)
    sum_h2[N-k-1] = sum(h2)


mx = None

#print("sum_h1", sum_h1)
#print("sum_h2", sum_h2)

for i in range(N+1):
    a = sum_h1[i] - sum_h2[i]

    if(mx == None or a > mx):
        mx = a

print(mx)

'''
for i in range(N+1):
    h1 = A[0:N+i]
    h2 = A[N+i:N*3]

    heapq.heapify(h1)
    heapq._heapify_max(h2)

    for k in range(N):
        if i <= k:
            _heappop_max(h2)
        else:
            heapq.heappop(h1)

    s = sum(h1) - sum(h2)

    if (mx == None or s > mx):
        mx = s
'''

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import copy


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


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

mx = None

for i in range(N+1):
    h1 = A[0:N+i]
    h2 = A[N+i:N*3]

    heapq.heapify(h1)
    heapq._heapify_max(h2)

    for k in range(N):
        if i <= k:
            _heappop_max(h2)
        else:
            heapq.heappop(h1)

    s = sum(h1) - sum(h2)

    if (mx == None or s > mx):
        mx = s

print(mx)

Submission status: Time Limit Exceeded

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

ans = -10**15
for i in range(n, 2*n+1):
    a_front = a[0 : i]
    a_back = a[i : 3*n]
    a_front.sort(reverse=True)
    a_back.sort()
    tmp = sum(a_front[0:n]) - sum(a_back[0:n])
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
a    = [ int(x) for x in input().split() ]
arev = [ -x for x in a[::-1] ]

Hl = a[:N]
heapq.heapify(Hl) #; print(Hl)

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

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

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