Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
# 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()


# 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():
    H, W = ILI()
    return (H, W)

def solve(H, W):
    ans = INF
    
    if H % 3 == 0 or W % 3 == 0:
        return 0
    else:
        ans = min(ans, H, W)

    if W % 2 == 0:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * W // 2
            ans = min(ans, abs(num_1 - num_2))
    else:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * (W // 2)
            num_3 = (H - h) * (W // 2 + 1)
            nums = sorted([num_1, num_2, num_3])
            ans = min(ans, (nums[2] - nums[0]))

    if H % 2 == 0:
        for w in range(1, W):
            num_1 = w * H
            num_2 = (W - w) * H // 2
            ans = min(ans, abs(num_1 - num_2))
    else:
        for w in range(1, W):
            num_1 = w * H
            num_2 = (W - w) * (H // 2)
            num_3 = (W - w) * (H // 2 + 1)
            nums = sorted([num_1, num_2, num_3])
            ans = min(ans, (nums[2] - nums[0]))
    
    return ans


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


if __name__ == "__main__":
    main()


Verdicts: Runtime Error

Accepted