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:
from heapq import heapify, heappop, heappush
from collections import deque

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

L = a[:n]
sum_l = sum(L)
heapify(L)

M = a[n:2 * n]
sum_m = sum(M)
M = deque(M)

R = a[2 * n:]
heapify(R)

ans = sum_l - sum_m
t = ans

for i in range(n):
    add_to_l = M.popleft()
    heappush(L, add_to_l)
    subtract_to_l = heappop(L)
    
    add_to_m = heappop(R)
    M.append(add_to_m)

    t -= subtract_to_l
    t += 2 * add_to_l
    t -= add_to_m

    ans = max(ans, t)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
from collections import deque

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

L = a[:n]
sum_l = [sum(L)]
heapify(L)

ML = a[n:2 * n]
ML = deque(ML)

R = list(map(lambda x: (-1) * x, a[2 * n:]))
sum_r = [sum(R)] # あとでReverseする
heapify(R)

MR = list(map(lambda x: (-1) * x, a[n:2 * n]))
MR = deque(MR)

for i in range(n):
    add_to_l = ML.popleft()
    heappush(L, add_to_l)
    subtract_to_l = heappop(L)

    t = sum_l[-1] + add_to_l - subtract_to_l
    sum_l.append(t)

for i in range(n):
    add_to_r = MR.pop()
    heappush(R, add_to_r)
    subtract_to_r = heappop(R)

    t = sum_r[-1] + add_to_r - subtract_to_r
    sum_r.append(t)

sum_r = sum_r[::-1]

ans = sum_l[0] + sum_r[0]
for i in range(1, n):
    t = sum_l[i] + sum_r[i]
    ans = max(ans, t)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
from collections import deque

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

L = a[:n]
sum_l = sum(L)
heapify(L)

M = a[n:2 * n]
sum_m = sum(M)
M = deque(M)

R = a[2 * n:]
heapify(R)

ans = sum_l - sum_m
t = ans

for i in range(n):
    subtract_to_l = heappop(L)
    add_to_l = M.popleft()
    heappush(L, add_to_l)
    add_to_m = heappop(R)
    M.append(add_to_m)

    t -= subtract_to_l
    t += 2 * add_to_l
    t -= add_to_m

    ans = max(ans, t)

print(ans)

Submission status: Wrong Answer

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

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

print(score)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

a1 = a[:n]
ax = a[n:2*n]
a2 = list(map(lambda x: -x, a[2*n:]))
#print('a2', a2)

sum_a1 = sum(a1)
fdif1 = [sum_a1]
heapq.heapify(a1)
for i in range(n):
    p = heapq.heappushpop(a1,ax[i])
    fdif1.append(fdif1[-1]+ax[i]-p)
    
sum_a2 = sum(a2)
fdif2 = [sum_a2]
heapq.heapify(a2)
#print('a2', a2)
for i in range(n):
    p = heapq.heappushpop(a2,-ax[-1-i])
    fdif2.append(fdif2[-1]-ax[-1-i]-p)
fdif2.reverse()

fdif = [fdif1[i]+fdif2[i] for i in range(n)]
print(max(fdif))

Submission status: Wrong Answer

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

a1 = a[:n]
ax = a[n:2*n]
a2 = list(map(lambda x: -x, a[2*n:]))
print('a2', a2)

sum_a1 = sum(a1)
fdif1 = [sum_a1]
heapq.heapify(a1)
for i in range(n):
    p = heapq.heappushpop(a1,ax[i])
    fdif1.append(fdif1[-1]+ax[i]-p)
    
sum_a2 = sum(a2)
fdif2 = [sum_a2]
heapq.heapify(a2)
print('a2', a2)
for i in range(n):
    p = heapq.heappushpop(a2,-ax[-1-i])
    fdif2.append(fdif2[-1]-ax[-1-i]-p)
fdif2.reverse()

fdif = [fdif1[i]+fdif2[i] for i in range(n)]
print(max(fdif))

Submission status: Wrong Answer

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

ans = -10**15
for i in range(n):
    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: Wrong Answer

Solution code:
import heapq
n = int(input())
a = list(map(int,input().split()))
aka = a[:n]
heapq.heapify(aka)
akasum = [0] * (n+1)
akasum[0] = sum(aka)
ao = a[2*n:]
heapq._heapify_max(ao)
aosum = [0] * (n+1)
aosum[-1] = sum(ao)
for i in range(n,2*n):
  b = heapq.heappop(aka)
  if b >= a[i]:
    heapq.heappush(aka, b)
  else:
    heapq.heappush(aka, a[i])
  akasum[i-n+1] = sum(aka)
  b = heapq.heappop(ao)
  if b <= a[-i-1]:
    heapq.heappush(ao, b)
  else:
    heapq.heappush(ao, a[-i-1])
  aosum[-i+n-2] = sum(ao)
ans = - float("inf")
for i in range(n+1):
  kota = akasum[i] - aosum[i]
  ans = max(kota,ans)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque
n = int(input())
a = list(map(int,input().split()))
zen = a[:n]
nak = a[n:2*n]
nak = deque(nak)
kou = a[2*n:]
heapq.heapify(zen)
heapq._heapify_max(kou)
for i in range(n):
  minz = heapq.heappop(zen)
  maxk = heapq.heappop(kou)
  c = nak[0]
  d = nak[-1]
  if (c - minz >= maxk - d and c - minz >= 0):
    heapq.heappush(zen, c)
    nak.popleft()
    heapq.heappush(kou, maxk)
  elif maxk - d >= c - minz and maxk - d >= 0:
    heapq.heappush(kou, d)
    nak.pop()
    heapq.heappush(zen, minz)
  else:
    nak.popleft()
print(sum(zen)-sum(kou))

Submission status: Wrong Answer

Solution code:
import heapq
N=int(input())
a=[int(i) for i in input().split()]
#ans[i]-> k=i+N,
red=[0 for i in range(N+1)]
blue=[0 for i in range(N+1)]
r=list(a[:N])
b=list([-i for i in a[2*N:]])
heapq.heapify(r)
heapq.heapify(b)
red[0]=sum(a[:N])
for i in range(N):
    k=i+N
    tmp1=a[k]
    heapq.heappush(r,a[k])
    tmp2=heapq.heappop(r)
    red[i+1]=red[i]-tmp2+tmp1
blue[-1]=sum(a[2*N:])
for i in range(N)[::-1]:
    k=i+N
    tmp1=a[k]
    tmp2=-heapq.heappop(b)
    blue[i]=blue[i+1]-tmp2+tmp1
ans=[red[i]-blue[i] for i in range(N+1)]
print(max(ans))

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(N, A):
    q = []
    lc = [0]*(N+1)
    for i in range(N):
        heapq.heappush(q, A[i])
        lc[0] += A[i]
    for i in range(N, 2*N):

        a = heapq.heappushpop(q, A[i])
        lc[i-N+1] = lc[i-N] + A[i] - a

    q = []
    rc = [0] * (N+1)
    for i in range(3*N-1, 2*N-1, -1):
        heapq.heappush(q, -A[i])
        rc[N] += A[i]
    for i in range(2*N-1, N-1, -1):
        a = -heapq.heappushpop(q, A[i])
        rc[i-N] = rc[i-N+1] + A[i] - a

    return max(map(lambda x: x[0]-x[1], zip(lc, rc)))


def main():
    N = read_int()
    A = read_int_n()

    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(N, A):
    N3 = N//3

    def f(i):
        l = A[:i]
        r = A[i:]
        rl = heapq.nsmallest(len(l)-N, l)
        rr = heapq.nlargest(len(r)-N, r)

        return (sum(l)-sum(rl)) - (sum(r) - sum(rr))

    l = N
    r = 3*N-N
    while r - l > 1:
        m = (r+l)//2
        if f(m) - f(m-1) > 0:
            l = m
        else:
            r = m

    return f((r+l)//2)


def main():
    N = read_int()
    A = read_int_n()

    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

a=(3*n)//2+1
b=sum(sorted(l[:a])[::-1][:-(a-n)])
c=sum(sorted(l[a:])[::-1][2*n-a:])
a-=1
d=sum(sorted(l[:a])[::-1][:-(a-n)])
e=sum(sorted(l[a:])[::-1][2*n-a:])
print(max(b-c,d-e))

Submission status: Wrong Answer

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

a=(n*n)//2+1
b=sum(sorted(l[:a])[::-1][:-(a-n)])
c=sum(sorted(l[a:])[::-1][2*n-a:])
a-=1
d=sum(sorted(l[:a])[::-1][:-(a-n)])
e=sum(sorted(l[a:])[::-1][2*n-a:])
print(max(b-c,d-e))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
mae = a[0:n]
naka = a[n:2*n]
ushiro = a[2*n:3*n]
mae.sort()
mtotal = sum(mae)

ushiro.sort()
utotal = sum(ushiro)

nakaused = [0 for i in range(n)]
i = 0
k = 0

while i < n:
    if mae[i] < naka[k]:
        mtotal += (naka[k]-mae[i])
        nakaused[k] = 1
        k += 1
    i += 1

k = n-1
e = n-1
while e >= 0:
    if ushiro[e] > naka[k] and nakaused[k] == 0:
        utotal += -(ushiro[e]-naka[k])
        nakaused[k] = 1
        k += -1
    e += -1

print(mtotal-utotal)

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappush, heappop

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

q=A[:N]
heapify(q)

q_sum=sum(q)

B=[ 0 for i in range(3*N)]
for i in range(N-1,2*N):
	x=A[i]
	if x>q[0]:
		r=i
		tmp=heappop(q)
		q_sum-=tmp
		q_sum+=x
		heappush(q,x)
	B[i]=q_sum

C=[ 0 for i in range(3*N)]

q=map(lambda x: x*-1, A[2*N:] )
heapify(q)

q_sum=sum(q)*-1
C[2*N-1]=q_sum

for i in range(2*N-1,N-1,-1):
	x=A[i]
	if x*-1>q[0]:
		tmp=heappop(q)*-1
		q_sum-=tmp
		q_sum+=x
		heappush(q,x*-1)
	C[i-1]=q_sum


ans=float("-inf")
for i in range(N-1,2*N):
	ans=max(ans, B[i]-C[i])
print ans

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappush, heappop

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

q=A[:N]
heapify(q)

r=0

for i in range(N,2*N):
	x=A[i]
	if x>q[0]:
		r=i
		heappop(q)
		heappush(q,x)


q2=map(lambda x: x*-1, A[2*N:] )
heapify(q2)

for i in range(2*N-1,r,-1):
	x=A[i]
	if x*-1>q2[0] :
		heappop(q2)
		heappush(q2,x*-1)

t1=sum(q)-sum(q2)*-1


q2=map(lambda x: x*-1, A[2*N:] )
heapify(q2)

r=2*N

for i in range(2*N-1,N-1,-1):
	x=A[i]
	if x*-1>q2[0] :
		r=i
		heappop(q2)
		heappush(q2,x*-1)

q=A[:N]
heapify(q)

for i in range(N,r):
	x=A[i]
	if x>q[0]:
		r=i
		heappop(q)
		heappush(q,x)

t2=sum(q)-sum(q2)*-1

print max( t1,t2)

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappush, heappop

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

q=A[:N]
heapify(q)

r=0

for i in range(N,2*N):
	x=A[i]
	if x>q[0]:
		r=i
		heappop(q)
		heappush(q,x)


q2=map(lambda x: x*-1, A[2*N:] )
heapify(q2)

for i in range(2*N-1,r,-1):
	x=A[i]
	if x*-1>q2[0] :
		heappop(q2)
		heappush(q2,x*-1)


print sum(q)-sum(q2)*-1

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappush, heappop

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

q=A[:N]
heapify(q)

V=[ 0 for i in range(N*3) ]

for i in range(N,2*N):
	x=A[i]
	if x>q[0]:
		V[i]=1
		heappop(q)
		heappush(q,x)


q2=map(lambda x: x*-1, A[2*N:] )
heapify(q2)

for i in range(2*N-1,N-1,-1):
	x=A[i]
	if x*-1>q2[0] and V[i]!=1:
		heappop(q2)
		heappush(q2,x*-1)


print sum(q)-sum(q2)*-1

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
n=int(input())
a=list(map(int,input().split()))
l=[]
for v in a[:n]:
  heappush(l,v)
suml=[sum(a[:n])]
for i in range(n):
  suml.append(suml[i]+a[n+i])
  heappush(l,a[n+i])
  suml[i+1]-=heappop(l)
r=[]
for v in a[2*n:]:
  heappush(r,(10**10-v,v))
sumr=[sum(a[2*n:])]
for i in range(n):
  sumr.append(sumr[i]+a[2*n-i-1])
  heappush(r,(10**10-a[2*n-i-1],a[2*n-i-1]))
  _,t=heappop(r)
  sumr[i+1]-=t
ans=-10**12
for i in range(n+1):
  ans=max(ans,suml[i]-sumr[n-i])
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
n=int(input())
a=list(map(int,input().split()))
l=[]
for v in a[:n]:
  heappush(l,v)
suml=[sum(a[:n])]
for i in range(n):
  suml.append(suml[i]+a[n+i])
  heappush(l,a[n+i])
  suml[i+1]-=heappop(l)
r=[]
for v in a[2*n:]:
  heappush(r,(10**10-v,v))
sumr=[sum(a[2*n:])]
for i in range(n):
  sumr.append(sumr[i]+a[2*n-i-1])
  heappush(r,(10**10-a[2*n-i-1],a[2*n-i-1]))
  _,t=heappop(r)
  sumr[i+1]-=t
ans=-10**10
for i in range(n+1):
  ans=max(ans,suml[i]-sumr[n-i])
print(ans)

Submission status: Wrong Answer

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

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)
    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)
    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(AL)
print(AR)
print(max(C))

Submission status: Wrong Answer

Solution code:
import heapq

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

left, right = [], []
for i in range(N):
    left.append(sum(heapq.nlargest(N, A[:N+i])))
    right.append(sum(heapq.nsmallest(N, A[N+i:])))

ans = max([l-r for l, r in zip(left, right)])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import insort_left

N = int(input())
A = list(map(int, input().split()))
left = sorted([a for a in A[:N]])
center = deque([a for a in A[N:2*N]])
right = sorted([a for a in A[2*N:]])
# print(left, center, right)
for i in range(N):
    if center[0] - left[0] > right[0] - center[-1]:
        del left[0]
        insort_left(left, center.popleft())
    else:
        del right[-1]
        insort_left(right, center.pop())
    # print(left, center, right)

print(sum(left) - sum(right))

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import insort_left

N = int(input())
A = list(map(int, input().split()))
left = sorted([a for a in A[:N]], reverse=True)
center = deque([a for a in A[N:2*N]])
right = sorted([a for a in A[2*N:]])

for i in range(N):
    if center[0] - left[-1] > right[0] - center[-1]:
        del left[-1]
        insort_left(left, center.popleft())
    else:
        del right[-1]
        insort_left(right, center.pop())

print(sum(left) - sum(right))

Submission status: Wrong Answer

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

a=A[:N]
b=A[-N:]
c=A[N:-N]

a.sort()
b.sort()

def solve(x):
  ans=0
  cnt=0
  while cnt<x:
    if a[cnt] <= c[cnt]:
      ans+=(c[cnt]-a[cnt])
      cnt+=1
    else:
      cnt+=1
  cnt=N-1
  while cnt>=x:
    if c[cnt] <= b[cnt]:
      ans+=(b[cnt]-c[cnt])
      cnt-=1
    else:
      cnt-=1
  return(ans)

res=sum(a)-sum(b)
ma_ans=0
for i in range(N+1):
  ma_ans=max(ma_ans,solve(i))
print(res+ma_ans)

Submission status: Wrong Answer

Solution code:
#can move
#choice N in 3N
N = int(input())
a = [int(i)  for i in input().split()]
S = -10**15
for k in range(N, 2*N):
    x = [a[i] for i in range(k)]
    y = [a[i] for i in range(k,3*N)]
    x.sort(reverse=True);y.sort()
    T=0
    for i in range(N):
       T += x[i] - y[i]
    if S<T:
        S=T
print(S)

Submission status: Wrong Answer

Solution code:
def d_3N_Numbers(N, A):
    if N % 2 == 0:
        # 数列Aを半分に割ったときの「左半分」と「右半分」に分ける
        left = A[:3 * N // 2]
        right = A[3 * N // 2:]
        # スコアを最大にするため、このようにソートしておく
        left = sorted(left, reverse=True)
        right = sorted(right)
    else:
        from bisect import insort
        left = A[:3 * N // 2]
        right = A[3 * N // 2 + 1:]
        mid = A[3 * N // 2]
        left = sorted(left)
        right = sorted(right)
        # 中央の要素を左半分と右半分のどちらに入れるか決める
        if min(left) <= mid:
            insort(left, mid)
        elif min(left) > mid:
            insort(right, mid)
        left = left[::-1]

    # 左半分から大きいものをN個、右半分からは小さいものをN個取る
    first_half = left[:N]
    second_half = right[:N]
    ans = sum(first_half) - sum(second_half)  # スコアの計算
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(d_3N_Numbers(N, A))

Submission status: Wrong Answer

Solution code:
from heapq import *
import itertools

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

# use heappushpop

second = xs[N:]
sindex = [i for i in range(N, 3*N)]
sindex.sort(key=lambda i: xs[i])

first = xs[:N]
first_sum = sum(first)
heapify(first)

best = None

for i in range(N, 2*N):
    x = heappushpop(first, xs[i])
    first_sum += xs[i]
    first_sum -= x

    second_sum = sum(itertools.islice(map(lambda k:xs[k], filter(lambda j: j > i, sindex)), N))

    score = first_sum - second_sum
    if best is None:
        best = score
    elif best < score:
        best = score
    else:
        pass

print(best)

Submission status: Wrong Answer

Solution code:
N = int(input())

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


def nlogn_first(ys):
    ys.sort(reverse=True)
    return sum(ys[i] for i in range(N))

def nlogn_second(ys):
    ys.sort()
    return sum(ys[i] for i in range(N))



print(max(nlogn_first(xs[:i]) - nlogn_second(xs[i:]) for i in range(N, 2*N)))

Submission status: Wrong Answer

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

N=input()
a=[]
a=map(int, raw_input().split())
a1=a[0:N]

heapify(a1)

l1=[]
sum_a1=sum(a1)
l1.append(sum_a1)

# Max
for i in range(N,2*N):
	if a[i]>a1[0]:
		sum_a1=sum_a1+a[i]-a1[0]
		heappop(a1)
		heappush(a1, a[i])

	l1.append(sum_a1)

#print l1


l2=[]
a2=[(-x, x) for x in a[2*N:3*N]]
heapify(a2)
sum_a2=sum(i[1] for i in a2 )
l2.append(sum_a2)

# Min
for i in reversed(range(N,2*N)):
	if a[i]<a2[0][1]:
		sum_a2=sum_a2+a[i]-a2[0][1]
		heappop(a2)
		heappush(a2, (-a[i],a[i]))
	l2.append(sum_a2)

l2.sort()

ans=0
for i in range(len(l1)):
	if l1[i]-l2[i]>0 or ans==0:
		ans=l1[i]-l2[i]

print ans

Submission status: Wrong Answer

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


a1=a[0:2*N]
c_a1=list(itertools.combinations(a1,N))
#print c_a1
c_a1_max=max(c_a1, key = (lambda x:sum(x)))

#print c_a1_max

j_tmp=0
for i in c_a1_max:
	for j,val in enumerate(a):
		if i==val:
			a[j]=10**9+1
			break
else:
	j_tmp=j


#print a
a2=a[j_tmp::]
c_a2=list(itertools.combinations(a2,N))
#print c_a2
c_a2_min=min(c_a2, key = (lambda x:sum(x)))
#print c_a2_min


print ( sum(c_a1_max) ) - ( sum(c_a2_min) )

Submission status: Wrong Answer

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

    best_ans = float('-inf')
    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: Wrong Answer

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


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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = map(int, input().split())
a = [(i, j) for i, j in enumerate(a)]
f, l = a[:3*n//2], a[3*n//2:]

f = sorted(f, key=lambda x: x[1])
l = sorted(l, key=lambda x: x[1])

if n > 1:
    f, l = f[n//2:], l[:0-(n//2)]

if n % 2:
    if f[0][1] < 9-l[-1][1]:
        f.pop(0)
    else:
        l.pop()

a = f + l
a = [i for _, i in sorted(a, key=lambda x: x[0])]

print(sum(a[:n]) - sum(a[n:]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
l=list(map(int,input().split()))
mi=0
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: Wrong Answer

Solution code:
import heapq

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



red = a[:n]
sr = sum(red)
sum_red = {n: sr}
heapq.heapify(red)
# print(red)

blue = [-1 * i for i in a[2*n:]]
sb = sum(blue)
sum_blue = {2 * n: sb}
heapq.heapify(blue)
# print(blue)

for k in range(n, 2 * n):
    popped_red = heapq.heappushpop(red, a[k])
    sr += a[k] - popped_red
    sum_red[k + 1] = sr
    # print(popped_red, red, sr, sum_red)

for k in range(2 * n - 1, n - 1, -1):
    popped_blue = heapq.heappushpop(blue, -1  * a[k])
    sb += -1 * a[k] - popped_blue
    sum_blue[k] = sb
    # print(popped_blue, blue, sb, sum_blue)

ans = -1 * float('inf')
for k in range(n + 1, 2 * n + 1):
    ans = max(ans, sum_red[k] + sum_blue[k])
    

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
count=0
f=0
s=0
flag=False
p=N*3
while count!=2*N:
    if flag:
        i=a.index(max(a[:int(p/2)]))
        f+=a[i]
        a=a[:i]+a[i+1:]
        flag=False
        count+=1
        p-=1
    else:
        i=a.index(min(a[int(p/2):]))
        s+=a[i]
        a=a[:i]+a[i+1:]
        flag=True
        count+=1
        p-=1
print(f-s)

Submission status: Wrong Answer

Solution code:
import heapq
N=int(input())
a=list(map(int,input().split()))
earl=[]
late=[]
for i in range(N):
  heapq.heappush(earl,a[i])
  heapq.heappush(late,-a[2*N+i])
E=0
L=0
for i in range(N):
  E+=a[i]
  L-=a[2*N+i]
e=[E]*(N+1)
l=[L]*(N+1)
for i in range(N):
  e[i+1]=e[i]+a[N+i]-heapq.heappushpop(earl,a[N+i])
  l[N-1-i]=l[N-i]-a[2*N-1-i]-heapq.heappushpop(late,-a[2*N-1-i])

ans=e[N]+l[N]
for i in range(N):
  ans=max(ans,a[i]+l[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
lst=[]
left_array=array[:N] 
right_array=array[-N:]
l_sum=sum(left_array)
r_sum=sum(right_array)
left_lst=[l_sum]
right_lst=[r_sum]
for k in range(N,2*N):
    new_a=array[k]
    new_b=array[-k-1]
    left_array.append(new_a)
    old_a=min(left_array)
    left_array.remove(old_a)
    l_sum+=(new_a-old_a)
    right_array.append(new_b)
    old_b=max(right_array)
    right_array.remove(old_b)
    r_sum+=(new_b-old_b)
    lst.append(l_sum-r_sum)
print(max(lst))

Submission status: Wrong Answer

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
lst=[]
left_array=array[:N]
right_array=array[-N:]
for i in range(N+1):
    for j in range(i):
        new_a=array[N+j+1]
        old_a=min(left_array)
        new_b=array[-N-j-1]
        old_b=min(right_array)
        left_array.append(new_a)
        left_array.remove(old_a)
        right_array.append(new_b)
        right_array.remove(old_b)
lst.append(sum(left_array)-sum(right_array))
print(max(lst))

Submission status: Wrong Answer

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
lst=[]
for i in range(N):
    a =len(array)//2 -1
    l=array[:a+1]
    r= array[a+1:]
    if max(r)-array[a] > array[a]- min(l) > 0 or max(r)-array[a] > 0 > array[a]- min(l):
        r.pop(r.index(max(r)))
        array= l+r
    elif  array[a]- min(l) >max(r)-array[a] > 0 or  array[a]- min(l) > 0 > max(r)-array[a]:
        l.pop(l.index(min(l)))
        array= l+r
    else:
        array.remove(array[a])
print(sum(array[:N])-sum(array[N:]))

Submission status: Wrong Answer

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
lst=[]
for i in range(N):
    a =len(array)//2 -1
    l=array[:a+1]
    r= array[a+1:]
    if max(r)-array[a] > array[a]- min(l) > 0 or max(r)-array[a] > 0 > array[a]- min(l):
        r.remove(max(r))
        array= l+r
    elif  array[a]- min(l) >max(r)-array[a] > 0 or  array[a]- min(l) > 0 > max(r)-array[a]:
        l.remove(min(l))
        array= l+r
    else:
        array.remove(array[a])
print(sum(array[:N])-sum(array[N:]))

Submission status: Wrong Answer

Solution code:
N = int(input())
array=[int(n) for n in input().split()]
lst=[]
for i in range(N+1):
    left_array=array[:N+i]
    l = sorted(left_array)[-N:]
    right_array=array[N+i:]
    r = sorted(right_array)[:N]
    ans = sum(l)-sum(r)
    if lst ==[] or ans>ans:
        lst=ans
print(lst)

Submission status: Wrong Answer

Solution code:
N = int(input())
array=[int(n) for n in input().split()]

lst=0
for i in range(N+1):
    left_array=array[:N+i]
    l = sorted(left_array)[-N:]
    right_array=array[N+i:]
    r = sorted(right_array)[:N]
    ans = sum(l)-sum(r)
    if ans > lst:
        lst= ans
print(lst)

Submission status: Wrong Answer

Solution code:
N = input()
array=[int(n) for n in input().split()]

lst=0
for i in range(int(N)):
    left_array=array[:int(len(array)/3+i+1)]
    l = sorted(left_array)[i:]  
    right_array=array[int(-len(array)/3+i+1):]
    r = sorted(right_array)[:-int(N)+i]
    ans = abs(sum(l)-sum(r))
    if ans > lst:
        lst= ans
print(lst)

Submission status: Wrong Answer

Solution code:
N = input()
array=[int(n) for n in input().split()]

lst=0
for i in range(int(N)):
    left_array=array[:int(len(array)/3+i+1)]
    l = sorted(left_array)[i+1:]  
    right_array=array[int(-len(array)/3+i+1):]
    r = sorted(right_array)[:-int(N)+i]
    ans = abs(sum(l)-sum(r))
    if ans > lst:
        lst= ans
print(lst)