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 __future__ import division
import math
import sys
import bisect

def get_min(w, h):
    m = 1e11
    for x in [w // 3, w // 3 + 1]:
        if x == 0: continue
        a = [x*h, (w-x)*(h//2), (w-x)*(h - h//2)]
        print a
        m = min(m, max(a) - min(a))
    return m

# digits = raw_input()
# a, b = [int(x) for x in digits.split(' ')]
N = input()
digits = [int(x) for x in raw_input().split(' ')]
# score = sum([x if x <= 0 else -1*x for x in digits])
l1_sorted = sorted(digits[:N])
l2_sorted = sorted(digits[N:])
score = sum(l1_sorted) - sum(l2_sorted[:N])
for p in range(N, 2*N-1):
    bisect.insort_left(l1_sorted, digits[p])
    r = bisect.bisect_right(l2_sorted, digits[p])
    l2_sorted.pop(r - 1)
    # print l1_sorted, l2_sorted
    score = max(score, sum(l1_sorted[-1*N:]) - sum(l2_sorted[:N]))
print score

Submission status: Wrong Answer

Solution code:
from __future__ import division
import math
import sys


def get_min(w, h):
    m = 1e11
    for x in [w // 3, w // 3 + 1]:
        if x == 0: continue
        a = [x*h, (w-x)*(h//2), (w-x)*(h - h//2)]
        print a
        m = min(m, max(a) - min(a))
    return m

# digits = raw_input()
# a, b = [int(x) for x in digits.split(' ')]
N = input()
digits = [int(x) for x in raw_input().split(' ')]
score = sum([x if x <= 0 else -1*x for x in digits])
for p in range(N-1, 2*N-1):
    l1 = digits[:p+1]
    l2 = digits[p+1:]
    l1_sorted = sorted(l1)
    l2_sorted = sorted(l2)
    # print l1_sorted, l2_sorted
    score = max(score, sum(l1_sorted[-1*N:]) - sum(l2_sorted[:N]))
print score

Submission status: Wrong Answer

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

left = sorted(a[:N])
middle = a[N:2*N]
right = sorted(a[N:])

m = sum(left) - sum(right[:N])
for i in middle:
    if (i > left[0]):
        left.remove(left[0])
        for j, l in enumerate(left):
            if (i < left[j]):
                left.insert(j, i)
                break
    right.remove(i)
    score = sum(left) - sum(right[:N])
    if m < score:
        m = score
print m

Submission status: Wrong Answer

Solution code:
import heapq as hp

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


left = a[:N]

hp.heapify(left)
x = [sum(left)]
for k in range(N, 2 * N):
    v = hp.heappushpop(left, a[k])
    x.append(x[-1] + a[k] - v)


a = a[::-1]

right = [-r for r in a[:N]]

hp.heapify(right)
y = [-sum(right)]

for k in range(N, 2 * N):
    v = hp.heappushpop(right, -a[k])
    y.append(y[-1] + a[k] - v)


print(max(v-w for v,w in zip(x, y[::-1])))

Submission status: Wrong Answer

Solution code:
import sys

N = int(raw_input())
a = map(int, raw_input().split())

m = -sys.maxint - 1
for i in range(N+1):
    left = sorted(a[:N+i])
    right = sorted(a[N+i:])
    print left
    print right
    score = sum(left[i:]) - sum(right[:N])
    if m < score:
        m = score
print m

Submission status: Wrong Answer

Solution code:
N=input()
l=map(int,raw_input().split())
left=list(reversed(sorted(l[:N])))
center=l[N:2*N]
right=sorted(l[2*N:])
la,ra,cl,cr=[0]*(N+1) ,[0]*(N+1) ,[0]*(N+1) ,[0]*(N+1)
for i in xrange(N): la[i+1]=la[i]+left[i]
for i in xrange(N): ra[i+1]=ra[i]+right[i]
for i in xrange(N): cl[i+1]=cl[i]+center[i]
for i in xrange(N): cr[i+1]=cr[i]+center[-i-1]

ans = -(10**20)
for a in xrange(N+1):
    b = N-a
    ans = max(ans,la[b]+cl[a]-cr[b]-ra[a])
print ans

Submission status: Wrong Answer

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

A = a[0:N]
B = a[2 * N:3 * N]

i = N
j = 2 * N - 1

minA = min(A)
maxB = max(B)

while i <= j:
    #print("i:{0}, j:{1}".format(i ,j))
    #print("A:{0}, B:{1}".format(A, B))
    delA = a[i] - min(A)
    delB = max(B) -a[j]

    if delA >= 0 and delA >= delB:
        A.remove(minA)
        A.append(a[i])
        minA = min(A)
        i += 1

    elif delB >= 0:
        B.remove(maxB)
        B.append(a[j])
        maxB = max(B)
        j -= 1

    else:
        i += 1

print(sum(A)-sum(B))

Submission status: Wrong Answer

Solution code:
import heapq
 
n = int(input())
a = list(map(int,input().split()))
 
if n > 10000:
    exit()
 
a1 = []
a2 = []
sum1 = [0] * (n + 1)
sum2 = [0] * (n + 1)
for i in range(n):
    heapq.heappush(a1, a[i])
 
i = 0
for aa in a[n: 2 * n + 1]:
    sum1[i] = sum(a1)
    heapq.heappush(a1, aa)
    heapq.heappop(a1)
    i += 1
 
a = a[::-1]
for i in range(n):
    heapq.heappush(a2, -a[i])
i = 0
for aa in a[n: 2 * n + 1]:
    sum2[i] = sum(a2)
    heapq.heappush(a2, -aa)
    heapq.heappop(a2)
    i += 1
 
ans = - 10 ** 10
for i in range(n + 1):
    ans = max(ans, sum1[i] + sum2[-i - 1])
 
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
 
n = int(input())
a = list(map(int,input().split()))
 
if n > 1000:
    exit()
 
a1 = []
a2 = []
sum1 = [0] * (n + 1)
sum2 = [0] * (n + 1)
for i in range(n):
    heapq.heappush(a1, a[i])
 
i = 0
for aa in a[n: 2 * n + 1]:
    sum1[i] = sum(a1)
    heapq.heappush(a1, aa)
    heapq.heappop(a1)
    i += 1
 
a = a[::-1]
for i in range(n):
    heapq.heappush(a2, -a[i])
i = 0
for aa in a[n: 2 * n + 1]:
    sum2[i] = sum(a2)
    heapq.heappush(a2, -aa)
    heapq.heappop(a2)
    i += 1
 
ans = - 10 ** 10
for i in range(n + 1):
    ans = max(ans, sum1[i] + sum2[-i - 1])
 
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

if n > 1000:
    exit()

a1 = []
a2 = []
sum1 = [0] * (n + 1)
sum2 = [0] * (n + 1)
v = 0
for i in range(n):
    heapq.heappush(a1, a[i])
    v += a[i]

i = 0
sum1[0] = v
for aa in a[n: 2 * n]:
    heapq.heappush(a1, aa)
    x = heapq.heappop(a1)
    sum1[i + 1] = sum(a1)
    i += 1


a = a[::-1]
v = 0
for i in range(n):
    heapq.heappush(a2, -a[i])
    v += a[i]

i = 0
sum2[0] = v
for aa in a[n: 2 * n]:
    heapq.heappush(a2, -aa)
    x = -heapq.heappop(a2)
    i += 1
    sum2[i] = sum(a2)

ans = - 10 ** 10
for i in range(n + 1):
    ans = max(ans, sum1[i] + sum2[-i - 1])

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
 
n = int(input())
a = list(map(int,input().split()))
 
a1 = []
a2 = []
sum1 = [0] * (n + 1)
sum2 = [0] * (n + 1)
for i in range(n):
    heapq.heappush(a1, a[i])
 
i = 0
for aa in a[n: 2 * n + 1]:
    sum1[i] = sum(a1)
    heapq.heappush(a1, aa)
    heapq.heappop(a1)
    i += 1
 
a = a[::-1]
for i in range(n):
    heapq.heappush(a2, -a[i])
i = 0
for aa in a[n: 2 * n + 1]:
    sum2[i] = sum(a2)
    heapq.heappush(a2, -aa)
    heapq.heappop(a2)
    i += 1
 
ans = - 10 ** 10
for i in range(n + 1):
    ans = max(ans, sum1[i] + sum2[-i - 1])
 
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

if n > 1000:
    exit()

a1 = []
a2 = []
sum1 = [0] * (n + 1)
sum2 = [0] * (n + 1)
for i in range(n):
    heapq.heappush(a1, a[i])

i = 0
for aa in a[n: 2 * n + 1]:
    sum1[i] = sum(a1)
    heapq.heappush(a1, aa)
    heapq.heappop(a1)
    i += 1

a = a[::-1]
for i in range(n):
    heapq.heappush(a2, -a[i])
i = 0
for aa in a[n: 2 * n + 1]:
    sum2[i] = sum(a2)
    heapq.heappush(a2, -aa)
    heapq.heappop(a2)
    i += 1

ans = - 10 ** 10
for i in range(n + 1):
    ans = max(ans, sum1[i] + sum2[-i - 1])

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
a=map(int,raw_input().split(' '))

def argmax(a):
    m=max(a)
    for i in range(len(a)-1,-1,-1):
        if a[i]==m:
            return i
        
    return None

def argmin(a):
    return a.index(min(a))

s_max=float('-inf')
for i in range(N):
    a_head=a[0:N+i]
    a_tail=a[N+i:]
    for _ in range(i):
        del(a_head[argmin(a_head)])
    for _ in range(N-i):
        del(a_tail[argmax(a_tail)])

    #print a_head,a_tail
    #a_res=a_head+a_tail
    #print a_res[0:len(a_res)/2],a_res[len(a_res)/2:]
    #s=sum(a_res[0:len(a_res)/2])-sum(a_res[len(a_res)/2:])
    s=sum(a_head)-sum(a_tail)
    if s_max<s:
        s_max=s

print s_max

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
a=map(int,raw_input().split(' '))

def argmax(a):
    m=max(a)
    for i in range(len(a)-1,-1,-1):
        if a[i]==m:
            return i
        
    return None

def argmin(a):
    return a.index(min(a))

s_max=float('-inf')
for i in range(N):
    a_head=a[0:len(a)/2+i]
    a_tail=a[len(a)/2+i:]
    for _ in range(i):
        del(a_head[argmin(a_head)])
    for _ in range(N-i):
        del(a_tail[argmax(a_tail)])

    #print a_head,a_tail
    a_res=a_head+a_tail
    #print a_res[0:len(a_res)/2],a_res[len(a_res)/2:]
    s=sum(a_res[0:len(a_res)/2])-sum(a_res[len(a_res)/2:])
    if s_max<s:
        s_max=s

print s_max

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
a = list(map(int,input().split()))
a1 = []
a2 = []
sum1 = [0] * (n + 1)
sum2 = [0] * (n + 1)
for i in range(n):
    heapq.heappush(a1, a[i])
i = 0
for aa in a[n: 2 * n + 1]:
    sum1[i] = sum(a1)
    heapq.heappush(a1, aa)
    heapq.heappop(a1)
    i += 1

a = a[::-1]
for i in range(n):
    heapq.heappush(a2, -a[i])
i = 0
for aa in a[n: 2 * n + 1]:
    sum2[i] = sum(a2)
    heapq.heappush(a2, -aa)
    heapq.heappop(a2)
    i += 1

ans = - 10 ** 10
for i in range(n):
    ans = max(ans, sum1[i] + sum2[-i - 1])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
r = []
for k in range(n,2*n): r.append(sum(sorted(a[:k])[-n:])-sum(sorted(a[k:])[:n]))
print(max(r))

Submission status: Wrong Answer

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

ans = -10000000000
for k in range(N, 2*N+1):
    s0 = a[:k]
    s1 = a[k:]
    s0.sort()
    s1.sort()
    m = sum(s0[-N:]) - sum(s1[:N])
    if ans < m:
        ans = m
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

N = int(raw_input())
a = map(int, raw_input().split())

flag = 0
while N > 1:
    l = len(a)
    if flag == 0:
      min = np.argmin(a[:(l//2)])
      a.pop(min)
      N -= 1
      flag = 1

    elif flag == 1:
      max = np.argmax(a[(l//2):]) + l//2
      a.pop(max)
      N -= 1
      flag = 0

l = len(a)
min = np.min(a[:(l//2)])
amin = np.argmin(a[:(l//2)])
max = np.max(a[(l//2):])
amax = np.argmax(a[(l//2):]) + l//2
mid = a[(l//2)+1]

if mid - min > - (mid - max):
  a.pop(amin)
else:
  a.pop(amax)

l = len(a)
res = sum(a[:(l//2)]) - sum(a[(l//2):])
print str(res)

Submission status: Wrong Answer

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

s = [a[:N], a[-N:]]
#print(s)
s[0].sort()
s[1].sort()
#print(s)
b = [N, 2*N-1]
z = a[N:-N]
zz1 = [sum(z[:i]) for i in range(N+1)]
zz2 = [sum(z[i:]) for i in range(N+1)]
sz1 = [sum(s[0][i:]) for i in range(N+1)]
sz2 = [sum(s[1][:i]) for i in range(N+1)]
#print(zz1)
#print(zz2)
#print(sz1)
#print(sz2)
ssz1 = [i+j for (i,j) in zip(sz1,zz1)]
ssz2 = [i+j for (i,j) in zip(sz2,zz2)]
#print(ssz1)
#print(ssz2)
dd = [i-j for (i,j) in zip(ssz1, ssz2)]
print(max(dd))
"""
while b[0] <= b[1]:
    d1 = a[b[0]] - s[0][0]
    d2 = s[1][-1] - a[b[1]]
    if d1 >= d2:
        s[0][0] = a[b[0]]
        s[0].sort()
        b[0] += 1
    else:
        s[1][-1] = a[b[1]]
        s[1].sort()
        b[1] -= 1
    #print(s)
#print(s)
#print(s[0])
#print(s[1])
print(sum(s[0]) - sum(s[1]))
"""

Submission status: Wrong Answer

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

a1 = a[0:N]
a2 = a[N:2*N]
a3 = a[2*N:3*N]

a1.sort(reverse=True)
a3.sort()

for i in range(N):
	ans.append(sum(a1[0:N-i]) + sum(a2[0:i]) - sum(a3[0:i]) - sum(a2[i:N]))

print(max(ans))

Submission status: Wrong Answer

Solution code:

def cal(lst, n):
    return sum(lst[:n])-sum(lst[-n:])

def skip(lst, idx):
    return lst[:idx]+lst[idx+1:]

n = int(input())
a = list(map(int, input().split(' ')))
for _ in range(n):
    b_idx = a.index(min(a[:n]))
    b_n = cal(skip(a, b_idx), n)

    c_idx = a.index(max(a[-n:]))
    c_n = cal(skip(a, c_idx), n)

    if c_n > b_n:
        a.pop(c_idx)
    else:
        a.pop(b_idx)
print(cal(a, n))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

N = int(raw_input())
a = map(int, raw_input().split())

flag = 0
while N > 1:
    l = len(a)
    if flag == 0:
      min = np.argmin(a[:(l//2)])
      a.pop(min)
      N -= 1
      flag = 1

    elif flag == 1:
      max = np.argmax(a[(l//2):]) + l//2
      a.pop(max)
      N -= 1
      flag = 0

l = len(a)
min = np.min(a[:(l//2)])
amin = np.argmin(a[:(l//2)])
max = np.max(a[(l//2):])
amax = np.argmax(a[(l//2):]) + l//2
mid = a[(l//2)+1]

if mid - min > - (mid - max):
  a.pop(amin)
else:
  a.pop(amax)

l = len(a)
print a
res = sum(a[:(l//2)]) - sum(a[(l//2):])
print str(res)

Submission status: Wrong Answer

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

A1 = a[0:N]
A2 = a[N:2 * N]
A3 = a[2 * N:3 * N]

a1 = sorted(A1 + A2)
a2 = sorted(A2 + A3)

al = sorted(A1 + A2 + A3)

A = al
a1max1 = 0
for i in range(N):
	a1max1 += a1[-i]
	A.remove(a1[-i])

A = sorted(A)

a2min1 = 0
for i in range(N):
	a2min1 += A[i]

score1 = a1max1 - a2min1


B = a
a2min2 = 0
for i in range(N):
	a2min2 += a2[i]
	B.remove(a2[i])

B = sorted(B)

a1max2 = 0
for i in range(N):
	a1max2 += B[-i]

score2 = a1max2 - a2min2

print(min(score1, score2))

Submission status: Wrong Answer

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

s = [a[:N], a[-N:]]
#print(s)
s[0].sort()
s[1].sort()
#print(s)
b = [N, 2*N-1]
#z = a[N:-N]
#zz1 = [sum(z[:i]) for i in range(N+1)]
#zz2 = [sum(z[i:]) for i in range(N+1)]
#print(zz1)
#print(zz2)
while b[0] <= b[1]:
    d1 = a[b[0]] - s[0][0]
    d2 = s[1][-1] - a[b[1]]
    if d1 >= d2:
        s[0][0] = a[b[0]]
        s[0].sort()
        b[0] += 1
    else:
        s[1][-1] = a[b[1]]
        s[1].sort()
        b[1] -= 1
    #print(s)
#print(s)
#print(s[0])
#print(s[1])
print(sum(s[0]) - sum(s[1]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
a = [int(n) for n in input().split()]
score = 10**9 * 10**5 * -3
for n in range(N):
    before = a[:N + n]
    after = a[N+n:]

    b_max = sum(sorted(before, reverse=True)[:N])
    a_min = sum(sorted(after)[:N])
    
    score = max(score, b_max - a_min)
print(score)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

N = int(raw_input())
a = map(int, raw_input().split())

flag = 0
while N > 0:
    l = len(a)
    if flag == 0:
      min = np.argmin(a[:(l//2)])
      a.pop(min)
      N -= 1
      flag = 1

    elif flag == 1:
      max = np.argmax(a[(l//2):]) + l//2
      a.pop(max)
      N -= 1
      flag = 0

l = len(a)
res = sum(a[:(l//2)]) - sum(a[(l//2):])
print str(res)

Submission status: Wrong Answer

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

a = l[:N]
b = l[N:N*2]
c = l[N*2:]

for j in range(N):
    front = b[0] - min(a)
    behind = b[-1] - max(c)
    if abs(front) >= abs(behind):
        a.remove(min(a))
        a.append(b[0])
        b.remove(b[0])
    else:
        c.remove(max(c))
        c.append(b[-1])
        b.remove(b[-1])

print( sum(a) - sum(c) )

Submission status: Wrong Answer

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

s = [a[:N], a[-N:]]
#print(s)
s[0].sort()
#print(s)
b = [N, 2*N-1]
while b[0] <= b[1]:
    d1 = a[b[0]] - s[0][0]
    d2 = s[1][-1] - a[b[1]]
    if d1 >= d2:
        s[0][0] = a[b[0]]
        s[0].sort()
        b[0] += 1
    else:
        s[1][-1] = a[b[1]]
        s[1].sort()
        b[1] -= 1
    #print(s)
#print(s)
#print(s[0])
#print(s[1])
print(sum(s[0]) - sum(s[1]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
from collections import deque

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

HEAD = deque(reversed(sorted(A[:N])))
TAIL = deque(sorted(A[2*N:]))
MID_ASC = deque(reversed(A[N:2*N]))
MID_DESC = deque(A[N:2*N])


# n個入れ替えたときの最大値
HEAD_DIFFS = [0]
TAIL_DIFFS = [0]
for n in xrange(1, N+1, 1):
    HEAD_DIFFS.append(HEAD_DIFFS[-1]+MID_ASC[-n] - HEAD[-n])
    TAIL_DIFFS.append(TAIL_DIFFS[-1]+TAIL[-n] - MID_DESC[-n])
POSSIBLE_HEAD_DIFFS = [0]
POSSIBLE_TAIL_DIFFS = [0]
# n個まで入れ替えたときの最大値
for n in xrange(1, N+1, 1):
    POSSIBLE_HEAD_DIFFS.append(max(POSSIBLE_HEAD_DIFFS[-1], HEAD_DIFFS[n]))
    POSSIBLE_TAIL_DIFFS.append(max(POSSIBLE_TAIL_DIFFS[-1], TAIL_DIFFS[n]))

score = sum(HEAD) - sum(TAIL)
max_diff = 0
#print(POSSIBLE_HEAD_DIFFS)
#print(POSSIBLE_TAIL_DIFFS)
for n in range(N+1):
    #print(score, POSSIBLE_HEAD_DIFFS[n], POSSIBLE_TAIL_DIFFS[N-n])
    #print(score +  POSSIBLE_HEAD_DIFFS[n] + POSSIBLE_TAIL_DIFFS[N-n])
    max_diff = max(max_diff, POSSIBLE_HEAD_DIFFS[n] + POSSIBLE_TAIL_DIFFS[N-n])
print(score+max_diff)
exit(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
i = input().split()
a = []
for x in i:
 a.append(int(x))
print(sum(a[:n]) - sum(a[-n:]))

Submission status: Wrong Answer

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

for i in range(N):
    f = a[0:N]
    b = a[-N:]
    m = min(f)
    M = max(b)
    if a[N] - m > M - a[- N - 1]:
        for i in range(N):
            if a[i] == m:
                a.pop(i)
                break
    else:
        for i in range(1, N + 1):
            if a[- i] == M:
                a.pop(-i)
                break
score = 0
for i in range(N):
    score += a[i]
    score -= a[-i - 1]
print score

Submission status: Wrong Answer

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

s = [a[:N], a[-N:]]
#print(s)
s[0].sort()
#print(s)
for i in range(int(N/2)):
    if s[0][0] < a[N+i]:
        s[0][0] = a[N+i]
        s[0].sort()
    if s[1][-1] > a[-N-i-1]:
        s[1][-1] = a[-N-i-1]
        s[1].sort()
    #print(s)
#print(s)
if int(N/2)*2 != N:
    aa = a[N+int(N/2)]
    d1 = aa - s[0][0]
    d2 = s[1][-1] - aa
    if d1 >= d2:
        s[0][0] = aa
        s[0].sort()
    else:
        s[1][-1] = aa
        s[1].sort()
#print(s)
print(sum(s[0]) - sum(s[1]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
from collections import deque

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

HEAD = deque(reversed(sorted(A[:N])))
TAIL = deque(sorted(A[2*N:]))
MID_ASC = deque(reversed(A[N:2*N]))
MID_DESC = deque(A[N:2*N])


score = sum(HEAD) - sum(TAIL)
for _ in range(N):
    #print(score)
    head_diff = MID_ASC[-1] - HEAD[-1]
    tail_diff = TAIL[-1] - MID_DESC[-1]
    #print(head_diff, tail_diff)
    if(head_diff < 0 and tail_diff < 0):
        break
    elif(head_diff > tail_diff):
        score += head_diff
        HEAD.pop()
        MID_ASC.pop()
    else:
        score += tail_diff
        TAIL.pop()
        MID_DESC.pop()
print(score)
exit(0)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math

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

HEAD = list(sorted(A[:N]))
TAIL = list(reversed(sorted(A[2*N:])))
MID_ASC = A[N:2*N]
MID_DESC = list(reversed(A[N:2*N]))


score = sum(HEAD) - sum(TAIL)
for _ in range(N):
    #print(score)
    head_diff = MID_ASC[0] - HEAD[0]
    tail_diff = TAIL[0] - MID_DESC[0]
    #print(head_diff, tail_diff)
    if(head_diff < 0 and tail_diff < 0):
        break
    elif(head_diff > tail_diff):
        score += head_diff
        HEAD.pop(0)
        MID_ASC.pop(0)
    else:
        score += tail_diff
        TAIL.pop(0)
        MID_DESC.pop(0)
print(score)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
import heapq 
N=int(input())
A=list(map(int, input().split()))
A_rev = [-x for x in A[::-1]]#逆順にして各要素を-1倍する
ans=-float("inf")
for k in range(N, 2*N+1):
	left=A[:k]
	right=A_rev[:(3*N-k)]

	heapq.heapify(left)
	heapq.heapify(right)

	for _ in range(k-N):
		heapq.heappop(left)
	for _ in range(2*N-k):
		heapq.heappop(right)

	ans= max(sum(left)+sum(right), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq 
N=int(input())
A=list(map(int, input().split()))
ans=-float("inf")
for k in range(N, 2*N+1):
	left=A[:k]
	right=[-i for i in A[k:]] #各要素を-1倍する

	heapq.heapify(left)
	heapq.heapify(right)

	for _ in range(k-N):
		heapq.heappop(left)
	for _ in range(2*N-k):
		heapq.heappop(right)

	ans= max(sum(left)+sum(right), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
with open(0) as f:
    N, *a = map(int, f.read().split())
F = [x for x in a[:N]] #Fの要素は加えるか取り除くかの2択
C = [x for x in a[N:2*N]] 
B = [-x for x in a[2*N:]] #Bの要素は引くか取り除くかの二択
import heapq as hq
hq.heapify(F)
hq.heapify(B)

#Cを二分し、前半はFと、後半はBとで演算を行う
#演算方法(c in C)
#前半：cがF[0]より大きければF[0]を取り除くN個の一つとし、cをスコアに加える
#後半：-cがB[0]より大きければB[0]を取り除くN個の一つとし、cをスコアから引く
#どちらも場合も条件を満たさない場合はそのｃを取り除くN個の一つとする
#計算量：O(N*N*logN)
#途中計算をメモして計算量軽減
from copy import deepcopy
memoF = [[]] * (N+1) #C[:i]を前半としたときのFとの演算結果
memoF[0] = deepcopy(F)
memoB = [[]] * (N+1) #C[i:]を後半としたときのBとの演算結果
memoB[N] = deepcopy(B)
for i in range(N):
    if C[i] > F[0]:
        hq.heapreplace(F, C[i])
    if -C[N-1-i] > B[0]:
        hq.heapreplace(B, -C[N-1-i])
    memoF[i+1] = deepcopy(F)
    memoB[N-1-i] = deepcopy(B)

Scores = [sum(memoF[i])+sum(memoB[i]) for i in range(N+1)]
ans = max(Scores)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 一部のTLEケースを突破できるようになった。
# 中央のシマを左右で取り合う形になるが、
# 取る要素がひとつ増えるときは、前回の値を利用するようにした。
# added.sort() を min/max_added 値で代替した。

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

a1=a[0:n]
a_m=a[n:2*n]
a2=a[2*n:3*n]

a1.sort()
a2.sort()
base_sum=sum(a1)-sum(a2)

a1_vals=[0]*(n+1)
added=[]
min_added=float("inf")
j=0
for i in range(0,n):
  val=0
  # addedの最小値を持って置き、sort()を使わないようにする。
  if min_added < a1[j] and min_added < a_m[i]:
    val=a_m[i]-min_added
    added.remove(min_added)
    added.append(a_m[i])
    min_added=min(added)
  elif a1[j] < a_m[i]:
    val=a_m[i]-a1[j]
    added.append(a_m[i])
    min_added=min(min_added,a_m[i])
    j+=1
  a1_vals[i+1]=val+a1_vals[i]

a_m.reverse()
a2_vals=[0]*(n+1)
added=[]
max_added=-float("inf")
j=-1
for i in range(0,n):
  val=0
  if max_added > a2[j] and max_added > a_m[i]:
    val=a_m[i]-max_added
    added.remove(max_added)
    added.append(a_m[i])
    max_added=max(added)
  elif a2[j] > a_m[i]:
    val=a_m[i]-a2[j]
    added.append(a_m[i])
    max_added=max(max_added,a_m[i])
    j-=1
  a2_vals[i+1]=val+a2_vals[i]

max_val=-float("inf")
for i in range(0,n+1):
  max_val=max(max_val, (a1_vals[i] - a2_vals[n-i]))

print(base_sum + max_val)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
max_s=-float("inf")

a1=a[0:n]
a_m=a[n:2*n]
a2=a[2*n:3*n]

a1.sort()
a2.sort()
base_sum=sum(a1)-sum(a2)

a1_vals=[0]*(n+1)
added=[]
j=0
for i in range(0,n):
  val=0
  if added != [] and added[-1] < a1[j] and added[-1] < a_m[i]:
    val=a_m[i]-added[-1]
    added.pop(-1)
    added.append(a_m[i])
    added.sort(reverse=True)
  elif a1[j] < a_m[i]:
    val=a_m[i]-a1[j]
    added.append(a_m[i])
    added.sort(reverse=True)
    j+=1
  a1_vals[i+1]=val+a1_vals[i]

a_m.reverse()
a2_vals=[0]*(n+1)
added=[]
j=-1
for i in range(0,n):
  val=0
  if added != [] and added[-1] > a2[j] and added[-1] > a_m[i]:
    val=a_m[i]-added[-1]
    added.pop(-1)
    added.append(a_m[i])
    added.sort(reverse=False)
  elif a2[j] > a_m[i]:
    val=a_m[i]-a2[j]
    added.append(a_m[i])
    added.sort(reverse=False)
    j-=1
  a2_vals[i+1]=val+a2_vals[i]

max_val=-float("inf")
for i in range(0,n+1):
  max_val=max(max_val, (a1_vals[i] - a2_vals[n-i]))

print(base_sum + max_val)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
max_s=-float("inf")

a1=a[0:n]
a_m=a[n:2*n]
a2=a[2*n:3*n]

a1.sort()
a2.sort()
base_sum=sum(a1)-sum(a2)

for i in range(0,n+1):
  a_m1=a_m[:i]
  x=a1+a_m1
  x.sort()
  addx=sum(a_m1)-sum(x[:i])
  
  a_m2=a_m[i:]
  y=a2+a_m2
  y.sort()
  remy=sum(a_m2)-sum(y[n:])
  max_s=max(max_s,(base_sum+addx-remy))
  
print(max_s)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
max_s=-float("inf")
for i in range(n,2*n+1):
  x=a[:i]
  x.sort()
  xs=sum(x[len(x)-n:])
  y=a[i:]
  y.sort()
  ys=sum(y[:n])
  max_s=max(max_s,(xs-ys))
print(max_s)

Submission status: Time Limit Exceeded

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

zen_a = a[:N]
kou_a = list(np.array(a[2*N:]) * -1)

heapq.heapify(zen_a)
heapq.heapify(kou_a)
zen_a_sum = []
kou_a_sum = []

for k in range(N, 2 * N+1):
    if k != N:
        heapq.heappush(zen_a, a[k-1])
        heapq.heappop(zen_a)
    zen_a_sum.append(sum(zen_a))

for k in range(N, 2 * N+1):
    if k != N:
        heapq.heappush(kou_a, -a[-k])
        heapq.heappop(kou_a)
    kou_a_sum.append(-sum(kou_a))

for i in range(len(zen_a_sum)):
    if zen_a_sum[i] - kou_a_sum[-i-1] > ans:
        ans = zen_a_sum[i] - kou_a_sum[-i-1]
print(ans)

Submission status: Time Limit Exceeded

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

zen_a = a[:N]
kou_a = list(map(lambda x: x*(-1), a[2*N:]))

heapq.heapify(zen_a)
heapq.heapify(kou_a)
zen_a_sum = []
kou_a_sum = []

for k in range(N, 2 * N+1):
    if k != N:
        heapq.heappush(zen_a, a[k-1])
        heapq.heappop(zen_a)
    zen_a_sum.append(sum(zen_a))

for k in range(N, 2 * N+1):
    if k != N:
        heapq.heappush(kou_a, -a[-k])
        heapq.heappop(kou_a)
    kou_a_sum.append(-sum(kou_a))

for i in range(len(zen_a_sum)):
    if zen_a_sum[i] - kou_a_sum[-i-1] > ans:
        ans = zen_a_sum[i] - kou_a_sum[-i-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n=int(input())
a=list(map(int,input().split()))
before=a[:n]
hb=heapq.heapify(before)
sum_front=[0]*(3*n)
sum_after=[-float("inf")]*(3*n)

after=[]
for i in range(3*n-1,2*n-1,-1):
    after.append(-a[i])

ha=heapq.heapify(after)

sum_front[n-1]=sum(before)
sum_after[3*n-n]=(-1)*sum(after)

for i in range(n,2*n):
    heapq.heappush(before,a[i])
    t=heapq.heappop(before)

    sum_front[i]=sum(before)

for i in range(2*n-1,n-1,-1):
    heapq.heappush(after,-a[i])
    heapq.heappop(after)
    sum_after[i]=sum(after)*(-1)


ans=-float("inf")
for i in range(n-1,2*n):
    tmp=sum_front[i]-sum_after[i+1]
    ans=max(ans,tmp)

print(ans)

Submission status: Time Limit Exceeded

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

answer=-float("inf")
for i in range(N,2*N+1):
  alist1=alist[:i]
  alist2=alist[i:]
  #print(alist1,alist2)
  
  alist1.sort(reverse=True)
  alist2.sort()
  maxn_a1=sum(alist1[:N])
  minn_a2=sum(alist2[:N])
  #print(maxn_a1,minn_a2)
  answer=max(answer,maxn_a1-minn_a2)

print(answer)

Submission status: Time Limit Exceeded

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

#dp[3N][N]
dp=[[0 for _ in range(N+1)] for _ in range(3*N+1)]
for i in range(1,3*N+1):
  for j in range(1,N+1):
    if i<j:
      break
    dp[i][j]=max(dp[i-1][j],alist[i-1]+dp[i-1][j-1])
#print(dp)

alist_rev=alist[::-1]
dp_rev=[[float("inf") for _ in range(N+1)] for _ in range(3*N+1)]
dp_rev[0][0]=0
for i in range(1,3*N+1):
  dp_rev[i][0]=0
  for j in range(1,N+1):
    if i<j:
      break
    dp_rev[i][j]=min(dp_rev[i-1][j],alist_rev[i-1]+dp_rev[i-1][j-1])
#print(dp_rev)

slist=[]
for i in range(3*N+1):
  slist.append(dp[i][N])
  
slist_rev=[]
for i in range(3*N+1):
  slist_rev.append(dp_rev[-i-1][N])
  
#print(slist)
#print(slist_rev)

answer=-float("inf")
for i in range(N,2*N+1):
  score=slist[i]-slist_rev[i]
  answer=max(score,answer)
  
print(answer)

Submission status: Time Limit Exceeded

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

dp = [[-float('inf')] * (N + 1) for _ in range(2 * N + 1)]
for i in range(2 * N + 1):
    dp[i][0] = 0
for i in range(2 * N):
    for j in range(1, N + 1):
        dp[i + 1][j] = max(dp[i][j], dp[i][j - 1] + A[i])

dp2 = [0] * (N + 1)
for i in range(N + 1):
    B = A[i + N:]
    B.sort()
    dp2[i] = sum(B[:N])

ans = -float('inf')
for i in range(N + 1):
    S1 = dp[i + N][N]
    S2 = dp2[i]
    ans = max(ans, S1 - S2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

ans=-float('inf')
for i in range(n+1):
    tmp1=a[:n+i]
    tmp2=a[n+i:]
    tmp1.sort(reverse=True)
    tmp2.sort()
    ans=max(ans,sum(tmp1[:n])-sum(tmp2[:n]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

# d = [8, 2, 2, 7, 4, 6, 5, 3, 8]

N = int(input())
d = list(map(int, input().split()))
d_rev = d[::-1]

d1 = d[:N]
heapq.heapify(d1)
d2 = [-i for i in d_rev[:N]]
heapq.heapify(d2)
sum_d1 = sum(d1)
sum_d2 = sum(d2)

sum_d1_arr = [sum_d1]
sum_d2_arr = [sum_d2]

for k in range(N, 2 * N):
    l = d[:]
    c = sum_d1_arr[-1]
    c += d[k]
    n = heapq.heappushpop(d1, d[k])
    c -= n
    sum_d1_arr.append(c)

    m = d[:]
    e = sum_d2_arr[-1]
    e += -d_rev[k]
    n = heapq.heappushpop(d2, -1 * d_rev[k])
    e -= n
    sum_d2_arr.append(e)

print(max(v+w for v, w in zip(sum_d1_arr, sum_d2_arr[::-1])))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

left = sorted(a[:N])
max_left = [sum(left)]

right = sorted([-x for x in a[-N:]])
min_right = [sum(right) * -1]

for i in range(N, 2 * N):
    heappush(left, a[i])
    heappop(left)
    max_left.append(sum(left))

    heappush(right, a[3 * N - i - 1] * -1)
    heappop(right)
    min_right.append(sum(right) * -1)

ans = float('-inf')
for l, r in zip(max_left, min_right[::-1]):
    ans = max(l - r, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=-99999999999999999999
for k in range(n,n*2+1):
  s=a[0:k]
  s.sort()
  s.reverse()
  f=sum(s[0:n])
  d=a[k:3*n]
  d.sort()
  h=sum(d[0:n])
  ans=max(ans,f-h)
print(ans)