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:
N=int(input())
A=list(map(int,input().split()))
h1=A[:N]
L=[0 for i in range(N+1)]
L[0]=sum(h1)
import heapq
heapq.heapify(h1)
for i in range(N):
  heapq.heappush(h1,A[N+i])
  heapq.heappop(h1)
  L[i+1]=sum(h1)
h=A[2*N:]
h2=[-i for i in h]
R=[0 for i in range(N+1)]
R[N]=-sum(h2)
heapq.heapify(h2)
for i in range(N):
  heapq.heappush(h2,-A[2*N-1-i])
  heapq.heappop(h2)
  R[N-i-1]=-sum(h2)
import math
ans=-math.inf
for i in range(N):
  ans=max(ans,L[i]-R[i])
print(ans)

Submission status: Wrong Answer

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

from heapq import heapify, heappushpop

# first half
fh = []
l = a[:n]
fh.append(sum(l))
heapify(l)
for i in a[n:2*n]:
    if l[0] < i:
        fh.append(fh[-1] + i - heappushpop(l, i))
    else:
        fh.append(fh[-1])

# latter half
lh = []
l = [-i for i in a[2*n:]]
lh.append(sum(l))
heapify(l)
for i in a[2*n-1:n-1:-1]:
    if l[0] < -i:
        lh.append(lh[-1] - i - heappushpop(l, i))
    else:
        lh.append(lh[-1])

ans = fh[0] + lh[n]
for i in range(1, n+1):
    if ans < fh[i] + lh[n-i]:
        ans = fh[i] + lh[n-i]

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify

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

ll = al[0:n]
cl = al[n:2*n]
rl = al[2*n:3*n]
rl = list(map(lambda x: -x, rl))


heapify(ll)
heapify(rl)

ll_vals = []
ll_vals.append(sum(ll))
c_sum = sum(ll)
c_max = c_sum
for i in range(n):
    poped = heappop(ll)
    c_sum -= poped
    heappush(ll,cl[i])
    c_sum += cl[i]
    c_max = max(c_max, c_sum)
    ll_vals.append(c_max)


rl_vals = []
rl_vals.append(-sum(rl))
c_sum = -sum(rl)
c_min = c_sum
for i in range(n):
    poped = -heappop(rl)
    c_sum -= poped
    heappush(rl,-cl[n-1-i])
    c_sum += cl[n-1-i]
    c_min = min(c_min, c_sum)
    rl_vals.append(c_min)


ans = -1*(10**9)
for i in range(n+1):
    v = ll_vals[i] - rl_vals[n-i]
    ans = max(ans,v)

print(ans)

Submission status: Wrong Answer

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):
  curr_sum=base_sum
  
  a1_m=a_m[:i]
  j=0
  for e in a1_m:
    if e > a1[j]:
      curr_sum+=e-a1[j]
      j+=1

  a2_m=a_m[i:]
  j=-1
  for e in a2_m:
    if e < a2[j]:
      curr_sum+=a2[j]-e
      j-=1

  max_s=max(max_s,curr_sum)
  
print(max_s)

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
A = list(map(int,input().split()))
L = A[:n]
R = A[2*n:]
R = list(map(lambda x:-x,R))
sum_l = [sum(L)]
sum_r = [sum(R)]
heapq.heapify(L)
heapq.heapify(R)
for i in range(n):
    elem = A[n+i]
    heapq.heappush(L,elem)
    sum_l.append(sum_l[-1] + elem -heapq.heappop(L))
for i in range(n):
    elem = -A[2*n-1-i]
    heapq.heappush(L,elem)
    sum_r.append(sum_r[-1] + elem -heapq.heappop(R))
ans = -float('inf')
sum_r = sum_r[::-1]
for i in range(len(sum_l)):
    ans = max(ans,sum_l[i] + sum_r[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def main():
    rl=sys.stdin.readline

    n=int(rl().strip())
    a=list(map(int,rl().strip().split()))

    fl=sorted(a[:n],reverse=True)
    ll=sorted(a[n:3*n])
    fmn=fl[-1]
    lmx=ll[n-1]
    maxscore=sum(fl)-sum(ll[:n])
    ts=maxscore
    s=0
    t=0
    for i in range(1,n):
        if fmn<a[n+i-1]:
            s+=1
            ts+=a[n+i-1]-fmn
            fmn=sorted(a[:n+i-1])[s]
        if lmx>=a[n+i-1]:
            t+=1
            lmx=sorted(a[n+i:])[n-t]
            ts+=a[n+i-1]-lmx
        maxscore=max(ts,maxscore)
    print(maxscore)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
rl=sys.stdin.readline

n=int(rl().strip())
a=list(map(int,rl().strip().split()))

fl=sorted(a[:n],reverse=True)
ll=sorted(a[n:3*n])
fmn=fl[-1]
lmx=ll[n-1]
maxscore=sum(fl)-sum(ll[:n])
ts=maxscore
s=0
t=0
for i in range(1,n):
  if fmn<a[n+i-1]:
    s+=1
    ts+=a[n+i-1]-fmn
    fmn=min(fl[-s-1],fmn)
  if lmx>=a[n+i-1]:
    t+=1
    lmx=sorted(a[n+i:])[n-t]
    ts+=a[n+i-1]-lmx
  maxscore=max(ts,maxscore)
print(maxscore)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heapreplace
n = int(input())
a = list(map(int, input().split()))
a1 = a[:n]
heapify(a1)
a2 = a[n:2*n]
a3 = [-i for i in a[2*n:]]
heapify(a3)
b1 = [sum(a1)]
b2 = [sum(a3)]
for i in range(n):
    b1.append(a2[i]-heapreplace(a1, a2[i]))
    b2.append(-heapreplace(a3, -a2[n-i-1])-a2[n-i-1])
for i in range(n):
    b1[i+1] += b1[i]
    b2[i+1] += b2[i]
accu = []
mx = b1[0]
for i in b1:
    mx = max(mx, i)
    accu.append(mx)
ans = -10**12
mx = b2[0]
for i in range(n+1):
    mx = max(mx, b2[i])
    ans = max(ans, mx+accu[n-i])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a1 = a[:n]
a1.sort()
a2 = a[n:2*n]
a3 = a[2*n:]
a3.sort(reverse=True)
b1 = [0] + [j-i for i, j in zip(a1, a2)]
b2 = [0] + [j-i for i, j in zip(reversed(a2), a3)]
for i in range(n):
    b1[i+1] += b1[i]
    b2[i+1] += b2[i]
accu = []
mx = 0
for i in b1:
    mx = max(mx, i)
    accu.append(mx)
ans = -10**12
mx = 0
for i in range(n+1):
    mx = max(mx, b2[i])
    ans = max(ans, mx+accu[n-i])
print(ans+sum(a1)-sum(a3))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify
from collections import deque
n = int(input())
a = list(map(int, input().split()))
a1 = a[:n]
heapify(a1)
a2 = a[n:2*n]
a2 = deque(a2)
a3 = [-i for i in a[2*n:]]
heapify(a3)
ans = []
score = sum(a1)+sum(a3)
for _ in range(n):
    d1 = a2[0] - a1[0]
    d2 = -a3[0] - a2[-1]
    if max(d1, d2)<=0:
        ans.append(score)
    score += max(d1, d2)
    if d1>d2:
        heappop(a1)
        heappush(a1, a2.popleft())
    else:
        heappop(a3)
        heappush(a3, -a2.pop())
ans.append(score)
print(max(ans))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify
from collections import deque
n = int(input())
a = list(map(int, input().split()))
a1 = a[:n]
heapify(a1)
a2 = a[n:2*n]
a2 = deque(a2)
a3 = [-i for i in a[2*n:]]
heapify(a3)
for _ in range(n):
    d1 = a2[0] - a1[0]
    d2 = -a3[0] - a2[-1]
    if max(d1, d2)<=0:
        break
    if d1>d2:
        heappop(a1)
        heappush(a1, a2.popleft())
    else:
        heappop(a3)
        heappush(a3, -a2.pop())
print(sum(a1)+sum(a3))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = 10**9
from heapq import heapify, heappop, heappush


def main():
    n = int(input())
    A = list(map(int, input().split()))

    L = A[:n]
    R = A[2*n:]
    R = list(map(lambda x:x*(-1), R))
    sum_l = [sum(L)]
    sum_r = [sum(R)]
    heapify(L)
    heapify(R)
    for i in range(n):
        elem = A[n+i]
        heappush(L, elem)
        sum_l.append(sum_l[-1] + elem - heappop(L))
    for i in range(n):
        elem = -A[2*n-1-i]
        heappush(R,elem)
        sum_r.append(sum_r[-1] + elem - heappop(R))
    ans = -INF
    for i in range(len(sum_l)):
        ans = max(ans, sum_l[i]+sum_r[-1-i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

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

# (1).左からN + 1～2N個のデータについて、iがいくつあるかのdictionary
# (2).左から2N個のデータのうち、大きい順にN個のデータの和
# (3).左から2N個のデータのうち、小さい順にN個のデータを、大きい順にheapqに入れたもの
# (4).右からN個のデータの和
# (5).右からN個のデータを、大きい順にheapqに入れたもの

# 上記を用いて、iを2N～N+1までずらし、そのたびに
# A[i]の数を(1)から減らす
# 次の数を(3)から取り出す。その数が(1)に存在していなければ何もしない
# 取り出した数を(2)に足す
# (4)にA[i]を足す
# (5)から一つ取り出し、(4)から引く
# (2) - (4)の最大値を更新

from collections import defaultdict

sortA = sorted(A[:2 * N])
smallA = sortA[:N]
largeA = sortA[N:]
dic = defaultdict(int)
for i in range(len(largeA)):
  dic[largeA[i]] += 1

leftsum = sum(sortA[N:])

import heapq as hq
leftq = list(map(lambda x:-x,smallA))
hq.heapify(leftq)

rightq = A[2 * N:]
rightsum = sum(rightq)
rightq = list(map(lambda x:-x,rightq))
hq.heapify(rightq)

ans = leftsum - rightsum

#print("leftsum",leftsum,"rightsum",rightsum,"ans",ans)
for i in range(2 * N - 1, N - 1, -1):
  #print("i",i,"A[i]",A[i])
  if dic[A[i]] > 0: # 除外対象である場合
    dic[A[i]] -= 1
    leftsum -= A[i]
    move = -hq.heappop(leftq)
    leftsum += move
    dic[move] += 1
    #print("leftsumから",A[i],"を除外",leftsum)
  hq.heappush(rightq, -A[i])
  rem = -hq.heappop(rightq)
  rightsum += A[i]
  rightsum -= rem
  
  if ans < leftsum - rightsum:
    ans = leftsum - rightsum
  #print("leftsum",leftsum,"rightsum",rightsum,"ans",ans)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

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

# (1).左からN + 1～2N個のデータについて、iがいくつあるかのdictionary
# (2).左から2N個のデータのうち、大きい順にN個のデータの和
# (3).左から2N個のデータのうち、小さい順にN個のデータを、大きい順にheapqに入れたもの
# (4).右からN個のデータの和
# (5).右からN個のデータを、大きい順にheapqに入れたもの

# 上記を用いて、iを2N～N+1までずらし、そのたびに
# A[i]の数を(1)から減らす
# 次の数を(3)から取り出す。その数が(1)に存在していなければ何もしない
# 取り出した数を(2)に足す
# (4)にA[i]を足す
# (5)から一つ取り出し、(4)から引く
# (2) - (4)の最大値を更新

from collections import defaultdict

sortA = sorted(A[:2 * N])
smallA = sortA[:N]
largeA = sortA[N:]
dic = defaultdict(int)
for i in range(len(largeA)):
  dic[largeA[i]] += 1

leftsum = sum(sortA[N:])

import heapq as hq
leftq = list(map(lambda x:-x,smallA))
hq.heapify(leftq)

rightq = A[2 * N:]
rightsum = sum(rightq)
rightq = list(map(lambda x:-x,rightq))
hq.heapify(rightq)

ans = leftsum - rightsum

#print("leftsum",leftsum,"rightsum",rightsum,"ans",ans)
for i in range(2 * N - 1, N - 1, -1):
  #print("i",i,"A[i]",A[i])
  if dic[A[i]] > 0: # 除外対象である場合
    dic[A[i]] -= 1
    leftsum -= A[i]
    leftsum += -hq.heappop(leftq)
    #print("leftsumから",A[i],"を除外",leftsum)
  hq.heappush(rightq, -A[i])
  rem = -hq.heappop(rightq)
  rightsum += A[i]
  rightsum -= rem
  
  if ans < leftsum - rightsum:
    ans = leftsum - rightsum
  #print("leftsum",leftsum,"rightsum",rightsum,"ans",ans)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

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

# (1).左から2N個のデータについて、iがいくつあるかのdictionary
# (2).左から2N個のデータのうち、大きい順にN個のデータの和
# (3).左から2N個のデータのうち、小さい順にN個のデータを、大きい順にheapqに入れたもの
# (4).右からN個のデータの和
# (5).右からN個のデータを、大きい順にheapqに入れたもの

# 上記を用いて、iを2N～N+1までずらし、そのたびに
# A[i]の数を(1)から減らす
# 次の数を(3)から取り出す。その数が(1)に存在していなければ何もしない
# 取り出した数を(2)に足す
# (4)にA[i]を足す
# (5)から一つ取り出し、(4)から引く
# (2) - (4)の最大値を更新

from collections import defaultdict
dic = defaultdict(int)
for i in range(N, 2 * N):
  dic[A[i]] += 1

sortA = sorted(A[:2 * N])
smallA = sortA[:N]
leftsum = sum(sortA[N:])

import heapq as hq
leftq = list(map(lambda x:-x,smallA))
hq.heapify(leftq)

rightq = A[2 * N:]
rightsum = sum(rightq)
rightq = list(map(lambda x:-x,rightq))
hq.heapify(rightq)

ans = leftsum - rightsum

for i in range(2 * N - 1, N - 1, -1):
  if dic[A[i]] > 0: # 除外対象である場合
    dic[A[i]] -= 1
    leftsum -= A[i]
    leftsum += -hq.heappop(leftq)
  hq.heappush(rightq, -A[i])
  rem = -hq.heappop(rightq)
  rightsum += A[i]
  rightsum -= rem
  
  if ans < leftsum - rightsum:
    ans = leftsum - rightsum
    
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0]*3*n
r=[-10000000000]*3*n
from heapq import heappop,heappush
h=[]
s=0
for i in a[:n]:
  heappush(h,i)
  s+=i
l[n-1]=s
for i in range(n,2*n):
  heappush(h,a[i])
  s+=a[i]
  s-=heappop(h)
  l[i]=s
h=[]
s=0
for i in a[2*n:]:
  heappush(h,-i)
  s+=-i
for i in range(2*n-1,n-2,-1):
  r[i]=s
  heappush(h,-a[i])
  s+=-a[i]
  s-=heappop(h)
print(max(l[i]+r[i]for i in range(3*n)))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0]*3*n
r=[-10000000]*3*n
from heapq import heappop,heappush
h=[]
s=0
for i in a[:n]:
  heappush(h,i)
  s+=i
l[n-1]=s
for i in range(n,2*n):
  heappush(h,a[i])
  s+=a[i]
  s-=heappop(h)
  l[i]=s
h=[]
s=0
for i in a[2*n:]:
  heappush(h,-i)
  s+=-i
for i in range(2*n-1,n-2,-1):
  r[i]=s
  heappush(h,-a[i])
  s+=-a[i]
  s-=heappop(h)
print(max(l[i]+r[i]for i in range(3*n)))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=-10**18
if n==1:
  for i in range(3*n):
    t=a[:]
    t.pop(i)
    t=a[0]-a[1]
    ans=max(t,ans)
  print(ans)
  exit(0)
a_minus=[-x for x in a]
af=a[:n]
ae=a_minus[2*n:]
f_sum=[sum(af)]
e_sum=[sum(ae)]
from heapq import heapify,heappop,heappush
heapify(af)
for aa in a[n:2*n]:
  heappush(af,aa)
  t=heappop(af)
  f_sum.append(f_sum[-1]+aa-t)
heapify(ae)
for aa in reversed(a[n:2*n]):
  heappush(ae,-aa)
  t=heappop(ae)
  e_sum.append(e_sum[-1]-aa-t)
for f,e in zip(f_sum,reversed(e_sum)):
  ans=max(ans,f+e)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

def f(idx):
    l = []
    r = []
    for a in A[:idx]:
        heapq.heappush(l, -a)
    for a in A[idx:]:
        heapq.heappush(r, a)
    before, after = 0, 0
    for i in range(N):
        before -= heapq.heappop(l)
    for i in range(N):
        after += heapq.heappop(r)
    #print(idx, before, after)
    return before - after

if N%2 == 0:
    print(f(3*N//2))
else:
    print(max(f(3*N//2), f(3*N//2+1)))

Submission status: Wrong Answer

Solution code:
import heapq

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

def f(idx):
    l = []
    r = []
    for a in A[:idx]:
        heapq.heappush(l, a)
    for a in A[idx:]:
        heapq.heappush(r, -a)
    while len(l)+len(r) > 2*N:
        if len(l) > len(r):
            heapq.heappop(l)
        else:
            heapq.heappop(r)
    #print(idx, l, r)
    return sum(l) + sum(r)

if N%2 == 0:
    print(f(3*N//2))
else:
    print(max(f(3*N//2), f(3*N//2+1)))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""


n = onem()

a = l()

fl = a[:n]
ba = a[2*n:]

normal = [sum(fl),sum(ba)]

ba = list(map(lambda x:-x,ba))

po = cl.deque(a[n:2*n])

hq.heapify(fl)
fll = fl
hq.heapify(ba)
baa = ba

for i in range(n):
	alpha = hq.heappop(fll)
	beta = hq.heappop(baa)

	if len(po) == 1:
		la = po[0]
		if la - alpha <= 0 and -beta - la <= 0:
			hq.heappush(fll,alpha)
			hq.heappush(baa,beta)
			break
		elif la - alpha >= -beta - la:
			hq.heappush(fll,la)
			hq.heappush(baa,beta)
		else:
			hq.heappush(baa,-la)
			hq.heappush(fll,alpha)

	else:
		aaa = po.popleft()
		bbb = po.pop()

		if aaa - alpha <= 0 and -beta - bbb <= 0:
			if aaa < bbb:
				po.append(aaa)
			else:
				po.appendleft(bbb)
		
		elif aaa - alpha >= -beta - bbb:
			hq.heappush(fll,aaa)
			hq.heappush(baa,beta)
			po.append(bbb)
		else:
			hq.heappush(baa,-bbb)
			hq.heappush(fll,alpha)
			po.appendleft(aaa)


print(max(normal[0]-normal[1],sum(fll)+sum(baa)))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""


n = onem()

a = l()

fl = a[:n]
ba = a[2*n:]

normal = [sum(fl),sum(ba)]

ba = list(map(lambda x:-x,ba))

po = cl.deque(a[n:2*n])

hq.heapify(fl)
fll = fl
hq.heapify(ba)
baa = ba

for i in range(n):
	alpha = hq.heappop(fll)
	beta = hq.heappop(baa)

	if len(po) == 1:
		la = po[0]
		if la - alpha <= 0 and -beta - la <= 0:
			hq.heappush(fll,alpha)
			hq.heappush(baa,beta)
			break
		elif la - alpha >= -beta - la:
			hq.heappush(fll,la)
			hq.heappush(baa,beta)
		else:
			hq.heappush(baa,-la)
			hq.heappush(fll,alpha)

	else:
		aaa = po.popleft()
		bbb = po.pop()

		if aaa - alpha <= 0 and -beta - bbb <= 0:
			if aaa < bbb:
				po.append(aaa)
			else:
				po.appendleft(bbb)
		
		elif aaa - alpha >= -beta - bbb:
			hq.heappush(fll,aaa)
			hq.heappush(baa,beta)
			po.append(bbb)
		else:
			hq.heappush(baa,-bbb)
			hq.heappush(fll,alpha)
			po.appendleft(aaa)

print(fll,baa)
print(max(normal[0]-normal[1],sum(fll)+sum(baa)))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""


n = onem()

a = l()

fl = a[:n]
ba = a[2*n:]

normal = [sum(fl),sum(ba)]

ba = list(map(lambda x:-x,ba))

po = cl.deque(a[n:2*n])

hq.heapify(fl)
fll = fl
hq.heapify(ba)
baa = ba

for i in range(n):
	alpha = hq.heappop(fll)
	beta = hq.heappop(baa)

	if len(po) == 1:
		la = po[0]
		if la - alpha <= 0 and -beta - la <= 0:
			break
		elif la - alpha >= -beta - la:
			hq.heappush(fll,la)
			hq.heappush(baa,beta)
		else:
			hq.heappush(baa,-la)
			hq.heappush(fll,alpha)

	else:
		aaa = po.popleft()
		bbb = po.pop()

		if aaa - alpha <= 0 and -beta - bbb <= 0:
			if aaa < bbb:
				po.append(aaa)
			else:
				po.appendleft(bbb)
		
		elif aaa - alpha >= -beta - bbb:
			hq.heappush(fll,aaa)
			hq.heappush(baa,beta)
			po.append(bbb)
		else:
			hq.heappush(baa,-bbb)
			hq.heappush(fll,alpha)
			po.appendleft(aaa)


print(max(normal[0]-normal[1],sum(fll)+sum(baa)))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""


n = onem()

a = l()

fl = a[:n]
ba = a[2*n:]

normal = [sum(fl),sum(ba)]

ba = list(map(lambda x:-x,ba))

po = cl.deque(a[n:2*n])

hq.heapify(fl)
fll = fl
hq.heapify(ba)
baa = ba

for i in range(n):
	alpha = hq.heappop(fll)
	beta = hq.heappop(baa)

	if len(po) == 1:
		la = po[0]
		if la - alpha <= 0 and -beta - la <= 0:
			break
		elif la - alpha >= -beta - la:
			hq.heappush(fll,la)
			hq.heappush(baa,beta)
		else:
			hq.heappush(baa,-la)
			hq.heappush(fll,alpha)

	else:
		aaa = po.popleft()
		bbb = po.pop()

		if aaa - alpha <= 0 and -beta - bbb <= 0:
			if aaa < bbb:
				po.append(bbb)
			else:
				po.appendleft(aaa)
		
		elif aaa - alpha >= -beta - bbb:
			hq.heappush(fll,aaa)
			hq.heappush(baa,beta)
			po.append(bbb)
		else:
			hq.heappush(baa,-bbb)
			hq.heappush(fll,alpha)
			po.appendleft(aaa)


print(max(normal[0]-normal[1],sum(fll)+sum(baa)))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""


n = onem()

a = l()

fl = a[:n]
ba = a[2*n:]

normal = [sum(fl),sum(ba)]

ba = list(map(lambda x:-x,ba))

po = cl.deque(a[n:2*n])

hq.heapify(fl)
fll = fl
hq.heapify(ba)
baa = ba

for i in range(n):
	alpha = hq.heappop(fll)
	beta = hq.heappop(baa)

	if len(po) == 1:
		la = po[0]
		if la - alpha >= -beta - la:
			hq.heappush(fll,la)
			hq.heappush(baa,beta)
		else:
			hq.heappush(baa,-la)
			hq.heappush(fll,alpha)

	else:
		aaa = po.popleft()
		bbb = po.pop()

		if aaa - alpha <= 0 and -beta - bbb <= 0:
			if aaa < bbb:
				po.append(bbb)
			else:
				po.appendleft(aaa)
		
		elif aaa - alpha >= -beta - bbb:
			hq.heappush(fll,aaa)
			hq.heappush(baa,beta)
			po.append(bbb)
		else:
			hq.heappush(baa,-bbb)
			hq.heappush(fll,alpha)
			po.appendleft(aaa)


print(max(normal[0]-normal[1],sum(fll)+sum(baa)))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""


n = onem()

a = l()

fl = a[:n]
ba = a[2*n:]

normal = [sum(fl),sum(ba)]

ba = list(map(lambda x:-x,ba))

po = cl.deque(a[n:2*n])

hq.heapify(fl)
fll = fl
hq.heapify(ba)
baa = ba

for i in range(n):
	alpha = hq.heappop(fll)
	beta = hq.heappop(baa)

	if len(po) == 1:
		la = po[0]
		if la - alpha >= -beta - la:
			hq.heappush(fll,la)
			hq.heappush(baa,beta)
		else:
			hq.heappush(baa,-la)
			hq.heappush(fll,alpha)

	else:
		aaa = po.popleft()
		bbb = po.pop()

		if aaa - alpha <= 0 and -beta - bbb <= 0:
			if aaa <= bbb:
				po.append(bbb)
			else:
				po.appendleft(aaa)
		
		elif aaa - alpha >= -beta - bbb:
			hq.heappush(fll,aaa)
			hq.heappush(baa,beta)
			po.append(bbb)
		else:
			hq.heappush(baa,-bbb)
			hq.heappush(fll,alpha)
			po.appendleft(aaa)


print(max(normal[0]-normal[1],sum(fll)+sum(baa)))

Submission status: Wrong Answer

Solution code:
N = int(input())

A = list(map(int,input().split()))
import heapq
L = A[:N]
heapq.heapify(L)
sum_L = sum(A[:N])
L_list = []
L_list.append(sum_L)
for i in range(N):
    sum_L += A[N+i]
    heapq.heappush(L,A[N+i])
    sum_L -= heapq.heappop(L)
    L_list.append(sum_L)

A = list(map(lambda x:-x, A[::-1]))
R = A[:N]
heapq.heapify(R)
sum_R = sum(A[:N])
R_list = []
R_list.append(sum_R)


for i in range(N):
    sum_R += A[N+i]
    heapq.heappush(R,A[N+i])
    sum_R -= heapq.heappop(R)
    R_list.append(sum_R)
maxi = -10000000000000000000000000000
R_list = R_list[::-1]
for i in range(N):
    maxi = max(maxi,L_list[i] + R_list[i])

print(maxi)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = list(map(int,input().split()))
import heapq
L = A[:N]
heapq.heapify(L)
sum_L = sum(A[:N])
L_list = []
L_list.append(sum_L)
for i in range(N):
    sum_L += A[N+i]
    heapq.heappush(L,A[N+i])
    sum_L -= heapq.heappop(L)
    L_list.append(sum_L)

A = list(map(lambda x:-x, A[::-1]))
R = A[:N]
heapq.heapify(R)
sum_R = sum(A[:N])
R_list = []
R_list.append(sum_R)


for i in range(N):
    sum_R += A[N+i]
    heapq.heappush(R,A[N+i])
    sum_R -= heapq.heappop(R)
    R_list.append(sum_R)
maxi = -1000000000000000
R_list = R_list[::-1]
for i in range(N):
    maxi = max(maxi,L_list[i] + R_list[i])

print(maxi)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))

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

    first_max = [0] * (n + 1)
    third_min = [0] * (n + 1)

    first_max[0] = sum(first)
    third_min[0] = sum(third)

    pq_first = PriorityQueue(first)
    cur = first_max[0]
    for i, x in enumerate(second, 1):
        if pq_first.top() < x:
            cur -= pq_first.pop()
            cur += x
            pq_first.push(x)
        first_max[i] = cur

    pq_third = PriorityQueue(third, desc=True)
    cur = third_min[0]
    for i, x in enumerate(second[::-1], 1):
        if pq_third.top() > x:
            cur -= pq_third.pop()
            cur += x
            pq_third.push(x)
        third_min[i] = cur

    ans = -INF
    for i in range(n):
        fi_idx = i
        th_idx = n - i
        ans = max(ans, first_max[fi_idx] - third_min[th_idx])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq


def solve(n):
  a = list(map(int,input().split()))
  # 左半分を計算して右端[n+idx]でメモ
  # 左半分は最大化したいので最小値が初めに出てくるようにする
  leftHsum = [0 for i in range(n+1)]
  leftH = a[0:n]
  heapq.heapify(leftH)
  leftHsum[0] = sum(leftH) # 
  for i in range(n):
    if leftH[0] < a[n+i]:
      leftHsum[i+1] = leftHsum[i] - leftH[0] + a[n+i]
      heapq.heappop(leftH)
      heapq.heappush(leftH, a[n+i])
    else:
      leftHsum[i+1] = leftHsum[i]
  # 右半分は負の値で保持する
  # もっとも大きい値から追い出していく
  rightHsum = [0 for i in range(n+1)]
  rightH = list(map(lambda x: -x,a[2*n:3*n]))
  heapq.heapify(rightH)
  rightHsum[0] = - sum(rightH)
  for i in range(n):
    if rightH[0] < -a[2*n-i-1]:
      rightHsum[i+1] = rightHsum[i] + rightH[0] + a[2*n-i-1]
      heapq.heappop(rightH)
      heapq.heappush(rightH, -a[2*n-i-1])
    else:
      rightHsum[i+1] = rightHsum[i]
  result = -1000000000000000000
  #print(leftHsum)
  #print(rightHsum)
  for i in range(n):
    result = max(result, leftHsum[0+i]-rightHsum[n-i])
  return result





n = int(input())
print(solve(n))