Problem p03716 (python)

Fixed submission:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    a = ILI()
    return (N, a)


def solve(N, a):
    a_lef = a[0: N]
    a_rig = [-i for i in a[2 * N: 3 * N]]
    heapq.heapify(a_lef)
    heapq.heapify(a_rig)
    sum_lef = sum(a_lef)
    sum_rig = sum(a_rig)
    l_sum_lef = [sum_lef]
    l_sum_rig = [sum_rig]
    
    for i in range(1, N + 1):
        heapq.heappush(a_lef, a[N - 1 + i])
        lef_pop = heapq.heappop(a_lef)
        sum_lef += a[N - 1 + i] - lef_pop
        l_sum_lef.append(sum_lef)
        
        heapq.heappush(a_rig, -a[2 * N - i])
        rig_pop = heapq.heappop(a_rig)
        sum_rig += -a[2 * N - i] - rig_pop
        l_sum_rig.append(sum_rig)

    ans = -INF

    for i in range(N + 1):
        num_dif = l_sum_lef[i] + l_sum_rig[N - i]
        ans = max(ans, num_dif)

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    a = ILI()
    return (N, a)


def solve(N, a):
    a_lef = a[0:N]
    heapq.heapify(a_lef)
    sum_lef = sum(a_lef)
    l_sum_lef = [sum_lef]

    for i in range(N, 2 * N):
        sum_lef += a[i]
        heapq.heappush(a_lef, a[i])
        num_pop = heapq.heappop(a_lef)
        sum_lef -= num_pop
        l_sum_lef.append(sum_lef)

    a_rig = a[2 * N:3 * N]
    heapq._heapify_max(a_rig)
    sum_rig = sum(a_rig)
    l_sum_rig = [sum_rig]

    for i in range(2 * N - 1, N - 1, -1):
        if a[i] >= a_rig[0]:
            l_sum_rig.append(sum_rig)
        else:
            sum_rig += a[i]
            num_pop = heapq._heapreplace_max(a_rig, a[i])
            sum_rig -= num_pop
            l_sum_rig.append(sum_rig)

    ans = INF * -1

    for i in range(N + 1):
        num_dif = l_sum_lef[i] - l_sum_rig[N - i]
        ans = max(ans, num_dif)

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    a = ILI()
    return (N, a)


def solve(N, a):
    a_lef = a[0:N]
    heapq.heapify(a_lef)
    sum_lef = sum(a_lef)
    l_sum_lef = [sum_lef]

    for i in range(N, 2 * N):
        sum_lef += a[i]
        heapq.heappush(a_lef, a[i])
        num_pop = heapq.heappop(a_lef)
        sum_lef -= num_pop
        l_sum_lef.append(sum_lef)

    a_rig = a[2 * N:3 * N]
    heapq._heapify_max(a_rig)
    sum_rig = sum(a_rig)
    l_sum_rig = [sum_rig]

    for i in range(2 * N - 1, N - 1, -1):
        if a[i] >= a_rig[0]:
            l_sum_rig.append(sum_rig)
        else:
            sum_rig += a[i]
            num_pop = heapq._heapreplace_max(a_rig, a[i])
            sum_rig -= num_pop
            l_sum_rig.append(sum_rig)

    ans = INF * -1

    for i in range(N + 1):
        num_dif = l_sum_lef[i] - l_sum_rig[N - i]
        ans = max(ans, num_dif)

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    a = ILI()
    return (N, a)

def solve(N, a):
    a_lef = a[0:N]
    a_mid = a[N:2 * N]
    a_rig = a[2 * N : 3 * N]
    heapq.heapify(a_lef)
    heapq._heapify_max(a_rig)

    i_lef = 0
    i_rig = N - 1

    for __ in range(N):
        n_lef = a_lef[0] * -1 + a_mid[i_lef]
        n_rig = a_rig[0] - a_mid[i_rig]
        if n_lef >= n_rig:
            heapq.heappop(a_lef)
            heapq.heappush(a_lef, a_mid[i_lef])
            i_lef += 1
        else:
            heapq._heapreplace_max(a_rig, a_mid[i_rig])
            i_rig -= 1

    ans = sum(a_lef) - sum(a_rig)
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    a = ILI()
    return (N, a)

def solve(N, a):
    a_lef = a[0:N]
    a_mid = a[N:2 * N]
    a_rig = a[2 * N : 3 * N]
    heapq.heapify(a_lef)
    heapq._heapify_max(a_rig)

    i_lef = 0
    i_rig = N - 1

    for __ in range(N):
        n_lef = a_lef[0] * -1 + a_mid[i_lef]
        n_rig = a_rig[0] - a_mid[i_rig]
        if n_lef >= n_rig:
            heapq.heappop(a_lef)
            heapq.heappush(a_lef, a_mid[i_lef])
            i_lef += 1
        else:
            heapq._heapreplace_max(a_rig, a_mid[i_rig])
            i_rig -= 1

    ans = sum(a_lef) - sum(a_rig)
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()