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:
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_bef, a_aft = a[:n], list(map(lambda x: -x, a))[-n:]
    a_bef_sum, a_aft_sum = {n: sum(a_bef)}, {2 * n: -sum(a_aft)}

    heapq.heapify(a_bef)
    heapq.heapify(a_aft)
    for i in range(n):
        bef_key = n + i
        heapq.heappush(a_bef, a[bef_key])
        a_bef_sum[bef_key+1] = a_bef_sum[bef_key] - heapq.heappop(a_bef) + a[bef_key]

        aft_key = n * 2 - i - 1
        heapq.heappush(a_aft, a[aft_key])
        a_aft_sum[aft_key] = a_aft_sum[aft_key+1] + heapq.heappop(a_aft) + a[aft_key]

    ans = - pow(10, 14)
    for i in range(n):
        diff = a_bef_sum[n+i] - a_aft_sum[n+i]
        if diff > ans:
            ans = diff
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq as hq
N = int(input())
a = list(map(int,input().split()))
heap = a[:N].copy()
hq.heapify(heap)
s = sum(heap)
ls = [s]
for k in range(N,2*N):
    x = hq.heappushpop(heap, a[k])
    s = s + a[k] - x
    ls.append(s)
heap = [-x for x in a[2*N:]]
hq.heapify(heap)
s = sum(heap)
rs = [s]
for k in range(2*N-1, N-1, -1):
    x = hq.heappushpop(heap,-a[k])
    s = s - a[k] - x
    rs.append(s)
print(max([ls[k] + rs[-k-1] for k in range(N)]))

Submission status: Wrong Answer

Solution code:
def solve():
    from heapq import heapify, heappush, heappop

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

    before = A[:N]
    after = [-n for n in A[N * 2:]]
    bes = sum(before)
    afs = sum(after)
    
    heapify(before)
    heapify(after)
    
    result = [0] * (N + 1)
    result[0] = bes
    result[-1] = afs
    
    for i in range(N, N * 2):
        a = A[i]
        k = heappop(before)
        heappush(before, a)
        bes += a - k
        result[i-N+1] += bes
    
    for i in range(N * 2 - 1, N - 1, -1):
        a = -A[i]
        k = heappop(after)
        heappush(after, a)
        afs += a - k
        result[i - N] += afs

    return max(result)

print(solve())

Submission status: Wrong Answer

Solution code:
def solve():
    from heapq import heapify, heappush, heappop

    N = int(input())
    A = list(map(int, input().split()))
    c = N * 3
    ans = 0
    
    half = c//2 if N % 2 == 0 else c//2 + 1
    before = A[:half]
    heapify(before)
    after = list(map(lambda x: x * (-1), A[half:]))
    heapify(after)

    if N > 1:
        for _ in range(N//2):
            heappop(before)
            heappop(after)
        
    if N % 2 == 1:
        heappop(before)
    ans = sum(before) + sum(after)

    return ans

print(solve())

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush


class MaxHeap:
    def __init__(self, li):
        self.hp = []
        for e in li:
            heappush(self.hp, -e)

    def push(self, x):
        heappush(self.hp, -x)

    def pop(self):
        ret = heappop(self.hp)
        ret *= -1
        return ret

    def seak(self):
        return -self.hp[0]

    def sum(self):
        return -sum(self.hp)


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

f = a[:n]
s = a[n:2*n]
t = a[2*n:]

heapify(f)
t = MaxHeap(t)

fi = 0
ti = n - 1

for _ in range(n):
    ef = f[0]
    et = t.seak()

    sf = s[fi]
    tf = s[ti]

    f_diff = sf - ef
    t_diff = et - tf

    if f_diff < 0 < t_diff:
        if abs(f_diff) > abs(t_diff):
            fi += 1
        else:
            ti -= 1

    else:
        if f_diff > t_diff:
            _ = heappop(f)
            es = s[fi]
            heappush(f, es)
            fi += 1
        else:
            _ = t.pop()
            es = s[ti]
            t.push(es)
            ti -= 1

ans = sum(f) - t.sum()
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
a_left = sorted(a[:N])
a_right = sorted(a[2*N:])
sum_left = sum(a_left)
sum_right = sum(a_right)
res = sum_left - sum_right
a_right = [-elem for elem in a_right]
heapq.heapify(a_right)
heapq.heapify(a_left)
sr = [0]*(N+1)
sr[0] = sum_right

for i,elem in enumerate(reversed(a[N:2*N])):
    now = -heapq.heappop(a_right)
    if now > elem:
        heapq.heappush(a_right, -elem)
        sum_right += (elem-now)
    else:
        heapq.heappush(a_right, -now)
    sr[i+1] = sum_right

for i,elem in enumerate(a[N:2*N]):
    now = heapq.heappop(a_left)
    if now < elem:
        heapq.heappush(a_left, elem)
        sum_left += (elem-now)
    else:
        heapq.heappush(a_left, now)
    res = max(res, sum_left-sr[N-i-1])
print(res)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
N = int(input())
a = list(map(int,input().split()))
a_left = sorted(a[:N])
a_right = sorted(a[N:])
sum_left = sum(a_left)
sum_right = sum(a_right[:N])
res = sum_left - sum_right

heapq.heapify(a_left)

len_left = N
for elem in a[N:2*N]:
    le = bisect.bisect_left(a_right, elem)
    #a_right.remove(elem)
    if le < N:
        sum_right -= elem
        sum_right += a_right[N-1]
    now = heapq.heappop(a_left)
    if now < elem:
        heapq.heappush(a_left, elem)
        sum_left += (elem-now)
    res = max(res, sum_left-sum_right)
print(res)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
N = int(input())
a = list(map(int,input().split()))
a_left = sorted(a[:N])
a_right = sorted(a[N:])
sum_left = sum(a_left)
sum_right = sum(a_right[:N])
res = sum_left - sum_right

heapq.heapify(a_left)

len_left = N
for elem in a[N:2*N]:
    le = bisect.bisect_left(a_right, elem)
    a_right.remove(elem)
    if le < N:
        sum_right -= elem
        sum_right += a_right[N-1]
    now = heapq.heappop(a_left)
    if now < elem:
        heapq.heappush(a_left, elem)
        sum_left += (elem-now)
    res = max(res, sum_left-sum_right)
print(res)

Submission status: Wrong Answer

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

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

q = []
heapq.heapify(q)
for i in range(n):
    heapq.heappush(q, al[i])

idx = n
for i in range(n, 2*n):
    if q[0]<al[i]:
        idx = i
        heapq.heappush(q, al[i])
        heapq.heappop(q)

print(sum(q) - sum(sorted(al[idx+1:])[:n]))

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        N = len(init_val)
        self.num = 2**(N-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(N):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        N = len(init_val)
        self.num = 2**(N-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(N):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted([(a, i) for i, a in enumerate(A)], key=lambda x:x[0])

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        N = len(init_val)
        self.num = 2**(N-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(N):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
z = dict()
for i, b in enumerate(B):
    z[b] = i

ss = SegTree([3*N]*3*N, 3*N, min)
bs = []
y = 0
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    y += x
    if i < N-1:
        continue
    if i == N-1:
        bs.append(y)
    else:
        mx = ss.query(0, 3*N)
        y = y - B[mx]
        ss.update(mx, 3*N)
        bs.append(y)

ss = SegTree([-1]*3*N, -1, max)
nbs = []
y = 0
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    y += x
    if i < N-1:
        continue
    if i == N-1:
        nbs.append(y)
    else:
        mx = ss.query(0, 3*N)
        y = y - B[mx]
        ss.update(mx, -1)
        nbs.append(y)

#print(B)
#print(bs)
#print(nbs)
r = -10**18
for i in range(N+1):
    r = max(r, bs[i] - nbs[N-i])
print(r)

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
z = dict()
for i, b in enumerate(B):
    z[b] = i

ss = SegTree([3*N+1] * 3*N, 3*N, 3*N+1, min)
bs = []
y = 0
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[x]+1, z[x]+1)
    y += x
    if i < N-1:
        continue
    if i == N-1:
        bs.append(y)
    else:
        mx = ss.query(0, 3*N+1)
        y = y - B[mx-1]
        ss.update(mx, 3*N+1)
        bs.append(y)

ss = SegTree([-1] * 3*N, 3*N, -1, max)
nbs = []
y = 0
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[x]+1, z[x]+1)
    y += x
    if i < N-1:
        continue
    if i == N-1:
        nbs.append(y)
    else:
        mx = ss.query(0, 3*N+1)
        y = y - B[mx-1]
        ss.update(mx, -1)
        nbs.append(y)

#print(B)
#print(bs)
#print(nbs)
r = -10**18
for i in range(N+1):
    r = max(r, bs[i] - nbs[N-i])
print(r)

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
z = dict()
for i, b in enumerate(B):
    z[b] = i

ss = SegTree([3*N+1] * 3*N, 3*N, 3*N+1, min)
bs = [0]
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[x]+1, z[x]+1)
    if i < N:
        continue
    mx = ss.query(0, 3*N+1)
    bs.append(B[mx-1]+bs[-1])
    ss.update(mx, 3*N+1)
ss = SegTree([-1] * 3*N, 3*N, -1, max)
nbs = [0]
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[x]+1, z[x]+1)
    if i < N:
        continue
    mx = ss.query(0, 3*N+1)
    nbs.append(B[mx-1]+nbs[-1])
    ss.update(mx, -1)
#print(B)
#print(bs)
#print(nbs)
y, W = 0, sum(A)
r = -10**18
for i, x in enumerate(A):
    if i == 2*N:
        break
    y+=x
    if i < N-1:
        continue
    r = max(r, (y-bs[i-(N-1)]) - (W-y-nbs[2*N-1-i]))
print(r)

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
z = dict()
for i, b in enumerate(B):
    z[b] = i

ss = SegTree([3*N] * 3*N, 3*N, 3*N, min)
bs = [0]
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[x]+1, z[x]+1)
    if i < N:
        continue
    mx = ss.query(0, 3*N+1)
    bs.append(B[mx-1]+bs[-1])
    ss.update(mx, 3*N)
ss = SegTree([-1] * 3*N, 3*N, -1, max)
nbs = [0]
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[x]+1, z[x]+1)
    if i < N:
        continue
    mx = ss.query(0, 3*N+1)
    nbs.append(B[mx-1]+nbs[-1])
    ss.update(mx, -1)
#print(B)
#print(bs)
#print(nbs)
y, W = 0, sum(A)
r = -10**18
for i, x in enumerate(A):
    if i == 2*N:
        break
    y+=x
    if i < N-1:
        continue
    r = max(r, (y-bs[i-(N-1)]) - (W-y-nbs[2*N-1-i]))
print(r)

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
z = dict()
for i, b in enumerate(B):
    z[b] = i

ss = SegTree([3*N] * 3*N, 3*N, 3*N, min)
bs = [0]
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    if i < N:
        continue
    mx = ss.query(0, 3*N+1)
    bs.append(B[mx]+bs[-1])
    ss.update(mx, 3*N)
ss = SegTree([-1] * 3*N, 3*N, -1, max)
nbs = [0]
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    if i < N:
        continue
    mx = ss.query(0, 3*N+1)
    nbs.append(B[mx]+nbs[-1])
    ss.update(mx, -1)
#print(B)
#print(bs)
#print(nbs)
y, W = 0, sum(A)
r = -10**18
for i, x in enumerate(A):
    if i == 2*N:
        break
    y+=x
    if i < N-1:
        continue
    r = max(r, (y-bs[i-(N-1)]) - (W-y-nbs[2*N-1-i]))
print(r)

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
z = dict()
for i, b in enumerate(B):
    z[b] = i

ss = SegTree([3*N] * 3*N, 3*N, 3*N, min)
bs = [0]
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    if i < N:
        continue
    mx = ss.query(0, 3*N+1)
    bs.append(B[mx]+bs[-1])
    ss.update(mx, 3*N)
ss = SegTree([-1] * 3*N, 3*N, -1, max)
nbs = [0]
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    if i < N:
        continue
    mx = ss.query(0, 3*N+1)
    nbs.append(B[mx]+nbs[-1])
    ss.update(mx, 0)
#print(B)
#print(bs)
#print(nbs)
y, W = 0, sum(A)
r = -10**18
for i, x in enumerate(A):
    if i == 2*N:
        break
    y+=x
    if i < N-1:
        continue
    r = max(r, (y-bs[i-(N-1)]) - (W-y-nbs[2*N-1-i]))
print(r)

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
z = dict()
for i, b in enumerate(B):
    z[b] = i

ss = SegTree([3*N] * 3*N, 3*N, 3*N, min)
bs = [0]
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    if i < N:
        continue
    mx = ss.query(0, 3*N)
    bs.append(B[mx]+bs[-1])
    ss.update(mx, 3*N)
ss = SegTree([-1] * 3*N, 3*N, -1, max)
nbs = [0]
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    if i < N:
        continue
    mx = ss.query(0, 3*N)
    nbs.append(B[mx]+nbs[-1])
    ss.update(mx, 0)
#print(B)
#print(bs)
#print(nbs)
y, W = 0, sum(A)
r = -10**18
for i, x in enumerate(A):
    if i == 2*N:
        break
    y+=x
    if i < N-1:
        continue
    r = max(r, (y-bs[i-(N-1)]) - (W-y-nbs[2*N-1-i]))
print(r)

Submission status: Wrong Answer

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
z = dict()
for i, b in enumerate(B):
    z[b] = i

ss = SegTree([3*N] * 3*N, 3*N, 3*N, min)
bs = [0]
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    if i < N:
        continue
    mx = ss.query(0, 3*N)
    bs.append(B[mx]+bs[-1])
    ss.update(mx, 3*N)
ss = SegTree([0] * 3*N, 3*N, 0, max)
nbs = [0]
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[x], z[x])
    if i < N:
        continue
    mx = ss.query(0, 3*N)
    nbs.append(B[mx]+nbs[-1])
    ss.update(mx, 0)
#print(B)
#print(bs)
#print(nbs)
y, W = 0, sum(A)
r = -10**18
for i, x in enumerate(A):
    if i == 2*N:
        break
    y+=x
    if i < N-1:
        continue
#    print(i, (y-bs[i-(N-1)]), W-y, (W-y-nbs[N-(i-(N-1))]))
    r = max(r, (y-bs[i-(N-1)]) - (W-y-nbs[2*N-1-i]))
print(r)

Submission status: Wrong Answer

Solution code:
import itertools
import math
import heapq

N = int(input())
nums = list(map(int,input().split(" ")))

half1 = nums[:N]
middle= nums[N:2 *N]
half2 = nums[2 *N:]
half2  = list(map(lambda x:-x ,half2) )

heapq.heapify(half1)
heapq.heapify(half2)
count = 0
lsum = sum(half1)
rsum = sum(half2)
ruiseki_left = [lsum]
ruiseki_right= [rsum]

for i in range(N):
    head = half1[0]
    if middle[i] > head:
        ruiseki_left.append(ruiseki_left[-1]  - head +  middle[i])
        heapq.heappop(half1)
        heapq.heappush(half1,middle[i])
    else:
        ruiseki_left.append(ruiseki_left[-1] )
middle.reverse()
for i in range(N):
    head = half2[0]
    if middle[i] > head:
        ruiseki_right.append(ruiseki_right[-1]  - head +   (-middle[i]))
        heapq.heappop(half2)
        heapq.heappush(half2,-middle[i])
    else:
        ruiseki_right.append(ruiseki_right[-1])
# print(ruiseki_left)
# print(ruiseki_right)
ans = - (10 **20)
for i in range(N):

    ans = max(ans,ruiseki_left[i] + ruiseki_right[N - i])
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import math
import heapq

N = int(input())
nums = list(map(int,input().split(" ")))

half1 = nums[:N]
middle= nums[N:2 *N]
half2 = nums[2 *N:]
half2  = list(map(lambda x:-x ,half2) )

heapq.heapify(half1)
heapq.heapify(half2)
count = 0
l = 0
r = N - 1
for _ in range(N):

    if r < l:
        break
    h1 = half1[0]
    h2 = half2[0] # マイナスの値
    h2 *= -1
    middle_l = middle[l]
    middle_r = middle[r]
    if middle_l  < h1  and middle_r > h2: #入れ替えても意味のない場合 →中央のカウンタを進める
        c1 = h2 - middle_l
        c2 = h1 - middle_r
        if c1 < c2:
            l += 1
        else:
            r -= 1
    else:
        if middle_l -  h1   >   h2 - middle_r: # 左と入れ替えた方が美味しい場合
            heapq.heappop(half1)
            heapq.heappush(half1,middle_l)
            l += 1
        else:
            heapq.heappop(half2)
            heapq.heappush(half2, middle_r)
            r -= 1
print(sum(half1) - sum(list(map(abs,(half2)))))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heappushpop


N = int(input())

lq = []
rq = []

A = list(map(int, input().split()))
B = [0] * (3 * N)
if N % 2 == 0:
    for idx, a in enumerate(A):
        if idx < (3 * N) // 2:
            heappush(lq, (a, idx))
        elif idx >= (3 * N) // 2:
            heappush(rq, (-1 * a, idx))
    rp = (3 * N) // 2
    lp = rp - 1
else:
    for idx, a in enumerate(A):
        if idx < (3 * N) // 2:
            heappush(lq, (a, idx))
        elif idx >= (3 * N) // 2 + 1:
            heappush(rq, (-1 * a, idx))
    rp = lp = (3 * N) // 2

A = list(A)
cnt = N
lc = heappop(lq)
rc = heappop(rq)
while cnt > 0:
    if cnt % 2 == 0:
        if (A[rp] - lc[0]) >= (-1 * rc[0] - A[lp]):
            B[lc[1]] = 1
            lc = heappushpop(lq, lc)
            while B[lc[1]]:
                lc = heappop(lq)
            lp = rp
        else:
            B[rc[1]] = 1
            rc = heappushpop(rq, rc)
            while B[rc[1]]:
                rc = heappop(rq)
            rp = lp
    else:
        if (A[rp] - lc[0]) >= (-1 * rc[0] - A[lp]):
            B[lc[1]] = 1
            lc = heappushpop(lq, lc)
            while B[lc[1]] and len(lq):
                lc = heappop(lq)
            rp += 1
            while B[rp] and rp < len(B):
                rp += 1
        else:
            B[rc[1]] = 1
            rc = heappushpop(rq, rc)
            while B[rc[1]] and len(rq):
                rc = heappop(rq)
            lp -= 1
            while B[lp] and lp >= 0:
                lp -= 1
    cnt -= 1

pos = 1
ans = 0
for i in range(3 * N):
    if pos <= N:
        if B[i] == 0:
            ans += A[i]
            pos += 1
    else:
        if B[i] == 0:
            ans -= A[i]

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
a = list(map(int,input().split()))
l1 = []
l2 = []
for i in range(n):
    l1.append(a[i])
    l2.append(-1*a[-(i+1)])
ni1 = n
ni2 = 2*n-1
heapq.heapify(l1)
heapq.heapify(l2)
for i in range(n):
    p = heapq.heappop(l1)
    q = -1*heapq.heappop(l2)
    x = a[ni1] - p
    y = q - a[ni2]
    if x >= y:
        heapq.heappush(l2,q*-1)
        heapq.heappush(l1,a[ni1])
        ni1 += 1
    else:
        heapq.heappush(l1,p)
        heapq.heappush(l2,-1*a[ni2])
        ni2 += 1
print(sum(l1)+sum(l2))