Problem:


Score : 500 points

Problem Statement

Let N be a positive integer.

There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}).
Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements.
Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').

Find the maximum possible score of a'.

Constraints

1 ≤ N ≤ 10^5

a_i is an integer.

1 ≤ a_i ≤ 10^9

Partial Score

In the test set worth 300 points, N ≤ 1000.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{3N}

Output

Print the maximum possible score of a'.

Sample Input 1

2
3 1 4 1 5 9

Sample Output 1

1

When a_2 and a_6 are removed, a' will be (3, 4, 1, 5), which has a score of (3 + 4) - (1 + 5) = 1.

Sample Input 2

1
1 2 3

Sample Output 2

-1

For example, when a_1 are removed, a' will be (2, 3), which has a score of 2 - 3 = -1.

Sample Input 3

3
8 2 2 7 4 6 5 3 8

Sample Output 3

5

For example, when a_2, a_3 and a_9 are removed, a' will be (8, 7, 4, 6, 5, 3), which has a score of (8 + 7 + 4) - (6 + 5 + 3) = 5.



Sample input:
2
3 1 4 1 5 9


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

HL0 = aneg[:N-1]
heapq.heapify(HL0) #; print(HL0)

sumL = []
for i in range(N+1):
    heapq.heappush(HL0, aneg[N-1+i])
    H = HL0.copy() #; print(i, H)
    sum_ = 0
    for j in range(N):
        x = heapq.heappop(H) #; print(x) 
        sum_ += x     
    sumL.append(sum_)

    
HR0 = arev[:N-1]
heapq.heapify(HR0) #; print(HR0)

sumR = []
for i in range(N+1):
    heapq.heappush(HR0, arev[N-1+i])
    H = HR0.copy() #;     print(i, H)
    sum_ = 0
    for j in range(N):
        x = heapq.heappop(H) #; print(x) 
        sum_ += x      
    sumR.append(sum_)

# print(sumL, sumR)    
sumL = [-x for x in sumL ]    
sumR = sumR[::-1]

dif = [ i-j for i, j in zip(sumL, sumR) ]

# print(l_sumL, l_sumR) ; print(dif)
print(max(dif))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    rA = list(map(lambda x: -1 * x, A[::-1]))

    MM = A[:N]
    mm = rA[:N]
    heapq.heapify(MM)
    heapq.heapify(mm)
    M = [sum(MM)]
    m = [sum(mm)]

    for i in range(N, 2*N):
        heapq.heappushpop(MM, A[i])
        heapq.heappushpop(mm, rA[i])
        M.append(sum(MM))
        m.append(sum(mm))

    Dm = -10**14
    for i, j in zip(M, m[::-1]):
        if i + j > Dm:
            Dm = i + j

    print(Dm)


main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    heapq.heappop(Q)
    sp = sum(P)
    sq = sum(Q)
    p[i] = sp
    q[i] = sq
ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
import heapq
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)
        j += 1
    while k < N-i:
        heapq.heappop(Q)
        k += 1
    s = sum(P) + sum(Q)
    S.append(s)
ans = max(S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

def solve(R_ite, L_ite, n):
	heapq.heapify(R_ite)
	heapq.heapify(L_ite)

	for _ in range(n):
		heapq.heappop(R_ite)
	for _ in range(N-n):
		heapq.heappop(L_ite)

	return sum(R_ite) + sum(L_ite)

ans = float("inf") * (-1)
for i in range(N+1):
	R = A[:N+i]
	LL = A[N+i:]
	L = [LL[j] * (-1) for j in range(len(LL))]

	ans = max(ans,solve(R,L,i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n=int(input())
a=[int(i) for i in input().split()]
 
ans=float('-inf')
for i in range(n+1):
    a_mae=sorted(a[:n+i],reverse=True)
    a_mae=list(map(lambda x:x*(-1),a_mae))
    a_ushiro=sorted(a[n+i:])
 
    mae=0
    ushiro=0
 
    for j in range(n):
        mae-=heapq.heappop(a_mae)
    for k in range(n):
        ushiro-=heapq.heappop(a_ushiro)
 
    
 
    ans=max(ans,mae+ushiro)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import numpy as np
n=int(input())
a=[int(i) for i in input().split()]

ans=float('-inf')
for i in range(n+1):
    a_mae=sorted(a[:n+i],reverse=True)
    a_mae=list(map(lambda x:x*(-1),a_mae))
    a_ushiro=sorted(a[n+i:])

    mae=0
    ushiro=0

    for j in range(n):
        mae-=heapq.heappop(a_mae)
    for k in range(n):
        ushiro-=heapq.heappop(a_ushiro)

    

    ans=max(ans,mae+ushiro)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import numpy as np
n=int(input())
a=[int(i) for i in input().split()]

ans=float('-inf')
for i in range(n+1):
    a_mae=sorted(a[:n+i])
    a_ushiro=sorted(a[n+i:],reverse=True)
    a_ushiro=list(map(lambda x:x*(-1),a_ushiro))


    for j in range(i):
        heapq.heappop(a_mae)
    for k in range(n-i):
        heapq.heappop(a_ushiro)

    ans=max(ans,sum(a_mae)+sum(a_ushiro))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import numpy as np
n=int(input())
a=[int(i) for i in input().split()]

ans=float('-inf')
for i in range(n+1):
    a_mae=sorted(a[:n+i])
    a_ushiro=sorted(a[n+i:],reverse=True)
    a_ushiro=np.array(a_ushiro)
    a_ushiro=list(a_ushiro*(-1))


    for j in range(i):
        heapq.heappop(a_mae)
    for k in range(n-i):
        heapq.heappop(a_ushiro)

    ans=max(ans,sum(a_mae)+sum(a_ushiro))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10*5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
a = LIST()

a1 = a[:2*n]
a2 = a[n:]
a2.reverse()
for i in range(2*n):
    a2[i] = a2[i]*-1

def searchmax(a):
    maxl = [0]*(n+1)
    left = a[:n]
    center = a[n:]
    heapq.heapify(left)
    maxl[0] = sum(left)
    for i in range(1,n+1):
        heapq.heappushpop(left, center[i-1])
        maxl[i] = sum(left)
    return maxl

maxll = searchmax(a1)
minrr = searchmax(a2)
minrr.reverse()

res = [INF *-1]*(n+1)
for i in range(n+1):
    res[i] = maxll[i] + minrr[i]

print(max(res))

Submission status: Time Limit Exceeded

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

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

ans = -float("inf")
for i in range(n, 2 * n + 1):
    fh = a[:i].copy()
    fh.sort(reverse=True)
    sh = a[i:].copy()
    sh.sort()
    score = sum(fh[:n]) - sum(sh[:n])
    ans = max(ans, score)

print(ans)

Submission status: Time Limit Exceeded

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

l = [0]*n
m = [0]*n
r = [0]*n
for i in range(n):
  l[i] = as_[i]
  m[i] = as_[n+i]
  r[i] = (-1)*as_[2*n+i]

import heapq
heapq.heapify(l)
heapq.heapify(r)

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

for i in range(n+1):
  if i != 0:
    j = i-1
    heapq.heappush(l, m[j])
    heapq.heappop(l)
    l_max = sum(l)
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    heapq.heappop(r)
    r_min = sum(r)
    
  else:
    l_max = sum(l)
    r_min = sum(r)
    
  l_maxs[i] = l_max
  r_mins[i] = r_min

#print(l_maxs)
#print(r_mins)

print(max([l_maxs[i] + r_mins[n-i] for i in range(n+1)]))

Submission status: Time Limit Exceeded

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

l = as_[0:n]
m = as_[n:2*n]
r = as_[2*n:3*n]
r = [(-1)*a for a in r]

import heapq
heapq.heapify(l)
heapq.heapify(r)

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

for i in range(n+1):
  if i != 0:
    j = i-1
    heapq.heappush(l, m[j])
    heapq.heappop(l)
    l_max = sum(l)
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    heapq.heappop(r)
    r_min = sum(r)
    
  else:
    l_max = sum(l)
    r_min = sum(r)
    
  l_maxs[i] = l_max
  r_mins[i] = r_min

#print(l_maxs)
#print(r_mins)

print(max([l_maxs[i] + r_mins[n-i] for i in range(n+1)]))

Submission status: Time Limit Exceeded

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

l = as_[0:n]
m = as_[n:2*n]
r = as_[2*n:3*n]
r = [(-1)*a for a in r]

import heapq
heapq.heapify(l)
heapq.heapify(r)

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

for i in range(n+1):
  if i != 0:
    j = i-1
    heapq.heappush(l, m[j])
    heapq.heappop(l)
    l_max = sum(l)
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    heapq.heappop(r)
    r_min = sum(r)
    
  else:
    l_max = sum(l)
    r_min = sum(r)
    
  l_maxs[i] = l_max
  r_mins[i] = r_min

#print(l_maxs)
#print(r_mins)

d = [0]*(n+1)
for i in range(n+1):
  d[i] = l_maxs[i] + r_mins[n-i]
print(max(d))

Submission status: Time Limit Exceeded

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

l = as_[0:n]
m = as_[n:2*n]
r = as_[2*n:3*n]
r = [(-1)*a for a in r]

import heapq
heapq.heapify(l)
heapq.heapify(r)

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

for i in range(n+1):
  if i == 0:
    l_max = sum(l)
    r_min = sum(r)
  else:
    j = i-1
    heapq.heappush(l, m[j])
    heapq.heappop(l)
    l_max = sum(l)
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    heapq.heappop(r)
    r_min = sum(r)
    
  l_maxs[i] = l_max
  r_mins[i] = r_min

#print(l_maxs)
#print(r_mins)

d = [0]*(n+1)
for i in range(n+1):
  d[i] = l_maxs[i] + r_mins[n-i]
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    n = int(input())
    a = list(map(int, input().split()))
    firstList = sorted(a[:n])
    secondList = sorted(a[n:])
    firstSum = sum(firstList)
    secondSum = sum(secondList[:n])
    ans = firstSum - secondSum
    # print(ans, firstSum, secondSum, firstList, secondList)
    for x in [a[i] for i in range(n, 2 * n)]:
        bisect.insort_left(firstList, x)
        firstList0 = firstList.pop(0)
        secondListn = secondList[n]
        secondList.remove(x)
        firstSum += x - firstList0
        secondSum -= x - secondListn if x < secondListn else 0
        ans = max(ans, firstSum - secondSum)
        # print(ans, firstSum, secondSum, firstList, secondList)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    n = int(input())
    a = list(map(int, input().split()))
    firstList = sorted(a[:n])
    secondList = sorted(a[n:])
    firstSum = sum(firstList)
    secondSum = sum(secondList[:n])
    ans = firstSum - secondSum
    # print(ans, firstSum, secondSum, firstList, secondList)
    for i in range(n, 2 * n):
        firstListn = firstList[-n]
        secondListn = secondList[n]
        bisect.insort_left(firstList, a[i])
        secondList.remove(a[i])
        firstSum += a[i] - firstListn if a[i] > firstListn else 0
        secondSum -= a[i] - secondListn if a[i] < secondListn else 0
        ans = max(ans, firstSum - secondSum)
        # print(ans, firstSum, secondSum, firstList, secondList)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = -float("inf")
    for i in range(n + 1):
        firstSum = sum(sorted(a[:n+i])[-n:])
        secondSum = sum(sorted(a[n+i:])[:n])
        ans = max(ans, firstSum - secondSum)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a = []
for i in range(N):
    heapq.heappush(a,A[i])
B = []
for i in range(3*N):
    B.append(-A[3*N-1-i])
b = []
for i in range(N):
    heapq.heappush(b,B[i])

Red = [sum(a) for i in range(N+1)]
Blue = [sum(b) for i in range(N+1)]
inf = float("inf")
MAX = -inf
AR = []
BB = []
for i in range(N):
    AR.append(A[N+i])
    BB.append(B[N+i])
for i,ar in enumerate(AR):
    l = heapq.heappushpop(a,ar)
    Red[i+1] = Red[i]+(ar-l)
for i,bb in enumerate(BB):
    m = heapq.heappushpop(b,bb)
    Blue[i+1] = Blue[i]+(bb-m)
    
for i in range(N+1):
    #print(Red[i],Blue[N-i])
    MAX = max(MAX,Red[i]+Blue[N-i])

#print(A,B)
print(MAX)

Submission status: Time Limit Exceeded

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

a = []
for i in range(N):
    heapq.heappush(a,A[i])
B = []
for i in range(3*N):
    B.append(-A[3*N-1-i])
b = []
for i in range(N):
    heapq.heappush(b,B[i])

Red = [sum(a) for i in range(N+1)]
Blue = [sum(b) for i in range(N+1)]
inf = float("inf")
MAX = -inf
for i in range(N):
    k = N+i
    l = heapq.heappushpop(a,A[k])
    Red[i+1] = Red[i]+(A[k]-l)
for i in range(N):
    k = N+i
    #print(k)
    m = heapq.heappushpop(b,B[k])
    Blue[i+1] = Blue[i]+(B[k]-m)
    
for i in range(N+1):
    #print(Red[i],Blue[N-i])
    MAX = max(MAX,Red[i]+Blue[N-i])

#print(A,B)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
minB=[]
maxC=[]
d = 0
import heapq
for k in range(N-1, 2*N):
    B = A[:k+1]
    C = A[k+1:]
    minB = heapq.nsmallest(k+1-N, B)
    maxC = heapq.nlargest(2*N-k-1, C)
    s = sum(B) - sum(minB)
    m = sum(C) - sum(maxC)
    
    if k == N-1:
        d = s - m
    if d < s - m:
        d = s - m
print(d)

Submission status: Time Limit Exceeded

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

pq1 = []
for x in a[:N]:
    heappush(pq1, x)

pq2 = sorted(a[N:])

ans = sum(pq1) - sum(pq2[:N])
for k in range(N, 2 * N):
    heappush(pq1, a[k])
    heappop(pq1)    
    pq2.remove(a[k])
    
    ans = max(ans, sum(pq1) - sum(pq2[:N]))
    
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
*A, = map(int, input().split())
INF = 10**16
first = A[:N]
heapify(first)
second = [-a for a in A[2*N:]]
heapify(second)
f = [0]*(N+1)
s = [0]*(N+1)
f[0] = sum(first)
s[N] = - sum(second)
for k in range(1, N+1):
    heappushpop(first, A[N-1+k])
    f[k] = sum(first)
for k in range(N-1, -1, -1):
    heappushpop(second, -A[N+k])
    s[k] = - sum(second)
ans = -INF
for k in range(N+1):
    ans = max(ans, f[k] - s[k])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
from collections import*
n,*a=map(int,open(0).read().split())
ans=-float("inf")
b=a[:n]
c=deque(a[n:])
heapify(b)
s=sum(b)
s2=sum(nsmallest(n,c))
red=[s-s2]
for i in range(n,n*2):
    s+=a[i]-heappushpop(b,a[i])
    c.popleft()
    s2=sum(nsmallest(n,c))
    red+=[s-s2]
print(max(red))

#あｈｊｆｋぁｄｓｈｆｌｋじゃｇはｌｋｊｄｊｇｌｋ；あｊｄｇｌｋ；あｄｓｊｇｌ；あｊｓｄｇｌｋ；あｊｓｄｇｌ；かｓ

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
n,*a=map(int,open(0).read().split())
#print(a)
ans=-float("inf")
for i in range(n,2*n+1):
    score=0
    tmp=a[:i]
    heapify(tmp)
#    print(tmp)
    for j in range(i-n):
        heappop(tmp)
    score+=sum(tmp)
    tmp=a[i:]
    heapify(tmp)
#    print(tmp)
    score-=sum(heappop(tmp)for r in range(n))

    ans=max(score,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n = int(input())
array = [int(i) for i in input().split()]
ans=-1e14
l_array = []
r_array = []
l_sum = [0]*(n+1)
r_sum = [0]*(n+1)

# left-n and right-n numbers
for i in range(n):
    heapq.heappush(l_array, array[i])
    heapq.heappush(r_array, (-array[3*n-1-i], array[3*n-1-i]))

l_sum[0] = sum(l_array)
r_sum[n] = sum([i[1] for i in r_array])

for i in range(n, 2*n):
    heapq.heappush(l_array, array[i])
    heapq.heappush(r_array, (-array[3*n-1-i], array[3*n-1-i]))
    heapq.heappop(l_array)
    heapq.heappop(r_array)

    l_sum[i-n+1] = sum(l_array)
    r_sum[2*n-1-i] = sum([j[1] for j in r_array])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
array = [int(i) for i in input().split()]
ans=-1e14

for i in range(n, 2*n+1):
    l_array = sorted(array[:i]) 
    r_array = sorted(array[i:])
    ans = max(ans, sum(l_array[i-n:])-sum(r_array[:n]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
a = list(map(int, input().split()))
ans = -10000000000
for i in itertools.combinations(a, n):
    b = a[:]
    i = list(i)
    for j in a:
        if j in i:
            i.remove(j)
            b.remove(j)
    ans = max(ans, sum(b[:n]) - sum(b[-n:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
b=list(map(int,input().split()))
sd1=[]
sd2=[]
d1=b[:N]
sd1.append(sum(d1))
d2=b[2*N:]
sd2.append(sum(d2))
Max=sum(d1)-sum(d2)

m=0
while m<N:
    if min(d1) < b[N+m]:
        sd1.append(sd1[m]-min(d1)+b[N+m])
        d1.remove((min(d1)))
        d1.append(b[N+m])
    else:
        sd1.append(sd1[m])
    if max(d2) > b[2*N-m-1]:
        sd2.append(sd2[m]-max(d2)+b[2*N-m-1])
        d2.remove((max(d2)))
        d2.append(b[2*N-m-1])
    else:
        sd2.append(sd2[m])
    m+=1


m=0
while m<=N:
    if Max < (sd1[m]-sd2[N-m]):
        Max=sd1[m]-sd2[N-m]
    m+=1
    
print(Max)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
b=list(map(int,input().split()))
sd1=[]
sd2=[]
"""
while m <= N:
    #d1=heapq.nlargest(N,b[:2*N-m])
    d1=sorted(b[:2*N-m], reverse=True)[:N]
    #d2=heapq.nsmallest(N,b[2*N-m:])
    d2=sorted(b[2*N-m:])[:N]
    Max.append(sum(d1)-sum(d2))
    m+=1
"""
d1=b[:N]
sd1.append(sum(d1))
d2=b[2*N:]
sd2.append(sum(d2))
Max=sum(d1)-sum(d2)

m=0
while m<N:
    if min(d1) < b[N+m]:
        sd1.append(sd1[m]-min(d1)+b[N+m])
        d1.remove((min(d1)))
        d1.append(b[N+m])
    else:
        sd1.append(sd1[m])
    m+=1

m=0
while m<N:
    if max(d2) > b[2*N-m-1]:
        sd2.append(sd2[m]-max(d2)+b[2*N-m-1])
        d2.remove((max(d2)))
        d2.append(b[2*N-m-1])
    else:
        sd2.append(sd2[m])
    m+=1

m=0
while m<=N:
    if Max < (sd1[m]-sd2[N-m]):
        Max=sd1[m]-sd2[N-m]
    m+=1
    
print(Max)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
b=list(map(int,input().split()))
sd1=[]
sd2=[]
"""
while m <= N:
    #d1=heapq.nlargest(N,b[:2*N-m])
    d1=sorted(b[:2*N-m], reverse=True)[:N]
    #d2=heapq.nsmallest(N,b[2*N-m:])
    d2=sorted(b[2*N-m:])[:N]
    Max.append(sum(d1)-sum(d2))
    m+=1
"""
d1=b[:N]
sd1.append(sum(d1))
d2=b[2*N:]
sd2.append(sum(d2))
Max=sum(d1)-sum(d2)
m=0
while m<N:
    if min(d1) < b[N+m]:
        d1.remove((min(d1)))
        d1.append(b[N+m])
    sd1.append(sum(d1))
    m+=1
m=0
while m<N:
    if max(d2) > b[2*N-m-1]:
        d2.remove((max(d2)))
        d2.append(b[2*N-m-1])
    sd2.append(sum(d2))
    m+=1
m=0
while m<=N:
    if Max < (sd1[m]-sd2[N-m]):
        Max=sd1[m]-sd2[N-m]
    m+=1

print(Max)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N=int(input())
b=list(map(int,input().split()))
Max=[]
m=0
while m <= N:
    #d1=heapq.nlargest(N,b[:2*N-m])
    d1=sorted(b[:2*N-m], reverse=True)[:N]
    #d2=heapq.nsmallest(N,b[2*N-m:])
    d2=sorted(b[2*N-m:])[:N]
    Max.append(sum(d1)-sum(d2))
    m+=1

#print(Max)
print(max(Max))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N=int(input())
b=list(map(int,input().split()))
Max=[]
m=0
while m <= N:
    d1=heapq.nlargest(N,b[:2*N-m])
    d2=heapq.nsmallest(N,b[2*N-m:])
    Max.append(sum(d1)-sum(d2))
    m+=1

#print(Max)
print(max(Max))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N=int(input())
a=input().split()
n=0
b=[]
Max=[]
while n < 3*N:
    b.append(int(a[n]))
    n+=1

m=0
while m <= N:
    d1=heapq.nlargest(N,b[:2*N-m])
    d2=heapq.nsmallest(N,b[2*N-m:])
    Max.append(sum(d1)-sum(d2))
    m+=1

print(max(Max))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [long(input_raw[0])]
    A_list = []
    input_raw = read_func().strip().split()
    for i in range(3* N):
        A_list.append(long(input_raw[i]))


    max_score = -sys.maxint
    L_min = sys.maxint
    R_max = -sys.maxint
    for i in range(N + 1):
       # if i == 0:
            AL_list = A_list[:N + i]
            AR_list = A_list[N + i:]
            AL_list = sorted(AL_list, reverse=True)
            AR_list = sorted(AR_list)
            L_sum = sum(AL_list[:N])
            R_sum = sum(AR_list[:N])
            max_score = max(max_score, (L_sum - R_sum))
            L_min = AL_list[0]
            R_min = AR_list[0]
##        else:
##            A = A_list[N + i]
##            if L_min < A:
##                L_sum = (L_sum - L_min) + A
##            if R_max > A:
##                R_sum = R_sum - A +
##
    print max_score


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from queue import PriorityQueue
try:
    from typing import List, Tuple, Dict
except ImportError:
    pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


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

hoge = 0
for i in range(N):
    for j in range(N):
        hoge += 1


left_queue = PriorityQueue()  # type: PriorityQueue[Tuple[int, None]]

for i in range(N):
    item = (a[i], None)
    left_queue.put(item)


score = sum(a[:N])
left_scores = [score]

for i in range(N, 2*N):
    b, none = left_queue.get()
    if a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (a[i], None)
        dscore = a[i] - b
    left_queue.put(item)
    score += dscore
    left_scores.append(score)


right_queue = PriorityQueue()  # type: PriorityQueue[Tuple[int, None]]

for i in range(2*N, 3*N):
    item = (-a[i], None)
    right_queue.put(item)


score = - sum(a[2*N:])
right_scores = [score]

for i in range(2*N-1, N-1, -1):
    b, none = right_queue.get()
    if -a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (-a[i], None)
        dscore = -a[i] - b
        # debug(a[i], b, i)
    right_queue.put(item)
    # debug(item, score, dscore)
    score += dscore
    right_scores.append(score)


scores = []
for i in range(N+1):
    scores.append(left_scores[i] + right_scores[N-i])

debug(scores)
print(max(scores))

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
numbers = map(int, raw_input().split())
result = -3*(10**14)
for i in range (n+1):
	a = numbers[0:n+i]
	b = numbers[n+i:]
	s = sorted(a)
	d1 = sum(s[0:i])
	t = sorted(b)
	t = t[::-1]
	d2 = sum(t[:n-i])
	c = sum(a) + d2 - (sum(b) + d1)
	if c > result:
		result = c
print result

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
import heapq
q=a[:n]
rq=[-a[i] for i in range(2*n,3*n)[::-1]]
d=[sum(q)]
rd=[sum(rq)]

heapq.heapify(q)
heapq.heapify(rq)

for i in range(n,2*n):
 heapq.heappush(q, a[i])
 heapq.heappop(q)
 d.append(sum(q))
for i in range(n,2*n)[::-1]:
 heapq.heappush(rq, -a[i])
 heapq.heappop(rq)
 rd.append(sum(rq))
c=-float("inf")
for i in range(len(d)):
  c=max(c,d[i]+rd[len(rd)-1-i])
print(c)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
from bisect import bisect_left, insort
N = int(input())
A = inpl()

before = sorted(A[:N])
after = sorted(A[N:])
x = sum(before)
y = sum(after[:N])
score = x - y

for i in range(N):
    insort(before, A[N+i])
    del after[bisect_left(after, A[N+i])]
    score = max(score, sum(before[-N:]) - sum(after[:N]))

print(score)

Submission status: Time Limit Exceeded

Solution code:
import sys


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


# sys.stdin = open('d1.in')
n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
B = []
for i in range(n,2*n + 1):
	A1 = A[:i]
	A2 = A[i:]
	a1 = i - n
	a2 = 2 * n - i
	A1.sort()
	A1 = A1[a1:]
	A2.sort()
	if a2 != 0:
		A2 = A2[:-a2]
	#print(A1,A2)
	B.append(sum(A1) - sum(A2))
#print(B)
print(max(B))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import bisect


def calc_l_score(N, a):
    scores = [None] * (N + 1)
    queue = sorted(a[:N])
    scores[0] = sum(queue)
    for i in range(N):
        na = a[N + i]
        bisect.insort(queue, na)
        m = queue.pop(0)
        scores[i + 1] = scores[i] + na - m
    return scores


def calc_r_score(N, a):
    scores = [None] * (N + 1)
    queue = sorted(a[2 * N:])
    scores[-1] = sum(queue)
    for i in range(1, N + 1):
        na = a[-N - i]
        bisect.insort(queue, na)
        m = queue.pop(-1)
        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: Time Limit Exceeded

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)

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] = sr[i + 1]
    else:
        sr[i] = sr[i + 1] - min(ar, ai) + max(ar, ai)
    heapq.heappush(qr, max(ar, ai))

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

print(ans)

Submission status: Time Limit Exceeded

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

INF=-100000000000000

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

Solution code:
n = int(input())

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

d = []
for i in range(n,2*n+1):
    l=a[0:i]
    r=a[i:3*n]
    l.sort(reverse=True)
    r.sort()
    l=l[0:n]
    r=r[0:n]
    d.append(sum(l)-sum(r))
print(max(d))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = -1e30
for i in range(n, 2 * n + 1):
    al = list(reversed(sorted(a[:i])))[:n]
    ar = sorted(a[i:])[:n]
    ans = max(ans, sum(al) - sum(ar))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
n = input()
A = map(int, raw_input().split())
left = [None]*(3*n+1)
right = [None]*(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
    if len(que) == n:
        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
    if len(que) == n:
        right[i] = rsum
ans = -10**18
for i in xrange(3*n):
    if left[i] is not None and right[i+1] is not None:
        ans = max(ans, left[i] - right[i+1])
print ans

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
INF = float("inf")
from heapq import heappop, heappush

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

def main():
	N = int(input())
	A = getlist()
	left = 0
	leftlis = [0] * (N + 1)
	rightlis = [0] * (N + 1)
	Q = []
	for i in range(N):
		left += A[i]
		heappush(Q, A[i])
	leftlis[0] = left

	for i in range(N, 2 * N):
		heappush(Q, A[i])
		left -= heappop(Q)
		left += A[i]
		leftlis[i + 1 - N] = left

	Q = []
	right = 0
	for i in range(3 * N - 1, 2 * N - 1, -1):
		right -= A[i]
		heappush(Q, -A[i])

	rightlis[0] = right

	for i in range(2 * N - 1, N - 1, -1):
		heappush(Q, -A[i])		
		right -= heappop(Q)
		right -= A[i]
		rightlis[2 * N - i] = right

	rightlis = list(reversed(rightlis))
	# print(leftlis)
	# print(rightlis)
	ans = -INF
	for i in range(N + 1):
		ans = max(ans, leftlis[i] + rightlis[i])

	print(ans)

if __name__ == '__main__':
	main()