Problem: 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'.

Submission attempts (in order):
N = int(input())
a = list(map(int, input().split()))

import heapq
que1 = []
heapq.heapify(que1)
S = [0] * (2*N + 1)
for i in range(N):
    S[i + 1] = S[i] + a[i]
    #que1.append(a[i])
    heapq.heappush(que1, a[i])
que2 = []
heapq.heapify(que2)
T = [0] * (2*N + 1)
for i in range(N):
    T[i + 1] = T[i] + a[3*N - i - 1]
    
    heapq.heappush(que2, -a[3*N - i - 1])

for i in range(N, 2*N):
    mi = heapq.heappop(que1)
    print(mi)
    if a[i] > mi:
        S[i + 1] = S[i] - mi + a[i]
        #heapq.heappop(que1)
        heapq.heappush(que1, a[i])
    else:
        S[i + 1] = S[i]
        heapq.heappush(que1, mi)
for i in range(N, 2*N):
    ma = heapq.heappop(que2) * -1
    print(ma)
    if a[3*N - i - 1] < ma:
        T[i + 1] = T[i] - ma + a[3*N - i - 1]
        #heapq.heappop(que2)
        
        heapq.heappush(que2, -a[3*N - i - 1])
    else:
        T[i + 1] = T[i]
        heapq.heappush(que2, -ma)

res = -float('Inf')
for i in range(N, 2*N + 1):
    res = max(res, S[i] - T[3*N - i])
print(res)


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

import heapq
que1 = []
heapq.heapify(que1)
S = [0] * (2*N + 1)
for i in range(N):
    S[i + 1] = S[i] + a[i]
    #que1.append(a[i])
    heapq.heappush(que1, a[i])
que2 = []
heapq.heapify(que2)
T = [0] * (2*N + 1)
for i in range(N):
    T[i + 1] = T[i] + a[3*N - i - 1]
    
    heapq.heappush(que2, -a[3*N - i - 1])

for i in range(N, 2*N):
    mi = heapq.heappop(que1)
    print(mi)
    if a[i] > mi:
        S[i + 1] = S[i] - mi + a[i]
        #heapq.heappop(que1)
        heapq.heappush(que1, a[i])
    else:
        S[i + 1] = S[i]
        heapq.heappush(que1, mi)
for i in range(N, 2*N):
    ma = heapq.heappop(que2) * -1
    print(ma)
    if a[3*N - i - 1] < ma:
        T[i + 1] = T[i] - ma + a[3*N - i - 1]
        #heapq.heappop(que2)
        
        heapq.heappush(que2, -a[3*N - i - 1])
    else:
        T[i + 1] = T[i]
        heapq.heappush(que2, -ma)

res = -float('Inf')
for i in range(N, 2*N):
    res = max(res, S[i] - T[3*N - i])
print(res)

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

import heapq
que1 = []
heapq.heapify(que1)
S = [0] * (2*N + 1)
for i in range(N):
    S[i + 1] = S[i] + a[i]
    #que1.append(a[i])
    heapq.heappush(que1, a[i])
que2 = []
heapq.heapify(que2)
T = [0] * (2*N + 1)
for i in range(N):
    T[i + 1] = T[i] + a[3*N - i - 1]
    
    heapq.heappush(que2, -a[3*N - i - 1])

for i in range(N, 2*N):
    mi = heapq.heappop(que1)
    #print(mi)
    if a[i] > mi:
        S[i + 1] = S[i] - mi + a[i]
        #heapq.heappop(que1)
        heapq.heappush(que1, a[i])
    else:
        S[i + 1] = S[i]
        heapq.heappush(que1, mi)
for i in range(N, 2*N):
    ma = heapq.heappop(que2) * -1
    #print(ma)
    if a[3*N - i - 1] < ma:
        T[i + 1] = T[i] - ma + a[3*N - i - 1]
        #heapq.heappop(que2)
        
        heapq.heappush(que2, -a[3*N - i - 1])
    else:
        T[i + 1] = T[i]
        heapq.heappush(que2, -ma)

res = -float('Inf')
for i in range(N, 2*N + 1):
    res = max(res, S[i] - T[3*N - i])
print(res)


Verdicts: Wrong Answer

Wrong Answer

Accepted