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:
maxi=-10**99 
n=int(input())
l=[int(i) for i in input().split()]
k=n
for i in range(n-1,2*n):
    z1=l[:i+1]
    z2=l[i+1:]
    #print(z1,z2)
    z1.sort(reverse=1)
    z2.sort()
  #  print(i)
   # print(sum(z1[:k]))
   # print(sum(z2[:k]))
    maxi=max(maxi,sum(z1[:k])-sum(z2[:k]))
print(maxi)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
As = list(map(int, input().split()))
rs = []
for k in range(N, 2*N+1):
  q1 = []
  for i in range(0, N):
    heapq.heappush(q1, As[i])
  q2 = []
  for i in range(2*N, 3*N):
    heapq.heappush(q2, -As[i])
  for i in range(N, k):
    if q1[0] < As[i]:
      heapq.heapreplace(q1, As[i])
  for i in reversed(range(k, 2*N)):
    if q2[0] < -As[i]:
      heapq.heapreplace(q2, -As[i])
  r = sum(q1)+sum(q2)
  #print(k, q1, q2, r)
  rs.append(r)
r = max(rs)
print(r)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  an = []
  a2n = a[n:2*n]
  a3n = []
  for i in range(n):
    heapq.heappush(an,a[i])
    heapq.heappush(a3n,-1*a[i+2*n])
  ta2n = a2n
  suman = [sum(an)]
  suma3n = [-1*sum(a3n)]
  for i in range(n):
    tmp = ta2n[i]
    heapq.heappush(an,tmp)
    heapq.heappop(an)
    suman.append(sum(an))
  for i in range(n):
    tmp = ta2n[n-i-1]
    heapq.heappush(a3n,-1*tmp)
    heapq.heappop(a3n)
    suma3n.append(-1 * sum(a3n))

  ans = -10000000000000000
  for i in range(n+1):
    tmpans = suman[i]-suma3n[n-i]
    ans = max(ans,tmpans)
  print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int,input().split()))
inf = float('inf')
ans = -inf

for i in range(N-1,2*N):
    a_fr = sorted(a[:i+1])
    a_ba = a[i+1:]
    a_ba = sorted(list(map(lambda n:n*(-1), a_ba)))
    a_fr = a_fr[len(a_fr) - N:]
    a_ba = a_ba[len(a_ba) - N:]
    ans = max(ans, sum(a_fr)+sum(a_ba))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#%%
import heapq
ans = []

N = int(input())
a = list(map(int, input().split()))
for i in range(N+1):
    left = a[:N+i]
    heapq.heapify(left)
    right = a[N+i:]
    for j in range(len(right)):
        right[j] = -right[j]
    heapq.heapify(right)

    for j in range(i):
        heapq.heappop(left)
    for j in range(N-i):
        heapq.heappop(right)
    
    tmp = sum(left) + sum(right)
    ans.append(tmp)

print(max(ans))
#print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a1 = a[:n]
a1.sort()
sum_a1 = [sum(a1)]
a2 = a[2 * n:3 * n]
a2.sort()
sum_a2 = [sum(a2)]

for i in range(n):
    bisect.insort(a1, a[n + i])
    sum_a1.append(sum_a1[-1] + a[n + i] - a1[0])
    a1.pop(0)
for i in range(n):
    bisect.insort(a2, a[2 * n - i - 1])
    sum_a2.append(sum_a2[-1] + a[2 * n - i - 1] - a2[-1])
    a2.pop()

sum_a2.reverse()
gap = []
for i in range(n + 1):
    gap.append(sum_a1[i] - sum_a2[i])
print(max(gap))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
al=a[0:n]
am=a[n:2*n]
ar=a[n:3*n]

import bisect
al.sort()
ls=sum(al)
ar.sort()
rs=sum(ar[0:n])
ans=ls-rs
for i in range(n):
    p=am[i]
    l=bisect.bisect_left(al,p)
    if l>i:
        ls=ls-al[i]+p
        al.insert(l,p)
    else:
        al.insert(l,p)
    r=bisect.bisect_left(ar,p)
    if r>n:
        del ar[r]
    elif r<=n:
        rs=rs-p+ar[n]
        del ar[r]
    ans=max(ans,ls-rs)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(_) for _ in input().split()]
ans=-10**15
for i in range(n,2*n+1):ans=max(ans, sum(sorted(a[:i])[i-n:])-sum(sorted(a[i:])[:n]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(_) for _ in input().split()]
ans=-10**15
for i in range(n,2*n+1):ans=max(ans, sum(sorted(a[:i])[::-1][:n])-sum(sorted(a[i:])[:n]))
print(ans)

Submission status: Time Limit Exceeded

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

def check(k):
    heap = []
    for i in range(k):
        heapq.heappush(heap, -1 * a[i])

    tmp = 0
    for _ in range(N):
        tmp -= heapq.heappop(heap)

    heap = []
    for i in range(k, 3 * N):
        heapq.heappush(heap, a[i])

    for _ in range(N):
        tmp -= heapq.heappop(heap)
    # print (tmp)
    return tmp

ans = -1 * 10 ** 20
for i in range(N, 2*N+1):
    ans = max(ans, check(i))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int,input().split()))
ans = -float('inf')
for i in range(N+1):
    L = a[:i+N]
    R = a[i+N:]
    L.sort()
    R.sort()
    ans = max(ans,sum(L[-N:]) - sum(R[:N]))
print(ans)

Submission status: Time Limit Exceeded

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

b = sorted(a[:n])
s  = sum(b)
f = [s]
for i in range(0,n):
  x = a[n+i]
  bisect.insort(b,x)
  y = b.pop(0)
  s += x-y
  f += [s]

b = sorted(a[2*n:])
s  = sum(b)
g = [s]
for i in range(0,n):
  x = a[2*n-1-i]
  bisect.insort(b,x)
  y = b.pop(-1)
  s += x-y
  g += [s]
        

print(max([ f[i] - g[n-i] for i in range(n+1)]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
As = list(map(int, input().split()))
fa = As[:N]
heapq.heapify(fa)
la = As[N:]
sla = sorted(la)
bigla = sla[N:]
smala = sla[:N]
f = sum(fa)
l = sum(smala)
ans = f - l
for i in range(1, N+1):
    x = As[N-1+i]
    heapq.heappush(fa, x)
    f = f + x - heapq.heappop(fa)
    y = smala[-1]
    if x <= y:
        l = l - x + bigla[0]
        smala.append(bigla[0])
        bigla = bigla[1:]
       
    else:
        lo = 0
        up = len(bigla)-1
        if x == bigla[up]:
            bigla.pop()
        elif x == bigla[0]:
            bigla = bigla[1:]
        else:
            while up - lo > 1:
                mid = (up+lo)//2
                if x >= bigla[mid]:
                    lo = mid
                else:
                    up = mid
            bigla = bigla[:lo]+bigla[lo+1:]
    if f-l > ans:
        ans = f-l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import collections
N = int(input())
As = list(map(int, input().split()))
fa = As[:N]
heapq.heapify(fa)
la = As[N:]
sla = sorted(la)
bigla = sla[N:]
smala = sla[:N]
f = sum(fa)
l = sum(smala)
ans = f - l
for i in range(1, N+1):
    x = As[N-1+i]
    heapq.heappush(fa, x)
    f = f + x - heapq.heappop(fa)
    y = smala[-1]
    if x <= y:
        l = l - x + bigla[0]
        smala.append(bigla[0])
        bigla = bigla[1:]
       
    else:
        lo = 0
        up = len(bigla)-1
        if x == bigla[up]:
            bigla.pop()
        elif x == bigla[0]:
            bigla = bigla[1:]
        else:
            while up - lo > 1:
                mid = (up+lo)//2
                if x >= bigla[mid]:
                    lo = mid
                else:
                    up = mid
            bigla = bigla[:lo]+bigla[lo+1:]
    if f-l > ans:
        ans = f-l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n=int(input())
A=[int(i) for i in input().split()]
AL=A[:n]
AR=[]
for i in range(2*n,3*n):
  AR.append(-A[i])
ALS,ARS=[0]*(n+1),[0]*(n+1)
ALS[0],ARS[0]=sum(AL),-sum(AR)
heapq.heapify(AL)
heapq.heapify(AR)
for i in range(n):
  heapq.heappushpop(AL,A[n+i])
  ALS[i+1]+=sum(AL)
  heapq.heappushpop(AR,-A[2*n-i-1])
  ARS[i+1]+=-sum(AR)
ARS=ARS[::-1]
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]-ARS[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n=int(input())
A=[int(i) for i in input().split()]
AL=A[:n]
ALS=[0]*(n+1)
ALS[0]=sum(AL)
heapq.heapify(AL)
for i in range(n):
  heapq.heappushpop(AL,A[n+i])
  ALS[i+1]+=sum(AL)
AR=[]
for i in range(2*n,3*n):
  AR.append(-A[i])
ARS=[0]*(n+1)
ARS[0]=-sum(AR)
heapq.heapify(AR)
for i in range(n):
  heapq.heappushpop(AR,-A[2*n-i-1])
  ARS[i+1]+=-sum(AR)
ARS=ARS[::-1]
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]-ARS[i])
print(ans)

Submission status: Time Limit Exceeded

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

ans = -10**14

for i in range(N+1):
    left = sorted(A[:N+i])
    right = sorted(A[N+i:])
    diff = sum(left[i:]) - sum(right[:N])
    ans = max(ans, diff)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

former_heap = A[:N]
heapq.heapify(former_heap)
former_sum = sum(A[:N])

latter = sorted(A[N:])
latter_sum = sum(latter[:N])

answer = former_sum - latter_sum
#print(A[:N], sorted(A[N:])[:N], answer)

for i in range(1,N+1):
  #former
  #print(former_heap)
  heapq.heappush(former_heap, A[N+i-1])
  x = heapq.heappop(former_heap)
  former_sum = former_sum + A[N+i-1] - x
  #print(former_heap, x)
  
  #latter
  latter.remove(A[N+i-1])
  

  a=former_sum - sum(latter[:N])
  #print(former_sum, latter, sum(latter[:N]), a)
  answer=max(a,answer)
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

answer=-1e15

former = sorted(A[:N-1])
latter = sorted(A[N-1:])

for i in range(N+1):
  former.insert(bisect.bisect_left(former, A[N+i-1]), A[N+i-1])
  latter.remove(A[N+i-1])
  
  a=sum(former[-N:]) - sum(latter[:N])
  answer=max(a,answer)
  
print(answer)

Submission status: Time Limit Exceeded

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

answer=-1e15

for i in range(N+1):
  a=sum(sorted(A[:N+i], reverse=True)[:N]) - sum(sorted(A[N+i:])[:N])
  answer=max(a,answer)
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n = int(input())

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

func = lambda p: p * (-1)

b = list(map(func,a[:]))

#print(a)
#print(b)

l = [0] * (3*n)

first = a[0:n]
second = b[2*n:3*n]

x = [0] * (3*n)
y = [0] * (3*n)

x[n-1] = sum(first)
y[2*n-1] = sum(second)

heapq.heapify(first)
heapq.heapify(second)

for i in range(n,2*n):
    heapq.heappushpop(first, a[i])
    x[i] = sum(first)

for i in range(n,2*n):
    heapq.heappushpop(second, b[-i-1])
    y[-i-2] = sum(second)
    
for i in range(n-1,2*n):
    l[i] = x[i] + y[i]
    
#print(x)
#print(y)
#print(l)

print(max(l[n-1:2*n]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

l = [0] * (3*n)

first = a[0:n]
second = a[2*n:3*n]

x = [0] * (3*n)
y = [0] * (3*n)

x[n-1] = sum(first)
y[2*n-1] = sum(second)

for i in range(n,2*n):
    first.append(a[i])
    first.remove(min(first))
    x[i] = sum(first)

for i in range(n,2*n):
    second.append(a[-i-1])
    second.remove(max(second))
    y[-i-2] = sum(second)
    
for i in range(n-1,2*n):
    l[i] = x[i] - y[i]
    
#print(x)
#print(y)
#print(l)

print(max(l[n-1:2*n]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy

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

ante, post = alist[:n], alist[-n:]
startante = sum(ante)
startpost = sum(post)
post = list(map(lambda x: -x, post))
heapq.heapify(ante)
heapq.heapify(post)

ans = None
for k in range(n+1):
  _ante = copy.deepcopy(ante)
  _post = copy.deepcopy(post)
  antesum = startante
  postsum = startpost
  for a in alist[n: n+k]:
    minante = heapq.heappushpop(_ante, a)
    antesum = antesum + a - minante
  for a in alist[n+k: 2*n]:
    maxpost = heapq.heappushpop(_post, -a)
    postsum = postsum + a + maxpost
  if ans is None:
    ans = antesum - postsum
  elif ans < antesum - postsum:
    ans = antesum - postsum
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import deque
import bisect
x,y,z=[],[],[]
for i in range(3*N):
    if 0<=i<N:x.append(A[i])
    elif N<=i<2*N:y.append(A[i])
    elif 2*N<=i<3*N:z.append(A[i])

a=x+y
a.sort()
mae=[sum(a[N:2*N])]
line=N-1
used=set()
for i in range(N-1,-1,-1):
    while line in used:
        line-=1
    idx=bisect.bisect_left(a,y[i])
    while idx in used:
        idx+=1
    used|={idx,}
    if line<idx:
        mae.append(mae[-1]-a[idx]+a[line])
        line-=1
    elif line==idx:
        mae.append(mae[-1])
        line-=1
    else:
        mae.append(mae[-1])

b=y+z
b.sort()
ushiro=[-1*sum(b[0:N])]
line=N
used=set()
for i in range(N):
    while line in used:
        line+=1
    idx=bisect.bisect_left(b,y[i])
    while idx in used:
        idx+=1
    used|={idx,}
    if idx<line:
        ushiro.append(ushiro[-1]+b[idx]-b[line])
        line+=1
    elif idx==line:
        ushiro.append(ushiro[-1])
        line+=1
    else:
        ushiro.append(ushiro[-1])
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import deque
import bisect
x,y,z=[],[],[]
for i in range(3*N):
    if 0<=i<N:x.append(A[i])
    elif N<=i<2*N:y.append(A[i])
    elif 2*N<=i<3*N:z.append(A[i])
a=x+y
a.sort()
mae=[sum(a[N:2*N])]
for i in range(N-1,-1,-1):
    idx=bisect.bisect_left(a,y[i])
    if y[i]>a[-1*N-1]:
        mae.append(mae[-1]-a[idx]+a[-1*N-1])
        a.pop(idx)
    else:
        mae.append(mae[-1])
        a.pop(idx)
b=y+z
b.sort()
ushiro=[-1*sum(b[0:N])]
for i in range(N):
    idx=bisect.bisect_left(b,y[i])
    if y[i]<b[N]:
        ushiro.append(ushiro[-1]+b[idx]-b[N])
        b.pop(idx)
    else:
        ushiro.append(ushiro[-1])
        b.pop(idx)
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import deque
x,y,z=[],[],[]

for i in range(3*N):
    if 0<=i<N:x.append(A[i])
    elif N<=i<2*N:y.append(A[i])
    elif 2*N<=i<3*N:z.append(A[i])
a=x
b=y+z
a.sort(reverse=True)
b.sort()
ans=sum(a[0:N])-sum(b[0:N])
for i in range(N):
    a=x+y[0:i+1]
    b=z+y[i+1:N]
    a.sort(reverse=True)
    b.sort()
    ans=max(ans,sum(a[0:N])-sum(b[0:N]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

p = [0] * (n + 1)
q = [] + p

L = [] + a[:n]
R = [] + a[n * 2:]
C = [] + a[n:n * 2]

p[0] = sum(L)
q[n] = sum(R)

L.sort()
R.sort()

for i in range(n):
    if C[i] > L[0]:
        p[i + 1] = p[i] + C[i] - L[0]
        del L[0]
        L.insert(bisect_left(L, C[i]), C[i])
    else:
        p[i + 1] = p[i]
    if C[n - 1 - i] < R[n -1]:
        q[n - 1 - i] = q[n - i] + C[n - 1 - i] - R[n - 1]
        del R[n - 1]
        R.insert(bisect_left(R, C[n - 1 - i]), C[n - 1 - i])
    else:
        q[n - 1 - i] = q[n - i]

ans = p[0] - q[0]
for i in range(1, n + 1):
    ans = max(ans, p[i] - q[i])

print(ans)

Submission status: Time Limit Exceeded

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from bisect import insort, bisect_left

N = int(input())
aN = list(map(int, input().split()))
mids = aN[N:N*2]
L = sorted(aN[:N])
R = sorted(aN[N:])

ans = sum(L) - sum(R[:N])
for i in range(N):
    insort(L, mids[i])
    R.pop(bisect_left(R, mids[i]))
    ans = max(sum(L[-N:]) - sum(R[:N]), ans)
print(ans)

Submission status: Time Limit Exceeded

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

b = sorted(a[:n])
s  = sum(b)
f = [0]*(n+1)
f[0] = s
for i in range(0,n):
  x = a[n+i]
  if x > b[0]:
    s -= b.pop(0)
    bisect.insort(b,x)
    s += x
  f[i+1] = s
# print(f)

b = sorted(a[2*n:])
s  = sum(b)
g = [0]*(n+1)
g[0] = s
for i in range(0,n):
  x = a[2*n-1-i]
  if x < b[-1]:
    s -= b.pop(-1)
    bisect.insort(b,x)
    s += x
  g[i+1] = s
# print(g)

h = [ f[i] - g[n-i] for i in range(n+1)]
print(max(h))

Submission status: Time Limit Exceeded

Solution code:
import copy as cp
n = int(input())
a = input().split()
a = [int(m) for m in a]
t1 = []
t2 = []
t3 = []
for i in range(3 * n):
    if i < (3 * n) // 3:
        t1.append(a[i])
    elif (3 * n) // 3 <= i < (3 * n) // 3 * 2:
        t2.append(a[i])
    else:
        t3.append(a[i])
t1.sort()
t3.sort(reverse=True)
t2c = cp.deepcopy(t2)
t1c = cp.deepcopy(t1)
t3c = cp.deepcopy(t3)
y = []
for i in range(n + 1):
    if i == 0:
        u = sum(t1c)
        for j in range(n + 1):
            if j == 0:
                w = sum(t3c)
                x = u - w
                y.append(x)
            else:
                t3c.sort(reverse=True)
                t3c = t3c[1:] + t2c[-1:]
                t2c = t2c[:-1]
                w = sum(t3c)
                x = u - w
                y.append(x)
            t1c = t1
            t2c = t2
            t3c = t3
    else:
        t1c.sort()
        t1c = t1c[1:] + t2c[0:1]
        t2c = t2c[1:]
        u = sum(t1c)
        for j in range(n + 1 - i):
            if j == 0:
                w = sum(t3c)
                x = u - w
                y.append(x)
            else:
                t3c.sort(reverse=True)
                t3c = t3c[1:] + t2c[-1:]
                t2c = t2c[:-1]
                w = sum(t3c)
                x = u - w
                y.append(x)
        t2c = t2
        t3c = t3
        t1c = t1
print(max(y))

Submission status: Time Limit Exceeded

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


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))
    h.heappushpop(tail, -A[-k-1])
    sum_blue.append(-sum(tail))


print(max([r-b for r, b in zip(sum_red, sum_blue[::-1])]))

Submission status: Time Limit Exceeded

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


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))
    h.heappushpop(tail, -A[-k-1])
    sum_blue.append(-sum(tail))


# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

diff = [r-b for r, b in zip(sum_red, sum_blue)]
print(max(diff))

Submission status: Time Limit Exceeded

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


# use 0 based index
sum_red, sum_blue = [], []

# sum_redを制作
head = A[:N]
h.heapify(head)
sum_red.append(sum(head))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))


# sum_blueを制作
# 最大値をpopしてほしいがそれができないのですべて負にすることで擬似的に最大値をpopする
tail = [-x for x in A[-N:]]
h.heapify(tail)
sum_blue.append(-sum(tail))
for k in range(2*N-1, N-1, -1):
    h.heappushpop(tail, -A[k])
    sum_blue.append(-sum(tail))

# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

diff = [r-b for r, b in zip(sum_red, sum_blue)]
print(max(diff))

Submission status: Time Limit Exceeded

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


def reverse(x):
    return -x


# use 0 based index
sum_red, sum_blue = [], []

# sum_redを制作
head = A[:N]
h.heapify(head)
sum_red.append(sum(head))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))


# sum_blueを制作
# 最大値をpopしてほしいがそれができないのですべて負にすることで擬似的に最大値をpopする
tail = list(map(reverse, A[-N:]))
h.heapify(tail)
sum_blue.append(-sum(tail))
for k in range(2*N-1, N-1, -1):
    h.heappushpop(tail, -A[k])
    sum_blue.append(-sum(tail))

# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

diff = [r-b for r, b in zip(sum_red, sum_blue)]
print(max(diff))

Submission status: Time Limit Exceeded

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


def reverse(x):
    return -x


# use 0 based index
sum_red, sum_blue = [], []

# sum_redを制作
head = A[:N]
h.heapify(head)
sum_red.append(sum(head))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))


# sum_blueを制作
# 最大値をpopしてほしいがそれができないのですべて負にすることで擬似的に最大値をpopする
tail = list(map(reverse, A[-N:]))
h.heapify(tail)
sum_blue.append(-sum(tail))
for k in range(2*N-1, N-1, -1):
    h.heappushpop(tail, -A[k])
    sum_blue.append(sum(list(map(reverse, tail))))

# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

diff = [r-b for r, b in zip(sum_red, sum_blue)]
print(max(diff))

Submission status: Time Limit Exceeded

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


def reverse(x):
    return -x


# use 0 based index
sum_red, sum_blue = [], []

# sum_redを制作
head = A[:N]
h.heapify(head)
sum_red.append(sum(head))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))


# sum_blueを制作
# 最大値をpopしてほしいがそれができないのですべて負にすることで擬似的に最大値をpopする
tail = list(map(reverse, A[-N:]))
h.heapify(tail)
sum_blue.append(-sum(tail))
for k in range(2*N-1, N-1, -1):
    h.heappushpop(tail, -A[k])
    sum_blue.append(sum(list(map(reverse, tail))))

# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

from numpy import array
diff = array(sum_red) - array(sum_blue)
print(max(diff))

Submission status: Time Limit Exceeded

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


def reverse(x):
    return -x


# use 0 based index
sum_red, sum_blue = [], []

# sum_redを制作
head = A[:N]
h.heapify(head)
sum_red.append(sum(head))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))


# sum_blueを制作
# 最大値をpopしてほしいがそれができないのですべて負にすることで擬似的に最大値をpopする
tail = list(map(reverse, A[-N:]))
h.heapify(tail)
sum_blue.append(-sum(tail))
for k in range(2*N-1, N-1, -1):
    h.heappushpop(tail, -A[k])
    sum_blue.append(sum(list(map(reverse, tail))))

# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

import numpy as np
diff = np.array(sum_red) - np.array(sum_blue)
print(max(diff))

Submission status: Time Limit Exceeded

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

X = A[0:N]
B = A[N:2*N]
Y = [-_ for _ in A[2*N:3*N]]

heapq.heapify(X)
heapq.heapify(Y)

x = [sum(X)]
y = [sum(Y)]

for i in range(N):
    x += [B[i] - heapq.heappushpop(X, B[i])]
    y += [-B[-1-i] - heapq.heappushpop(Y, -B[-1-i])]

for i in range(N):
    x[i+1] = x[i]+x[i+1]
    y[i+1] = y[i]+y[i+1]

print(max([x[_] + y[::-1][_] for _ in range(N+1)]))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
score=[0]*(N+1)
score[0]=sum(A[0:N])-sum(sorted(A[N:3*N])[0:N])
former=sorted(A[0:N-1])
latter=A[N:3*N]
for i in range(1,N+1):
  score[i]=score[i-1]+A[N+i-1]-A[N+i-2]
  if former!=[]:
    if former[0]<A[N+i-2]:
      score[i]+=A[N+i-2]-former[0]
      del former[0]
      former.append(A[N+i-2])
      former.sort(key=lambda x:x)
  if sorted(latter)[N-1]>=A[N+i-1]:
    score[i]+=A[N+i-1]-sorted(latter)[N]
  del latter[0]
print(max(score))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy
n=int(input())
a=list(map(int,input().split()))
m1=min(a[:n])
s1=sum(a[:n])
ca=copy.deepcopy(a)
f=ca[:n]
heapq.heapify(f)
fs=sum(ca[:n])
t=ca[n:]
ls=sum(heapq.nsmallest(n,t))
ans=fs-ls
for i in range(n,2*n):
    heapq.heappush(f,a[i])
    fs=fs+a[i]-heapq.heappop(f)
    t=a[i+1:]
    ls=sum(heapq.nsmallest(n,t))
    ans=max(ans,fs-ls)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq, copy
N = int(input())
A = [int(i) for i in input().split()]
Aleft = copy.deepcopy(A[:N])
sumLeft = sum(Aleft)
heapq.heapify(Aleft)
Aright = sorted(copy.deepcopy(A[N:]))
Rlim = Aright[N-1]
sumRight = sum(Aright[:N])
score = sumLeft - sumRight

for i in range(N):
    a = A[N+i]
    heapq.heappush(Aleft, a)
    sumLeft += a - heapq.heappop(Aleft)
    Aright.remove(a)
    if a <= Rlim:
        Rlim = Aright[N-1]
        sumRight += Rlim - a
    score = max(score, sumLeft - sumRight)
print(score)

Submission status: Time Limit Exceeded

Solution code:
import heapq, copy
N = int(input())
A = [int(i) for i in input().split()]
Aleft = copy.deepcopy(A[:N])
heapq.heapify(Aleft)
Aright = copy.deepcopy(A[N:])
ArightS = sorted(copy.deepcopy(A[N:]))
score = sum(A[:N]) - sum(ArightS[:N])

for i in range(1, N+1):
    a = Aright.pop(0)
    ArightS.remove(a)
    heapq.heappush(Aleft, a)
    heapq.heappop(Aleft)
    score = max(score, sum(Aleft) - sum(ArightS[:N]))

print(score)

Submission status: Time Limit Exceeded

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

ans = -10**15
for i in range(n+1):
    b1 = a[:n+i]
    b2 = a[n+i:]

    b1.sort(reverse=True)
    s1 = sum(b1[:n])
    b2.sort()
    s2 = sum(b2[:n])
    ans = max(ans, s1-s2)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import copy
N=input()
a=[]
a=map(int, raw_input().split())
#print N
#print a

n_l=[ i for i in range(len(a))]
#print n_l
c = list(itertools.combinations(n_l,N))
#c=[(3,1)]
#print c

score=0.1
for i in c:
	a_t=copy.deepcopy(a)
	#print "#Loop start"
	#print i
	for j in range(N):
		a_t.pop(i[j]-j)
	#print a_t
	a1=zip(*[iter(a_t)]*N)
	#print a1
	if score==0.1 or score<sum(a1[0])-sum(a1[1]):
		score=sum(a1[0])-sum(a1[1])
		#print "score::"+str(score)

print score

Submission status: Time Limit Exceeded

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

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


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

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

    temp = A[N:]
    temp.sort()
    blue_total = sum(temp[:N])
    best_ans = red_total - blue_total


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

        temp = A[k+1:]
        temp.sort()
        blue_total = sum(temp[:N])

        ans = red_total - blue_total
        best_ans = max(best_ans, ans)

    return best_ans


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


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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

heapq.heapify(former)

former_sum = [sum(former)]


for k in range(N):
  heapq.heappushpop(former, a[N+k])
  former_sum.append(sum(former))

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

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

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

print(max(res))

Submission status: Time Limit Exceeded

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


maxv = -float("inf")
for i in range(N, 2*N+1):
    tmp = sum(sorted(a[:i], reverse=True)[:N]) - sum(sorted(a[i:])[:N])
    if tmp > maxv:
        maxv = tmp
print(maxv)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
l=list(map(int,input().split()))
print(max(sum(sorted(l[:(_+N)])[-N:])-sum(sorted(l[(_+N):])[:N])for _ in range(N+1)) )

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
l=list(map(int,input().split()))
mi=-1e14
for _ in range(N+1):
    a=sum(sorted(l[:(_+N)])[-N:])-sum(sorted(l[(_+N):])[:N])
    if(a>mi):mi=a
print(mi)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
l=list(map(int,input().split()))
mi=-1e14
for _ in range(N+1):
    l1=sorted(l[:(_+N)])
    l2=sorted(l[(_+N):])
    df=sum(l1[-N:])-sum(l2[:N])
    if df>mi:
        mi=df
print(mi)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
import copy
lst=[None for i in range(N+1)]
left_lst = copy.deepcopy(lst)
right_lst = copy.deepcopy(lst)
left_array=array[:N] 
right_array=array[-N:]
l_sum=sum(left_array)
r_sum=sum(right_array)
left_lst[0]= l_sum
right_lst[0]=r_sum
for k in range(N,2*N):
    new_a,new_b=array[k],array[-k-1]
    left_array.append(new_a)
    old_a=min(left_array)
    left_array.remove(old_a)
    l_sum+=(new_a-old_a)
    left_lst[k-N+1]=l_sum
    right_array.append(new_b)
    old_b=max(right_array)
    right_array.remove(old_b)
    r_sum+=(new_b-old_b)
    right_lst[k-N+1]=r_sum
lst = [a-b for a,b in zip(left_lst,list(reversed(right_lst)))]
print(max(lst))