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 heapq
n = int(input())
a = list(map(int,input().split()))

first = []
second = []
for i in range(n):
    first.append(a[i])
for i in range(2*n,3*n):
    second.append(-a[i])
heapq.heapify(first)
heapq.heapify(second)


sumfirst = [0]*(n+1)
sumsecond = [0]*(n+1)
sumfirst[0] = sum(first)
sumsecond[n] = -sum(second)

for i in range(1,n+1):
    k = 0
    k += a[n-1+i]
    heapq.heappush(first,a[n-1+i])
    k -= heapq.heappop(first)
    sumfirst[i] = sumfirst[i-1]+k

for i in range(n-1,-1,-1):
    k = 0
    k += a[n+i]
    heapq.heappush(second,-a[n+i])
    k -= -heapq.heappop(second)
    sumsecond[i] = sumsecond[i+1]+k

res = -10**9
for i in range(n+1):
    res = max(res,sumfirst[i]-sumsecond[i])
print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush,heappushpop,heapify

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

q = []
s = 0
for i in range(n):
    heappush(q, a[i])
    s += a[i]
left = [s]
for k in range(n):
    x = heappushpop(q, a[n+k])
    s = s - x + a[n+k]
    left.append(s)

q = []
s = 0
for i in range(n):
    heappush(q, -1*a[3*n-1-i])
    s += a[3*n-1-i]
right = [0 for _ in range(n+1)]
right[n] = s
for k in range(n):
    x = heappushpop(q, -1*a[2*n-1-k])
    s = s - (-1*x) + a[2*n-1-k]
    right[n-1-k] = s

m = -1
for k in range(n+1):
    m = max(m, left[k]-right[k])

print(m)

Submission status: Wrong Answer

Solution code:
import heapq


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

    sum_max, sum_min = [0] * (n+1), [0] * (n+1)
    mx_pq, mn_pq = [], []

    for i in range(n):
        heapq.heappush(mx_pq, a[i])
        heapq.heappush(mn_pq, -a[3*n-i-1])

    sum_max[0], sum_min[n] = sum(mx_pq), -sum(mn_pq)

    for i in range(1, n+1):
        if mx_pq[0] < a[n+i-1]:
            sum_max[i] = sum_max[i-1] + a[n+i-1] - heapq.heappop(mx_pq)
            heapq.heappush(mx_pq, a[n+i-1])
        else:
            sum_max[i] = sum_max[i-1]

        if mn_pq[0] < -a[2*n-i]:
            sum_min[n-i] = sum_min[n-i+1] + a[2*n-i] + heapq.heappop(mn_pq)
            heapq.heappush(mn_pq, -a[2*n-i])
        else:
            sum_min[n-i] = sum_min[n-i+1]

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq


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

    sum_max, sum_min = [0] * n, [0] * n
    mx_pq, mn_pq = [], []

    for i in range(n):
        heapq.heappush(mx_pq, a[i])
        heapq.heappush(mn_pq, -a[3*n-i-1])

    sum_min[n-1] = -sum(mn_pq)

    if mx_pq[0] < a[n]:
        sum_max[0] = sum(mx_pq) + a[n] - heapq.heappop(mx_pq)
        heapq.heappush(mx_pq, a[n])

    for i in range(1, n):
        if mx_pq[0] < a[n+i]:
            sum_max[i] = sum_max[i-1] + a[n+i] - heapq.heappop(mx_pq)
            heapq.heappush(mx_pq, a[n+i])
        else:
            sum_max[i] = sum_max[i-1]

        if mn_pq[0] < a[2*n-i]:
            sum_min[n-i-1] = sum_min[n-i] + a[2*n-i] + heapq.heappop(mn_pq)
            heapq.heappush(mn_pq, -a[2*n-i])
        else:
            sum_min[n-i-1] = sum_min[n-i]

    ans = -10 ** 10
    for i in range(n):
        ans = max(ans, sum_max[i]-sum_min[i])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))

n = int(input())
a = ai()

ans = -float('inf')
for k in range(n):
    af = a[:n+k]
    ar = a[n+k:]
    aa = sum(sorted(af, reverse=True)[:n]) - sum(sorted(ar)[:n])
    ans = max(ans, aa)

print(ans)

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))

n = int(input())
a = ai()

ans = 0
for k in range(n):
    af = a[:n+k]
    ar = a[n+k:]
    aa = sum(sorted(af)[:n]) + sum(sorted(af, reverse=True)[:n])
    ans = max(ans, aa)

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
b=list(map(int,input().split()))
m=0
sd1=[]
sd2=[]
"""
while m <= N:
    #d1=heapq.nlargest(N,b[:2*N-m])
    d1=sorted(b[:2*N-m], reverse=True)[:N]
    #d2=heapq.nsmallest(N,b[2*N-m:])
    d2=sorted(b[2*N-m:])[:N]
    Max.append(sum(d1)-sum(d2))
    m+=1
"""
d1=b[:N]
sd1.append(sum(d1))
d2=b[2*N:]
sd2.append(sum(d2))
Max=sum(d1)-sum(d2)
while m<N:
    if min(d1) < b[N+m]:
        d1.remove((min(d1)))
        d1.append(b[N+m])
    if max(d2) > b[2*N-m]:
        d2.remove((max(d2)))
        d2.append(b[2*N-m])

    sd1.append(sd1[m]-min(d1)+b[N+m])
    sd2.append(sd2[m]-max(d2)+b[2*N-m])
    if Max < (sd1[m+1]-sd2[m+1]):
            Max=sum(d1)-sum(d2)
    m+=1

print(Max)

Submission status: Wrong Answer

Solution code:
N=int(input())
b=list(map(int,input().split()))
Max=[]
m=0
d1=b[:N]
d2=b[2*N:]
Max.append(sum(d1)-sum(d2))
while m<N:
    if min(d1) < b[N+m]:
        d1.remove((min(d1)))
        d1.append(b[N+m])
        d2=sorted(b[N+m+1:])[:N]
        Max.append(sum(d1)-sum(d2))
    m+=1

print(max(Max))

Submission status: Wrong Answer

Solution code:
import heapq

N=int(input())
a=input().split()
n=0
b=[]
Max=[]
while n < 3*N:
    b.append(int(a[n]))
    n+=1

m=0
while m <= N:
    d1=heapq.nlargest(N,b[:2*N-n])
    d2=heapq.nsmallest(N,b[2*N-n:])
    Max.append(sum(d1)-sum(d2))
    m+=1

print(max(Max))

Submission status: Wrong Answer

Solution code:
import heapq
import bisect

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

left = a[0:n//3]
right = list(-i for i in a[2*n//3:])

leftsum = [0 for i in range(n//3+1)]
rightsum = [0 for i in range(n//3+1)]

heapq.heapify(left)
leftsum[0] = sum(left)
for i in range(n//3):
    k = i + n//3
    heapq.heappush(left,a[k])
    temp = heapq.heappop(left)
    leftsum[i+1] = leftsum[i]+a[k]-temp

heapq.heapify(right)
rightsum[-1] = -sum(right)
for i in range(n//3)[::-1]:
    k = i + n//3
    heapq.heappush(right,-a[k])
    temp = -heapq.heappop(right)
    rightsum[i] = rightsum[i+1] - temp + a[k]

mxm = -sum(a)
for i in range(n//3):
    if leftsum[i]-rightsum[i] > mxm:
        mxm = leftsum[i]-rightsum[i]
print(mxm)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [long(input_raw[0])]
    A_list = []
    input_raw = read_func().strip().split()
    for i in range(3* N):
        A_list.append(long(input_raw[i]))

    AL_list = A_list[:N]
    L_sum = [0 for i in range(N + 1)]
    L_sum[0] = sum(AL_list)
    heapq.heapify(AL_list)
    for i in range(N, 2 * N):
        if AL_list[0] < A_list[i]:
            heapq.heappush(AL_list, A_list[i])
            min_L = heapq.heappop(AL_list)
            L_sum[i + 1- N] = L_sum[i - N] - min_L + A_list[i]
        else:
            L_sum[i + 1- N] = L_sum[i - N]

    AR_list = [-A_list[i] for i in range(2 * N, 3 * N)]
    R_sum = [0 for i in range(N + 1)]
    R_sum[N] = sum(AR_list)
    heapq.heapify(AR_list)
    for i in range(2 * N - 1, N - 1, -1):
        if AR_list[0] < -A_list[i]:
            heapq.heappush(AR_list, -A_list[i])
            min_R = heapq.heappop(AR_list)
            R_sum[i - N] = R_sum[i - N + 1] - min_R + (-A_list[i])
        else:
            R_sum[i - N] = R_sum[i - N + 1]

    max_score = -long(sys.maxint * sys.maxint)
    for i in range(N):
        max_score = max(max_score, L_sum[i] + R_sum[i])


##    for i in range(N + 1):
##        if i == 0:
##            AL_list = A_list[:N + i]
##            AR_list = A_list[N + i:]
##            AL_list = sorted(AL_list, reverse=True)
##            AR_list = sorted(AR_list)
##            L_sum = sum(AL_list[:N])
##            R_sum = sum(AR_list[:N])
##            max_score = max(max_score, (L_sum - R_sum))
##            L_min = AL_list[0]
##            R_min = AR_list[0]
##        else:
##            A = A_list[N + i]
##            if L_min < A:
##                L_index += 1
##                L_sum = (L_sum - L_min) + A
##                L_min(AL_list[L_index])
##            if R_max > A:
##                R_sum = R_sum - A +

    print max_score


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [long(input_raw[0])]
    A_list = []
    input_raw = read_func().strip().split()
    for i in range(3* N):
        A_list.append(long(input_raw[i]))

    max_score = -sys.maxint
    L_min = sys.maxint
    R_max = -sys.maxint

    AL_list = A_list[:N]
    L_sum = [0 for i in range(N + 1)]
    L_sum[0] = sum(AL_list)
    heapq.heapify(AL_list)
    for i in range(N, 2 * N):
        if AL_list[0] < A_list[i]:
            heapq.heappush(AL_list, A_list[i])
            min_L = heapq.heappop(AL_list)
            L_sum[i + 1- N] = L_sum[i - N] - min_L + A_list[i]
        else:
            L_sum[i + 1- N] = L_sum[i - N]

    AR_list = [-A_list[i] for i in range(2 * N, 3 * N)]
    R_sum = [0 for i in range(N + 1)]
    R_sum[N] = sum(AR_list)
    heapq.heapify(AR_list)
    for i in range(2 * N - 1, N - 1, -1):
        if AR_list[0] < -A_list[i]:
            heapq.heappush(AR_list, -A_list[i])
            min_R = heapq.heappop(AR_list)
            R_sum[i - N] = R_sum[i - N + 1] - min_R + (-A_list[i])
        else:
            R_sum[i - N] = R_sum[i - N + 1]

    max_score = -(sys.maxint * sys.maxint)
    for i in range(N):
        max_score = max(max_score, L_sum[i] + R_sum[i])


##    for i in range(N + 1):
##        if i == 0:
##            AL_list = A_list[:N + i]
##            AR_list = A_list[N + i:]
##            AL_list = sorted(AL_list, reverse=True)
##            AR_list = sorted(AR_list)
##            L_sum = sum(AL_list[:N])
##            R_sum = sum(AR_list[:N])
##            max_score = max(max_score, (L_sum - R_sum))
##            L_min = AL_list[0]
##            R_min = AR_list[0]
##        else:
##            A = A_list[N + i]
##            if L_min < A:
##                L_index += 1
##                L_sum = (L_sum - L_min) + A
##                L_min(AL_list[L_index])
##            if R_max > A:
##                R_sum = R_sum - A +

    print max_score


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [long(input_raw[0])]
    A_list = []
    input_raw = read_func().strip().split()
    for i in range(3* N):
        A_list.append(long(input_raw[i]))

    max_score = -sys.maxint
    L_min = sys.maxint
    R_max = -sys.maxint

    AL_list = A_list[:N]
    L_sum = [0 for i in range(N + 1)]
    L_sum[0] = sum(AL_list)
    heapq.heapify(AL_list)
    for i in range(N, 2 * N):
        if AL_list[0] < A_list[i]:
            heapq.heappush(AL_list, A_list[i])
            min_L = heapq.heappop(AL_list)
            L_sum[i + 1- N] = L_sum[i - N] - min_L + A_list[i]
        else:
            L_sum[i + 1- N] = L_sum[i - N]

    AR_list = [-A_list[i] for i in range(2 * N, 3 * N)]
    R_sum = [0 for i in range(N + 1)]
    R_sum[N] = sum(AR_list)
    heapq.heapify(AR_list)
    for i in range(2 * N - 1, N - 1, -1):
        if AR_list[0] < -A_list[i]:
            heapq.heappush(AR_list, -A_list[i])
            min_R = heapq.heappop(AR_list)
            R_sum[i - N] = R_sum[i - N + 1] - min_R + (-A_list[i])
        else:
            R_sum[i - N] = R_sum[i - N + 1]

    max_score = -sys.maxint
    for i in range(N):
        max_score = max(max_score, L_sum[i] + R_sum[i])


##    for i in range(N + 1):
##        if i == 0:
##            AL_list = A_list[:N + i]
##            AR_list = A_list[N + i:]
##            AL_list = sorted(AL_list, reverse=True)
##            AR_list = sorted(AR_list)
##            L_sum = sum(AL_list[:N])
##            R_sum = sum(AR_list[:N])
##            max_score = max(max_score, (L_sum - R_sum))
##            L_min = AL_list[0]
##            R_min = AR_list[0]
##        else:
##            A = A_list[N + i]
##            if L_min < A:
##                L_index += 1
##                L_sum = (L_sum - L_min) + A
##                L_min(AL_list[L_index])
##            if R_max > A:
##                R_sum = R_sum - A +

    print max_score


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

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

first_q = a_li[0:N] # 前半部分
last_q = []			# 後半部分

first_ans = sum(first_q)
last_ans = 0

for i in range(2*N,3*N):	#最大値を取るために[-x,x]のタプルでlist
	last_q.append([-a_li[i],a_li[i]])
	last_ans += a_li[i]
	
# 優先度付きキューの作成
heapq.heapify(first_q)
heapq.heapify(last_q)
 
first_ans_li = []
last_ans_li = []

first_ans_li.append(first_ans)
last_ans_li.append(last_ans)


for k in range(N,2*N): # k:区切り位置
	pop = heapq.heappushpop(first_q,a_li[k])	# push + 最小値のpop
	push = a_li[k]
	first_ans = first_ans + push - pop
	first_ans_li.append(first_ans)
	

for k in range(2*N-1,N-1,-1): # k:区切り位置
	pop = heapq.heappushpop(last_q,[-a_li[k],a_li[k]])[1] # push + 最大値のpop
	push = a_li[k]
	last_ans = last_ans + push - pop
	last_ans_li.append(last_ans)

ans = -1000000000
	
for i in range(0,N+1):
	ans_dush = first_ans_li[i] - last_ans_li[N-i]
	ans = max(ans,ans_dush)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


class Node:
    def __init__(self, val, l, r):
        self.val = val
        self.l = l
        self.r = r

    def min(self):
        if self.l is None:
            return self.val
        else:
            return self.l.min()

    def max(self):
        if self.r is None:
            return self.val
        else:
            return self.r.max()

    def popmin(self):
        if self.l is None:
            return self.r
        return Node(self.val, self.l.popmin(), self.r)

    def popmax(self):
        if self.r is None:
            return self.l
        return Node(self.val, self.l, self.r.popmax())

    def insert(self, x):
        if x < self.val:
            if self.l is None:
                return Node(self.val, Node(x, None, None), self.r)
            else:
                return Node(self.val, self.l.insert(x), self.r)
        else:
            if self.r is None:
                return Node(self.val, self.l, Node(x, None, None))
            else:
                return Node(self.val, self.l, self.r.insert(x))

    def sum(self):
        if self.l is None and self.r is None:
            return self.val
        if self.l is None:
            return self.val + self.r.sum()
        if self.r is None:
            return self.val + self.l.sum()
        return self.val + self.l.sum() + self.r.sum()

def make(list_):
    if len(list_) == 0:
        raise Exception("none")
    elif len(list_) == 1:
        return Node(list_[0], None, None)
    else:
        return make(list_[:-1]).insert(list_[-1])

#
if __name__ == '__main__':
    N = int(input())
    a = list(map(int, input().split()))

    if N == 1:
        print(max(a[0]-a[1], a[0]-a[2], a[1]-a[2]))
        exit()

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

    i = N
    j = 2*N-1

    for k in range(N):
        leftmin = left.min()
        rightmax = right.max()
        if leftmin < a[i]:
            if a[j] < rightmax:
                if (a[i]-leftmin) < (rightmax-a[j]):
                    right = right.popmax()
                    right = right.insert(a[j])
                    j -= 1
                else:
                    left = left.popmin()
                    left = left.insert(a[i])
                    i += 1
            else:
                left = left.popmin()
                left = left.insert(a[i])
                i += 1
        else:
            if a[j] < rightmax:
                right = right.popmax()
                right = right.insert(a[j])
                j -= 1
            else:
                if (leftmin-a[i]) < (a[j]-rightmax):
                    left = left.popmin()
                    left = left.insert(a[i])
                    i += 1
                else:
                    right = right.popmax()
                    right = right.insert(a[j])
                    j -= 1

    print(left.sum()-right.sum())

Submission status: Wrong Answer

Solution code:
import numpy as np
import queue


def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def next_pair(lst):
    n = len(lst)
    for i in range(n-1):
        yield lst[i], lst[i+1]


import bisect

def main():
    N = ii()
    a = lii()

    INF = 1e5

    q = []
    score = [-INF for _ in range(3 * N)]
    sum = 0
    for n in range(0, 2*N+1):
        bisect.insort(q, a[n])
        sum += a[n]
        if len(q) > N:
            sum -= q.pop(0)
        score[n] = sum

    q = []
    sum = 0
    for n in reversed(range(N, 3*N)):
        bisect.insort(q, a[n])
        sum += a[n]
        if len(q) > N:
            sum -= q.pop()
        score[n-1] -= sum

    print(max(score[N:2*N]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

max_result = -1000000

for k in range(N, 2*N+1):
  big_a = a[:k]
  heapq.heapify(big_a)
  small_a =[(-x, x) for x in a[k:]]
  heapq.heapify(small_a)

  for i in range(len(big_a) - N):
    heapq.heappop(big_a)

  for i in range(len(small_a) - N):
    heapq.heappop(small_a)

  big_sum = sum(big_a)
  small_sum = 0
  for i in small_a:
    small_sum += i[1]

  if (big_sum - small_sum) > max_result:
    max_result = big_sum - small_sum

print(max_result)

Submission status: Wrong Answer

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

max_result = -1000000

for k in range(N, 2*N+1):
  print("----------------")
  big_a = a[:k]
  heapq.heapify(big_a)
  print(big_a)
  small_a =[(-x, x) for x in a[k:]]
  heapq.heapify(small_a)
  print(small_a)

  for i in range(len(big_a) - N):
    heapq.heappop(big_a)
  print(big_a)

  for i in range(len(small_a) - N):
    heapq.heappop(small_a)
  print(small_a)

  big_sum = sum(big_a)
  small_sum = 0
  for i in small_a:
    small_sum += i[1]

  if (big_sum - small_sum) > max_result:
    max_result = big_sum - small_sum

print(max_result)

Submission status: Wrong Answer

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

max_result = 0

for k in range(N, 2*N+1):
  big_a = a[:k]
  heapq.heapify(big_a)
  small_a =[(-x, x) for x in a[k:]]
  heapq.heapify(small_a)

  for i in range(len(big_a) - N):
    heapq.heappop(big_a)

  for i in range(len(small_a) - N):
    heapq.heappop(small_a)

  big_sum = sum(big_a)
  small_sum = 0
  for i in small_a:
    small_sum += i[1]

  if (big_sum - small_sum) > max_result:
    max_result = big_sum - small_sum

print(max_result)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

s_minus = [-i for i in second]
t_minus = [-i for i in third]

former = [sum(first)]
latter = [sum(t_minus)]

heapq.heapify(first)
for k in range(n):
	heapq.heappush(first, second[k])
	former.append(former[-1] + second[k] - heapq.heappop(first))

heapq.heapify(t_minus)
for k in range(n):
	heapq.heappush(t_minus, s_minus[-(k + 1)])
	latter.append(latter[-1] + s_minus[-(k + 1)] - heapq.heappop(t_minus))

new_latter = [latter[-(i + 1)] for i in range(n)]

ans = -5000000000000000000000000000000
for f, l in zip(former, new_latter):
	if f + l >= ans:
		ans = f + l

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

s_minus = [-i for i in second]
t_minus = [-i for i in third]

former = [sum(first)]
latter = [sum(t_minus)]

heapq.heapify(first)
for k in range(n):
	heapq.heappush(first, second[k])
	former.append(former[-1] + second[k] - heapq.heappop(first))

heapq.heapify(t_minus)
for k in range(n):
	heapq.heappush(t_minus, s_minus[-(k + 1)])
	latter.append(latter[-1] + s_minus[-(k + 1)] - heapq.heappop(t_minus))

new_latter = [latter[-(i + 1)] for i in range(n)]

ans = -5000000000000
for f, l in zip(former, new_latter):
	if f + l >= ans:
		ans = f + l

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
from bisect import bisect_left, insort
N = int(input())
A = inpl()

before = sorted(A[:N])
middle = sorted(A[N:-N])
after = sorted(A[-N:])

S_before = [sum(before)]
S_after = [sum(after)]

for m in middle:
    if before[0] < m:
        S_before.append(S_before[-1] + m - before[0])
        insort(before, m)
        before = before[1:]
    else:
        S_before.append(S_before[-1])

for m in middle[::-1]:
    if after[-1] > m:
        S_after.append(S_after[-1] - m + after[-1])
        insort(after, m)
        after = after[:-1]
    else:
        S_after.append(S_after[-1])    

print(max([b-a for b, a in zip(S_before, S_after[::-1])]))

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [int(i) for i in input().split()]
arr[0:n] = sorted(arr[0:n])
arr[2 * n : 3 * n] = sorted(arr[2 * n: 3 * n])
s1 = sum(arr[0:n])
s2 = sum(arr[2*n:3*n])
i = 0
j = 3 * n - 1
l = n
r = 2 * n - 1
for _ in range(n):
    if(arr[l] - arr[i] > arr[j] - arr[r]):
        s1 += arr[l] - arr[i]
        i += 1
        l += 1
    else:
        s2 -= arr[j] - arr[r]
        j -= 1
        r -= 1
print(s1 - s2)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**9
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    b = []
    c = []
    for i in range(n):
        heapq.heappush(b, a[i])
        heapq.heappush(c, -a[i+n*2])
    sb = sum(b)
    sc = sum(c)
    ba = {}
    ba[n-1] = sb
    for i in range(n):
        t = heapq.heappop(b)
        sb -= t
        heapq.heappush(b, a[n+i])
        sb += a[n+i]
        ba[n+i] = sb

    ca = {}
    ca[n*2-1] = sc
    for i in range(n-1,-1,-1):
        t = heapq.heappop(c)
        sc -= t
        heapq.heappush(c, -a[n+i])
        sc -= a[n+i]
        ca[n+i-1] = sc

    r = -inf
    for k in ba.keys():
        tr = ba[k] + ca[k]
        if tr > r:
            r = tr

    return r



print(main())

Submission status: Wrong Answer

Solution code:
import sys, heapq

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = na()

ln = a[0:n]
rn = [-x for x in a[2*n: 3*n]]
heapq.heapify(ln)
heapq.heapify(rn)
ls = sum(ln)
rs = sum(rn)

lb = [ls]
rb = [rs]
for i in range(1, n+1):
    vl = heapq.heappop(ln)
    heapq.heappush(ln, a[n-1+i])
    ls = ls - vl + a[n-1+i]
    lb.append(ls)

    vr = heapq.heappop(rn)
    heapq.heappush(rn, -a[2*n-i])
    rs = rs - vr - a[2*n-i]
    rb.append(rs)

ans = -float('inf')
for i in range(n+1):
    ans = max(ans, lb[i] + rb[n-i])

print (ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
n2 = 2*n
n3 = 3*n
ai = [int(i) for i in input().split()]
head = 0
tail = 0
for i in range(n):
    head += ai[i]
    tail += ai[n3 - 1 - i]
ret = head - tail

head_a = sorted(ai[0:n])
tail_a = sorted(ai[n2:n3])
tail_a.reverse()
# print(head_a, tail_a, ai)
bs = [0]
right = n
cs = [0]
left = n2 - 1
for i in range(n):
    if(head_a[i] < ai[right]):
        bs.append(ai[right] - head_a[i] + bs[len(bs) - 1])
        right += 1
    if(tail_a[i] > ai[left]):
        cs.append(tail_a[i] - ai[left] + cs[len(cs) - 1])
        left -= 1
# print(bs, cs)


if(len(bs) + len(cs) <= n + 2):
    print(ret + bs[len(bs) - 1] + cs[len(cs) - 1])
else:
    ndiff = (len(bs) + len(cs)) - n - 2
    diffmax = 0
    for i in range(ndiff+1):
        if(diffmax < (bs[len(bs) - 1 - i] + cs[len(cs) - 1 - ndiff + i])):
            diffmax = bs[len(bs) - 1 - i] + cs[len(cs) - 1 - ndiff + i]
    print(ret + diffmax)

Submission status: Wrong Answer

Solution code:
n = int(input())
n2 = 2*n
n3 = 3*n
ai = [int(i) for i in input().split()]
head = 0
tail = 0
for i in range(n):
    head += ai[i]
    tail += ai[n3 - 1 - i]
ret = head - tail

head_a = sorted(ai[0:n])
tail_a = sorted(ai[n2:n3])
tail_a.reverse()
print(head_a, tail_a, ai)
bs = [0]
right = n
cs = [0]
left = n2 - 1
for i in range(n):
    if(head_a[i] < ai[right]):
        bs.append(ai[right] - head_a[i] + bs[len(bs) - 1])
        right += 1
    if(tail_a[i] > ai[left]):
        cs.append(tail_a[i] - ai[left] + cs[len(cs) - 1])
        left -= 1
print(bs, cs)


if(len(bs) + len(cs) <= n + 2):
    print(ret + bs[len(bs) - 1] + cs[len(cs) - 1])
else:
    ndiff = (len(bs) + len(cs)) - n - 2
    diffmax = 0
    for i in range(ndiff+1):
        if(diffmax < (bs[len(bs) - 1 - i] + cs[len(cs) - 1 - ndiff + i])):
            diffmax = bs[len(bs) - 1 - i] + cs[len(cs) - 1 - ndiff + i]
    print(ret + diffmax)

Submission status: Wrong Answer

Solution code:
import heapq as hq
n = int(raw_input())
aa = map(int, raw_input().split())

am = aa[n:2*n]
reversed_am = am[::-1]
sum_al = sum(aa[:n])
sum_ar = sum(aa[2*n:])

al = []
ar = []
for i in range(n):
  hq.heappush(al, aa[i])
  hq.heappush(ar, -aa[2*n+i])

sum_als = [sum_al]
sum_ars = [sum_ar]

for i in range(n):
  ami = am[i]
  sum_al += ami

  hq.heappush(al, ami)
  sum_al -= hq.heappop(al)

  sum_als.append(sum_al)

for i in range(n):
  ami = reversed_am[i]
  sum_ar += ami

  hq.heappush(ar, ami)
  sum_ar -= (-hq.heappop(ar))

  sum_ars.append(sum_ar)

ans = -float('inf')
for sum_al,sum_ar in zip(sum_als, sum_ars[::-1]):
  ans = max(ans, sum_al - sum_ar)

print ans

Submission status: Wrong Answer

Solution code:
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 = 0
    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


# sys.stdin = open('d1.in')
n = int(input())
a = list(map(int, input().split()))
print(solve_large(n, a))

Submission status: Wrong Answer

Solution code:
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])
    ta1+=heapq.heappop(hp1)
    ta2+=-heapq.heappop(hp2)
    #print hp1,hp2
#print p,b
for i in xrange(n+1):
    ans=max(ans,p[i]-b[n-i])
print ans

Submission status: Wrong Answer

Solution code:
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)

# li = n
# ri = 2*n-1
# score = sum(a[0: n]) - sum(a[2*n: 3*n])
al = sorted(a[0: n], reverse=True)
ar = sorted(a[2*n: 3*n])
scorem = [0]
for i in range(n):
    scorem.append(scorem[i] + a[n+i])
scorel = [scorem[n]]
scorer = [scorem[n]]
for i in range(n):
    scorel.append(scorel[i] + al[i] - a[2*n-1-i])
    scorer.append(scorer[i] + ar[i] - a[n+i])
# print(scorel)
# print(scorer)
# print(scorem)
max_score = -float('inf')
for i in range(n+1):
    for j in range(n-i, n+1):
        if not 0 <= i+j <= n:
            continue
        max_score = max(max_score, scorel[i] - scorer[j])
        # print(i, j, max_score, scorel[i] , scorer[j])


print(max_score)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
B = []
for i in range(n,2*n):
	A1 = A[:i]
	A2 = A[i:]
	a1 = i - n
	a2 = 2*n - i
	A1.sort()
	A1 = A1[a1:]
	A2.sort()
	A2 = A2[:-a2]
	#print(A1,A2)
	B.append(sum(A1) - sum(A2))
	

#print(B)
print(max(B))