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 .

Solution (Python):


from heapq import *

def score(input_list):
    s = sum(input_list[:N])
    score_list = [s]
    l = input_list[:N]
    heapify(l)

    for val in input_list[N:2 * N]:
        s -= heappushpop(l, val)
        s += val
        score_list.append(s)

    return score_list

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split(" ")))
    B = list(map(lambda x : -x, reversed(A)))

    max_score = 0
    left_score = score(A)
    right_score = reversed(score(B))
    score_list = map(lambda x,y : x + y, left_score, right_score)
    print (max(score_list))

Solution (Python):
from heapq import *
r=reversed
N=int(input())
A=list(map(int,input().split()))
def w(L):
	q=L[:N]
	heapify(q)
	s=sum(q)
	yield s
	for e in L[N:2*N]:
		s+=e-heappushpop(q,e)
		yield s
print(max(map(sum,zip(w(A),r(list(w([-a for a in r(A)])))))))

Solution (Python):
from heapq import *
 
N = int(input())
A = list(map(int, input().split()))
B = list(map(lambda x: -x, reversed(A)))

def left_scores(L):
  s = sum(L[:N])
  scores = [s]
  q = L[:N]
  heapify(q)

  for e in L[N:2*N]:
    s -= heappushpop(q, e)
    s += e
    scores.append(s)
  return scores

print(max(map(lambda x: x[0]+x[1], zip(left_scores(A), reversed(left_scores(B))))))

Solution (Python):
import os
import sys
import heapq


def solve(n, a):
    res = -10 ** 20
    for i in range(n, 2 * n + 1):
        l = a[0:i]
        r = a[i:3 * n]
        l.sort(reverse=True)
        r.sort()
        res0 = sum(l[0:n]) - sum(r[0:n])
        if res0 > res:
            res = res0
    return res


def find_best(n, a):
    h = list()
    s = 0
    best_s = -10**20
    res = list()
    for i in range(0, 2 * n):
        heapq.heappush(h, a[i])
        s += a[i]
        if len(h) > n:
            m = heapq.heappop(h)
            s -= m
        if len(h) == n:
            if best_s < s:
                best_s = s
            res.append(best_s)
    return res


def solve_large(n, a):
    res = -10 ** 20
    max_l = find_best(n, a)
    b = [-x for x in reversed(a)]
    max_r = find_best(n, b)
    max_r.reverse()
    for l, r in zip(max_l, max_r):
        res0 = l + r
        if res < res0:
            res = res0
    return res


input_file = 'd1.in'
if os.path.exists(input_file):
    sys.stdin = open(input_file)
n = int(input())
a = list(map(int, input().split()))
print(solve_large(n, a))

Solution (Python):


import heapq


def calc_l_score(N, a):
    scores = [None] * (N + 1)
    queue = a[:N]
    heapq.heapify(queue)
    scores[0] = sum(queue)
    for i in range(N):
        na = a[N + i]
        heapq.heappush(queue, na)
        m = heapq.heappop(queue)
        scores[i + 1] = scores[i] + na - m
    return scores


def calc_r_score(N, a):
    scores = [None] * (N + 1)
    queue = []
    for i in range(1, N + 1):
        heapq.heappush(queue, -a[-i])
    scores[-1] = - sum(queue)
    for i in range(1, N + 1):
        na = a[-N - i]
        heapq.heappush(queue, -na)
        m = - heapq.heappop(queue)
        scores[-i - 1] = scores[-i] + na - m
    return scores


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

    ls = calc_l_score(N, a)
    rs = calc_r_score(N, a)
    return max([l - r for l, r in zip(ls, rs)])


if __name__ == "__main__":
    print(main())

Solution (Python):
import heapq

n = int(input())
a = list(map(int, input().split()))
hl = a[0: n]
hr = [-x for x in a[2*n: 3*n]]
heapq.heapify(hl)
heapq.heapify(hr)
sl = sum(hl)
sr = sum(hr)

bl = [sl]
br = [sr]
for i in range(1, n+1):
    heapq.heappush(hl, a[n-1+i])
    vl = heapq.heappop(hl)
    sl += a[n-1+i] - vl
    bl.append(sl)

    heapq.heappush(hr, -a[2*n-i])
    vr = heapq.heappop(hr)
    sr += -a[2*n-i] - vr
    br.append(sr)

max_score = -float('inf')
for i in range(n+1):
    max_score = max(max_score, bl[i]+br[n-i])


print(max_score)

Solution (Python):
import heapq
n=int(raw_input())
a=map(int,raw_input().split())
su=[0]*(3*n+1)
hp1=[]
hp2=[]
for i in xrange(3*n):
    su[i+1]+=su[i]+a[i]
for i in xrange(n):
    heapq.heappush(hp1,a[i])
    heapq.heappush(hp2,-a[i+2*n])
ans=-float("inf")
ta1=0
ta2=0
p=[]
b=[]
for i in xrange(n+1):
    p.append(su[n+i]-ta1)
    b.append(su[3*n]-su[2*n-i]-ta2)
    heapq.heappush(hp1,a[i+n])
    heapq.heappush(hp2,-a[2*n-i-1])
    ta1+=heapq.heappop(hp1)
    ta2+=-heapq.heappop(hp2)
    

for i in xrange(n+1):
    ans=max(ans,p[i]-b[n-i])
print ans

Solution (Python):

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))


popleft = [0]*(N+1)
A_LEFT = np.argsort(A[:(2*N)])
ind_left = 1
for i in range(N):
    while popleft[ind_left] > 0:
        ind_left += 1
    if A_LEFT[i] < N:
        popleft[ind_left] = A[A_LEFT[i]]
    else:
        popleft[max(ind_left, A_LEFT[i] - (N-1))] = A[A_LEFT[i]]
left_sum = np.cumsum(A)[(N-1):(2*N)] - np.cumsum(np.array(popleft))


popright = [0]*(N+1)
A_RIGHT = np.argsort(-A[::-1][:(2*N)])
ind_right = 1
for i in range(N):
    while popright[ind_right] > 0:
        ind_right += 1
    if A_RIGHT[i] < N:
        popright[ind_right] = A[3*N - 1 - A_RIGHT[i]]
    else:
        popright[max(ind_right, A_RIGHT[i] - (N-1))] = A[3*N - 1 - A_RIGHT[i]]
right_sum = np.cumsum(A[::-1])[(N-1):(2*N)] - np.cumsum(np.array(popright))



res = (left_sum - right_sum[::-1]).max()

res1 = (np.sort(A[:2*N])[N:]).sum() - A[2*N:].sum()
res2 = A[:N].sum() - (np.sort(A[N:])[:N]).sum()
print(max(res, res1, res2))

Solution (Python):
from heapq import *

N = int(input())

A = list(map(int, input().split()))
A_indexed = [(a, i) for i, a in enumerate(A)]

def scores():
  
  selected_left = A[:N] 
  heapify(selected_left)
  l_score = sum(selected_left)

  temp = sorted(A_indexed[N:])
  selected_right_set = set(temp[:N])
  unselected_right = temp[N:] 
  del temp
  r_score = sum(map(lambda x: x[0], selected_right_set))

  yield l_score,r_score

  for i in range(N, 2*N):
    a = A[i]
    
    if selected_left[0] < a:
      l_score -= heapreplace(selected_left, a)
      l_score += a
      
    if (a,i) in selected_right_set:
      r_score -= a
      selected_right_set.remove((a,i))

      n_element = heappop(unselected_right)
      while n_element[1] <= i:
        n_element = heappop(unselected_right)
      selected_right_set.add(n_element)
      r_score += n_element[0]

    yield l_score,r_score


print(max(map(lambda x: x[0]-x[1],scores())))

Solution (Python):
import sys
from heapq import heapify, heappush, heappop
from itertools import accumulate

inf = 1<<100

def solve():
    N = int(input())
    a = [int(i) for i in input().split()]
    ps = [0] + list(accumulate(a))

    psmin = [0] * (N + 1)
    minhp = a[:N]
    heapify(minhp)

    for i in range(1, N + 1):
        heappush(minhp, a[N - 1 + i])
        x = heappop(minhp)
        psmin[i] = psmin[i - 1] + x

    psmax = [0] * (N + 1)
    maxhp = [-ai for ai in a[2*N:]]
    heapify(maxhp)

    for i in range(1, N + 1):
        heappush(maxhp, -a[2*N - i])
        x = -heappop(maxhp)
        psmax[i] = psmax[i - 1] + x

    
    

    ans = -inf

    for i in range(0, N + 1):
        
        v = (ps[N + i] - psmin[i]) - (ps[3*N] - ps[N + i] - psmax[N - i])
        ans = max(ans, v)

    print(ans)
    pass

if __name__ == '__main__':
    solve()

Solution (Python):
from heapq import heappush, heappop
n = input()
A = map(int, raw_input().split())
left = [None]*(3*n+1)
right = [None]*(3*n+1)
lsum = rsum = 0
que = []
for i in xrange(3*n):
    lsum += A[i]
    heappush(que, A[i])
    if len(que) > n:
        v = heappop(que)
        lsum -= v
    if len(que) == n:
        left[i] = lsum
que = []
for i in xrange(3*n-1, -1, -1):
    rsum += A[i]
    heappush(que, -A[i])
    if len(que) > n:
        v = heappop(que)
        rsum += v
    if len(que) == n:
        right[i] = rsum
ans = -10**18
for i in xrange(3*n):
    if left[i] is not None and right[i+1] is not None:
        ans = max(ans, left[i] - right[i+1])
print ans