Problem:


Score : 400 points

Problem Statement

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}.

Constraints

2 ≤ H, W ≤ 10^5

Input

Input is given from Standard Input in the following format:

H W

Output

Print the minimum possible value of S_{max} - S_{min}.

Sample Input 1

3 5

Sample Output 1

0

In the division below, S_{max} - S_{min} = 5 - 5 = 0.

Sample Input 2

4 5

Sample Output 2

2

In the division below, S_{max} - S_{min} = 8 - 6 = 2.

Sample Input 3

5 5

Sample Output 3

4

In the division below, S_{max} - S_{min} = 10 - 6 = 4.

Sample Input 4

100000 2

Sample Output 4

1

Sample Input 5

100000 100000

Sample Output 5

50000



Sample input:
3 5


Sample output:
0

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

def bi(h, w):
    s = h * w
    if h % 2 == 0 or w % 2 == 0:
        s0 = h * w // 2
    else:
        s0 = (max(h, w) + 1) // 2 * min(h, w)
    return [s0, s - s0]

ans = h * w
for i in range(1, h):
    arr = bi(h - i, w)
    arr.append(w * i)
    ans = min(ans, max(arr) - min(arr))

for i in range(1, w):
    arr = bi(h, w - i)
    arr.append(h * i)
    ans = min(ans, max(arr) - min(arr))

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
can = []
if h%3 == 0 or w%3 == 0:
    can.append(0)
if h > 3:
    can.append(w)
if w > 3:
    can.append(h)

for a in range(w//3, w//2+1):
    size = [h * a]
    if h%2 == 0:
        size.append(h//2 * (w-a))
        size.append(h//2 * (w-a))
    else:
        size.append(h//2 * (w-a))
        size.append((h//2 + 1) * (w-a))
    can.append(max(size) - min(size))

for a in range(h//3, h//2+1):
    size = [w * a]
    if w%2 == 0:
        size.append(w//2 * (h-a))
        size.append(w//2 * (h-a))
    else:
        size.append(w//2 * (h-a))
        size.append((w//2 + 1) * (h-a))
    can.append(max(size) - min(size))
print(min(can))

Submission status: Accepted

Solution code:
h, w = map(int, raw_input().split())
if h % 3 == 0 or w % 3 == 0:
    print 0
else:
    ans = min(w, h)
    for x in xrange(1, w):
        A = x * h
        B = (h / 2) * (w - x)
        C = w*h - A - B
        result = max(A, B, C) - min(A, B, C)
        ans = min(ans, result)
    for y in xrange(1, h):
        A = y * w
        B = (w / 2) * (h - y)
        C = w*h - A - B
        result = max(A, B, C) - min(A, B, C)
        ans = min(ans, result)
    print ans

Submission status: Accepted

Solution code:
H,W = map(int, raw_input().split())
ans = 10**10

s = [0]*3
for i in range(1,H):
    s[0] = i*W
    s[1] = (H-i)*(W/2)
    s[2] = (H-i)*((W+1)/2)
    s.sort()
    ans = min(ans, s[2]-s[0])

for i in range(1,W):
    s[0] = i*H
    s[1] = (W-i)*(H/2)
    s[2] = (W-i)*((H+1)/2)
    s.sort()
    ans = min(ans, s[2]-s[0])

if H>=3:
    ans = min(ans, 0 if H%3==0 else W)

if W>=3:
    ans = min(ans, 0 if W%3==0 else H)

print ans

Submission status: Accepted

Solution code:
H, W = map(int, input().split())

def fun(H, W):
    ans = 1e20
    for w in range(1, W):
        w_a = (W - w) // 2
        w_b = W - w - w_a
        S1 = H * w
        ans = min(ans, max(S1, H * w_a, H * w_b) - min(S1, H * w_a, H * w_b))

        h_a = H // 2
        h_b = H - h_a
        S2 = h_a * (W - w)
        S3 = h_b * (W - w)
        ans = min(ans, max(S1, S2, S3) - min(S1, S2, S3))
    return ans

print(min(fun(H, W), fun(W, H)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def f(H, W):
    mh = H // 2
    mw = W // 2
    return (mh*W, (H-mh)*W), (H*mw, H*(W-mw))

def solve_iter(H: int, W: int):
    for h in range(1, H):
        for s in ((h*W,*s) for s in f(H-h, W)):
            yield max(s) - min(s)
    for w in range(1, W):
        for s in ((H*w,*s) for s in f(H, W-w)):
            yield max(s) - min(s)

def solve(H: int, W: int):
    return min(solve_iter(H, W))


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    print(solve(H, W))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Runtime Error

Solution code:
import math
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

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

#################################################
#################################################
#################################################
#################################################



#28-

n,m= list(map(int, input().split()))
ans = 10**9

for i in range(1,n):
    s1 = m*i
    s2 = (n-i)*(m//2)
    s3 = (n-i)*m - s2
    ans = min(ans,max(s1,s2,s3)-min(s1,s2,s3))
n,m = m,n
for i in range(1,n):
    s1 = m*i
    s2 = (n-i)*(m//2)
    s3 = (n-i)*m - s2
    ans = min(ans,max(s1,s2,s3)-min(s1,s2,s3))

if(n//3==0 or m//3==0):
    ans = 0
else:
    ans = min(ans,n,m)
    
print(ans)





















































































import math
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

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

#################################################
#################################################
#################################################
#################################################



#28-

n,m= list(map(int, input().split()))
ans = 10**9

for i in range(1,n):
    s1 = m*i
    s2 = (n-i)*(m//2)
    s3 = (n-i)*m - s2
    ans = min(ans,max(s1,s2,s3)-min(s1,s2,s3))
n,m = m,n
for i in range(1,n):
    s1 = m*i
    s2 = (n-i)*(m//2)
    s3 = (n-i)*m - s2
    ans = min(ans,max(s1,s2,s3)-min(s1,s2,s3))

if(n%3==0 or m%3==0):
    ans = 0
else:
    ans = min(ans,n,m)
    
print(ans)

Submission status: Runtime Error

Solution code:
    def main():
        import sys
        input = sys.stdin.readline
        a, b = map(int, input().split())
        if a % 3 == 0 or b % 3 == 0:
            print(0)
            sys.exit()
        if a > b:
            a, b = b, a

        x = (b // 3) * a
        bb = b - b//3
        aa = a
        if aa % 2 == 0 or bb % 2 == 0:
            y = (bb * aa) // 2
            li = sorted([x,y,y])
        else:
            if aa > bb:
                aa, bb = bb, aa
            y = aa * (bb//2)
            z = aa * ((bb+1)//2)
            li = sorted([x, y, z])
        ans = li[2] - li[0]

        x = (b // 3 + 1) * a
        bb = b - b//3 - 1
        aa = a
        if aa % 2 == 0 or bb % 2 == 0:
            y = (aa*bb)//2
            li = sorted([x,y,y])
        else:
            if aa > bb:
                aa, bb = bb, aa
            y = aa * (bb//2)
            y = aa * (bb//2)
            z = aa * ((bb+1)//2)
            li = sorted([x, y, z])
        ans = min(ans, li[2] - li[0])
        print(ans)


    if __name__ == '__main__':
        main()

Submission status: Runtime Error

Solution code:
import heapq
n=int(input())
a=list(map(int,input().split()))
q=a[0:n]
sums=[0]*(n+1)
sums[0]=sum(q)
heapq.heapify(q)
am=a[n:2*n]
for i in range(0,n):
    heapq.heappush(q,am[i])
    heapq.heappop(q)
    sums[i+1]=sum(q)
p=a[2*n:3*n]
p=list(map(lambda x: x*(-1),p))
sums[n]+=sum(p)
heapq.heapify(p)
for i in range(n-1,-1,-1):
    heapq.heappush(p,(-1)*am[i])
    heapq.heappop(p)
    sums[i]+=sum(p)
print(max(sums))

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
t = list(map(int, input().split()))

o = T
for i, j in zip(t, t[1:]):
  o += min(j-i, T)
print(o)

Submission status: Runtime Error

Solution code:
def solve(h, w):
    if h % 3 == 0 or w % 3 == 0:
        return 0
    if h == 1 or w == 1:
        return 1
    min_diff = h * w
    vals = [0, 0, 0]
    def f(a, b):
        for i in range(1, a // 2 + 1):
            vals[0] = i * b
            vals[1] = (a - i) * (b // 2 + b % 2)
            vals[2] = (a - i) * (b // 2)
            diff = max(vals) - min(vals)
            if diff < min_diff:
                min_diff = diff
            vals[1] = b * ((a - i) // 2 + (a - i) % 2)
            vals[2] = b * ((a - i) // 2)
            diff = max(vals) - min(vals)
            if diff < min_diff:
                min_diff = diff
    f(h, w)
    f(w, h)
    return min_diff

_h, _w = map(int, input().split())
print(solve(_h, _w))

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
if H%3==0 or W%3==0:
    print(0)

elif H%2==0 or W%2==0:
    if W%2==0:
        H,W=W,H
    A1=(H//2 )* W
    A3=0
    value=A1-A3
    for i in range(1,W//2 +):
        A3+=H
        A1-=H//2
        value=min(int(abs(A1-A3)),value)
    print(value)
else:
    A1=(H//2 +1)* W
    A2=(H//2)* W
    A3=0
    value=max(A1,A2,A3)-min(A1,A2,A3)
    for i in range(1,W//2):
        A3+=H
        A1-=H//2 + 1
        A2-=H//2
        value=min(max(A1,A2,A3)-min(A1,A2,A3),value)

    H,W=H,W
    A1=(H//2 +1)* W
    A2=(H//2) * W
    A3=0
    value=min(max(A1,A2,A3)-min(A1,A2,A3),value)
    for i in range(1,W//2):
        A3+=H
        A1-=H//2 + 1
        A2-=H//2
        value=min(max(A1,A2,A3)-min(A1,A2,A3),value)
    print(value)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
if H%3==0 or W%3==0:
    answer = 0
else:
    answer = min(H, W)
# さらに小さくするには縦と横で割る
def cal(H, W):
    h = H // 3
    area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
    answer = min(answer, max(area)-min(area))
    h += 1
    area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
    answer = min(answer, max(area)-min(area))

cal(H, W)
cal(W, H)
print(answer)
# 13

Submission status: Runtime Error

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()

  if h%3==0 or w%3==0:
    return 0

  ans=inf
  for i in range(1,h):
    a=i*w
    b=(h-i)*w//2
    c=(h-i)*(-(-w)//2)
    ans=min(ans,max([a,b,c])-min([a,b,c]))
    if a+b+c!=h*W:
      aaa

    a=i*w
    b=(h-i)//2*w
    c=-(-(h-i)//2)*w
    ans=min(ans,max([a,b,c])-min([a,b,c]))
    if a+b+c!=h*W:
      aaa

  for i in range(1,w):
    a=i*h
    b=(w-i)*h//2
    c=(w-i)*(-(-h)//2)
    ans=min(ans,max([a,b,c])-min([a,b,c]))
    if a+b+c!=h*W:
      aaa

    a=i*h
    b=(w-i)//2*h
    c=-(-(w-i)//2)*h
    ans=min(ans,max([a,b,c])-min([a,b,c]))
    if a+b+c!=h*W:
      aaa

  return ans

# main()
print(main())

Submission status: Runtime Error

Solution code:
import math
H,W=map(int,input().split())
if H%3==0 or W%3==0:
  print(0)
  exit(0)
S=[0]*3
s=H*import math
H,W=map(int,input().split())
if H%3==0 or W%3==0:
  print(0)
  exit(0)
S=[0]*3
s=H*W/3
w0=math.ceil(s/H)
h0=math.ceil(s/W)

S[0]=w0*H
w1=W-W/3
w0=math.ceil(s/H)
h0=math.ceil(s/W)

S[0]=w0*H
w1=W-w0
if w1%2==0 or H%2==0:
  S[1]=(H*w1)//2
  S[2]=(H*w1)//2
else:
  s1=H*w1/2
  w10=math.ceil(s1/H)
  h10=math.ceil(s1/w1)
  S[2]=max((w1-w10)*H,(H-h10)*w1)
ans=abs(S[0]-S[2])

S[0]=W*h0
h1=H-h0
if h1%2==0 or W%2==0:
  S[1]=(W*h1)//2
  S[2]=(W*h1)//2
else:
  s1=h1*W/2
  w11=math.ceil(s1/h1)
  h11=math.ceil(s1/W)
  S[2]=max((W-w11)*h1,(h1-h11)*W)
ans=min(ans,abs(S[0]-S[2]))


S=[0]*3
s=H*W/3
w0=math.floor(s/H)
h0=math.floor(s/W)

S[0]=w0*H
w1=W-w0
if w1%2==0 or H%2==0:
  S[1]=(H*w1)//2
  S[2]=(H*w1)//2
else:
  s1=H*w1/2
  w10=math.floor(s1/H)
  h10=math.floor(s1/w1)
  S[2]=max((w1-w10)*H,(H-h10)*w1)
ans=min(ans,abs(S[0]-S[2]))

S[0]=W*h0
h1=H-h0
if h1%2==0 or W%2==0:
  S[1]=(W*h1)//2
  S[2]=(W*h1)//2
else:
  s1=h1*W/2
  w11=math.floor(s1/h1)
  h11=math.floor(s1/W)
  S[2]=max((W-w11)*h1,(h1-h11)*W)
ans=min(ans,abs(S[0]-S[2]))

print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    middle = w // 2
    ans = 10 ** 10
    for i in range(h):
        area = [i * w, (h - i) * middle, (h - i) * (w - middle)]
        ans = min(ans, max(area) - min(area))
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    x = heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    y = heapq.heappop(Q)
    sp = sp + R[i-1] - x
    sq = sq - R[-i] - y
    p[i] = sp
    q[i] = sq
ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    heapq.heappop(P)
    sp = sum(P)
    p[i] = sum(Q)
for i in range(1,N+1):
    heapq.heappush(Q,-R[-i])
    heapq.heappop(Q)
    sq = sum(Q)
    q[i] = sq

ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
import heapq
for i in range(N+1):
    P = A[:(N+i)]
    Q = A[(N+i):]
    for l in range(len(Q)):
        Q[l] *= -1
    heapq.heapify(P)
    heapq.heapify(Q)
    j = 0
    k = 0
    while j < i:
        heapq.heappop(P)
        j += 1
    while k < N-i:
        heapq.heappop(Q)
        k += 1
    s = sum(P) + sum(Q)
    S.append(s)
ans = max(S)
print(ans)

Submission status: Runtime Error

Solution code:
from math import floor, ceil
h, w = map(int, input().split(' '))
result = []
if h%3 == 0 or w%3 == 0:
    print(0)
else:
    for i in range(1, h-1):
        x = i*w
        y = (h-i)*floor(w/2)
        z = (h-i)*ceil(w/2)
        result.append(max(x,y,z)-min(x,y,z))
        y = floor((h-i)/2)*w
        z = ceil((h-i)/2)*w
        result.append(max(x,y,z)-min(x,y,z))
    for i in range(1, w-1):
        x = i*h
        y = (w-i)*floor(h/2)
        z = (w-i)*ceil(h/2)
        result.append(max(x,y,z)-min(x,y,z))
        y = floor((w-i)/2)*h
        z = ceil((w-i)/2)*h
        result.append(max(x,y,z)-min(x,y,z))
    print(min(result))

Submission status: Runtime Error

Solution code:
import numpy as np
from heapq import heapreplace, heapify
N=int(input())
A=np.array([int(a) for a in input().split(" ")])
lheap, rheap = list(A[:N]), list(-A[2*N:])
heapify(lheap)
heapify(rheap)
Lsum, Rsum = sum(lheap), sum(rheap)
left = [Lsum]
right = [Rsum]

for i in range(N):
    if A[N+i] > lheap[0]:
        Lsum += (A[N+i]-lheap[0])
        heapreplace(lheap, A[N+i])
    
    if -A[2*N-i-1] > rheap[0]:
        Rsum += (-A[2*N-i-1]-rheap[0])
        heapreplace(rheap, -A[2*N-i-1])
    
    left.append(Lsum)
    right.append(Rsum)
print(max(np.array(left)+np.array(right)[::-1]))

Submission status: Runtime Error

Solution code:
from heapq import*
from collections import*
n,*a=map(int,open(0).read().split())
ans=-float("inf")
b=a[:n]
c=deque(a[n:])
heapify(b)
s=sum(b)
s2=sum(nsmallest(n,c))
red=[s-s2]
for i in range(n,n*2):
    s+=a[i]-heappushpop(b,a[i])
    c.popleft()
    s2=sum(nsmallest(n,c))
    red+=[s-s2]
print(max(red))

#あｈｊｆｋぁｄｓｈｆｌｋじゃｇはｌｋｊｄｊｇｌｋ；あｊｄｇｌｋ；あｄｓｊｇｌ；あｊｓｄｇｌｋ；あｊｓｄｇｌ；かｓ

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
if h*w%3==0:
  print(0)
else:
  ans=min(h,w)
  hh=h//2
  for ww in range(1,w):
    A=[hh*ww,(h-hh)*ww,h*(w-ww)]
    ans=min(ans,max(A)-min(A))
  ww=w//2
  for hh in range(1,h):
    B=[ww*hh,(w-ww)*hh,(h-hh)*w]
    ans=min(ans,max(B)-min(B))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
array = [int(i) for i in input().split()]
ans=-1e14

for i in range(n, 2*n+1):
    l_array = sorted(array[:i])
    r_array = sorted(array[i:])
    ans = max(ans, sum(l_array[i-n:])-sum(r_array[:n]))

print(ans)

Submission status: Runtime Error

Solution code:
#ABC074C
H,W = map(int, input().split())
if H%3==0 or W%3==0:
    print(0)
else:
    a=H//3
    b=H//3+1
    c=H-(a+b)
    abc=[a,b,c]
    ans=min(max(abc)-min(abc),ans)
    a=W//3
    b=W//3+1
    c=W-(a+b)
    abc=[a,b,c]
    ans=min(max(abc)-min(abc),ans)

    for i in range(1,W+1):
        a=i*H
        b=(W-i)*(H//2) 
        c=H*W-(a+b)
        abc=[a,b,c]
        ans=min(max(abc)-min(abc),ans)

    for i in range(1,H+1): 
        a=i*W
        b=(H-i)*(W//2) 
        c=H*W-(a+b)
        abc=[a,b,c]
        ans=min(max(abc)-min(abc),ans)
    print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
s = h * w
if (h == 2) & (w == 2):
    ans = 1
if s % 3 == 0:
    ans = 0
else:
    c = []
    for i in range(1, h-1):
        sa = i * w
        sb = (h - i) * (w // 2)
        sc = (h - i) * (w - (w // 2))
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
    for i in range(1, w-1):
        sa = i * h
        sb = (w - i) * (h // 2)
        sc = (w - i) * (h - (h // 2))
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
    ans = min(c)
print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
s = h * w
if s % 3 == 0:
    ans = 0
else:
    c = []
    for i in range(1, h-1):
        sa = i * w
        sb = (h - i) * (w // 2)
        sc = (h - i) * (w - (w // 2))
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
    for i in range(1, w-1):
        sa = i * h
        sb = (w - i) * (h // 2)
        sc = (w - i) * (h - (h // 2))
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
    ans = min(c)
print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int,input().split())

if h%3 ==0 or w % 3 == 0:
	print(0)
	exit()

x = w//4
Sb =max(x*h,h//2*(w-x),(h-h//2)*(w-x))
Ss =min(x*h,h//2*(w-x),(h-h//2)*(w-x))
ans1 =Sb-ss
x += 1
Sb =max(x*h,h//2*(w-x),(h-h//2)*(w-x))
Ss =min(x*h,h//2*(w-x),(h-h//2)*(w-x))
ans2 =Sb-ss
y = h//4
Sb =max(y*w,w//2*(h-y),(w-w//2)*(h-y))
Ss =min(y*w,w//2*(h-y),(w-w//2)*(h-y))
ans3 =Sb-ss
y += 1
Sb =max(y*w,w//2*(h-y),(w-w//2)*(h-y))
Ss =min(y*w,w//2*(h-y),(w-w//2)*(h-y))
ans4 =Sb-ss

print(min(ans1,ans2,ans3,ans4))

Submission status: Runtime Error

Solution code:
import sys
a,b=map(int,input().split())
if a>b:
	swap(a,b)
if a%3==0 or b%3==0:
	print(0)
	sys.exit()
c=int((b+1)/3)
b-=c
d=int(a/2)
e=a-d
print(max(c*a,b*d,b*e)-min(c*a,b*d,b*e))

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
if a>b:
	swap(a,b)
if a%3==0 or b%3==0:
	print(0)
	exit(0)
c=int((b+1)/3)
b-=c
d=int(a/2)
e=a-d
print(max(c*a,b*d,b*e)-min(c*a,b*d,b*e))

Submission status: Runtime Error

Solution code:
h, w=map(int,input().split())
m = h * w

if h % 3 == 0 or w % 3 == 0:
  print(0)
  exit()

def chk(h,w):
  a = m
  for i in range(1, h):
    l = i * w
    o = (h - i) // 2 * w
    g = m - l - o
    a = min(a, max(abs(l - o), abs(g - o), abs(g - l)))

  for i in range(1, h):
    l = i * w
    o = (h - i) * (w // 2)
    g = m - i - o
    a = min(a, max(abs(l - o), abs(g - o), abs(g - l)))

  return a

print(min(chk(h, w), cck(w, h)))

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
l = max(h, w)
s = min(h, w)
if h % 3 == 0 or w % 3 == 0:
	print(0)
else:
	if abs((l // 3) - l / 3) <= abs((l // 3 + 1) - l / 3):
		block1 = s * (l // 3)
		block3 = (l - (l // 3)) * ((s + 1) // 2)
		block2 = H * W - block1 - block3
		print(max(block1, block2, block3) - min(block1, block2, block3))
	else:
		block1 = s * (l // 3 + 1)
		block3 = (l - 1 - (l // 3)) * (s // 2)
		block2 = H * W - block1 - block3
		print(max(block1, block2, block3) - min(block1, block2, block3))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
def calculate_t(x, y):
    min_d = 1e12
    for i in range(x):
        s1 = (y//2)*i
        s2 = y*(x-i)
        s3 = (y-y//2)*i
        min_d = min(min_d, max(s1,s2,s3) - min(s1,s2,s3))
    return min_d
def calculate_3(x, y):
    for i in range(x):
        w1 = i
        w2 = (x-i)//2
        x3 = x - w1 -w2
        return min(w1, w2, w3)*y
if (h*w)%3 == 0:
    print(0)
else:
    d1 = calculate_t(h,w)
    d2 = calculate_t(w,h)
    d3 = calculate_3(h,w)
    d4 = calculate_3(w,h)
    print(min(d1,d2,d3,d4))

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
if h%3 == 0 or w%3 ==0:
    print(0)
else:
    def calculate_t(x, y):
        d = h*w + 1
        i = x//2
        s1, s2 = 0, d
        rng = range(x) if x < 1000 else range(x//3, x*4//5)
        new_d = h*w
        for i in rng:
            s1 = (y//2)*i
            s2 = y*(x-i)
            s3 = (y-y//2)*i
            new_d = max(s1,s2,s3)- min(s1,s2,s3)
            if d > new_d:
                d = new_d
                continue
            else:
                break
        return d
    def calculate_3(x, y):
        h1 = y//3
        h2 = y//3 + y%3
        return x*(h2-h1)
    
    if h == w:
        print(min(d1,d2))
    else:
        d3 = calculate_t(w, h)
        d4 = calculate_3(w, h)
        print(min(d1,d2,d3,d4))

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
if h%3 == 0 or w%3 ==0:
    print(0)
else:
    def calculate_d(x, y):
        d = h*w + 1
        i = x//2
        s1, s2 = 0, d
        for i in range(x):
            s1 = (y//2)*i
            s2 = y*(x-i)
            s3 = (y-y//2)*i
            new_d = max(abs(s1-s2), abs(s1-s3))
            if s1 < s2:
                i = 
            if d > new_d:
                d = new_d
                continue
            else:
                break
        return d
    d1 = calculate_d(h, w)
    d2 = calculate_d(w, h)
    print(min(d1,d2))

Submission status: Runtime Error

Solution code:
def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)
 
def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return [area1, area2]
 
def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h

        tmp = solve2(h, w - w2)
        ans = min(ans, max_minus_min([area1, tmp[0], tmp[1]])

        tmp = solve2(w - w2, h)
        ans = min(ans, max_minus_min([area1, tmp[0], tmp[1]])
    return ans
 
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))

Submission status: Runtime Error

Solution code:
def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)
 
def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return area1, area2
 
def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h
        ans = min(ans, max_minus_min([area1, *solve2(h, w - w2)]))
        ans = min(ans, max_minus_min([area1, *solve2(w - w2, h)]))
    return ans
 
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))

Submission status: Runtime Error

Solution code:
def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)
 
def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return [area1, area2]
 
def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h
        ans = min(ans, max_minus_min([area1, *solve2(h, w - w2)]))
        ans = min(ans, max_minus_min([area1, *solve2(w - w2, h)]))
    return ans
 
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))