Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

# 解説AC
# http://drken1215.hatenablog.com/entry/2019/09/16/213700
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

DIGIT = 60

mat = []
for a in A:
    mat.append(list(np.binary_repr(a, DIGIT)))
mat = np.array(mat, dtype=np.uint8).T

zero_rows = mat.sum(axis=1) == 0
# ビットの数が奇数の場合、どう頑張っても変わらない
odd_rows = (mat.sum(axis=1) % 2).astype(bool)
mat[odd_rows, :] = 0

# MOD 2 の方程式
# 全部 1 にしたい
mat = np.hstack((mat, np.ones((DIGIT, 1), dtype=np.uint8)))

# 掃き出し法
used_row = np.zeros(DIGIT, dtype=bool)
for col in range(N):
    pivot = (mat[:, col] & ~used_row).argmax()
    if not mat[pivot, col]:
        continue
    used_row[pivot] = True

    pivot_row = mat[pivot].copy()
    mat[mat[:, col].astype(bool)] ^= pivot_row
    mat[pivot] = pivot_row

# 矛盾するやつを除外
# 一番右だけ 1 で他が 0 の行は矛盾
ng_rows = (mat[:, :-1].sum(axis=1) == 0) & (mat[:, -1] == 1)
ok_even_rows = ~odd_rows & ~zero_rows & ~ng_rows

ans = 0
for d in range(DIGIT):
    ans += pow(2, d) * (odd_rows[~d] + ok_even_rows[~d] * 2)
print(ans)


Fixed submission:
import os
import os
import sys
from functools import reduce
from operator import xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A = np.array(A, dtype=np.int64)


def dump(arr):
    for a in arr:
        print(np.binary_repr(a, 60))
    print()


# 解説AC
# 立ってるビットが奇数ならどう分けても結果は同じ
odds = reduce(xor, A)
ans = odds

# 奇数のやつは無視
A &= ~odds

# 行標準形にする
# https://qiita.com/vain0x/items/015ff6d49853e5d9d403#f---xor-sum-3
rank = 0
for d in reversed(range(60)):
    # 下からd桁目が立ってる最初のindex
    bits1 = (A >> d & 1).astype(bool)
    pos = bits1[rank:].argmax() + rank
    if not bits1[pos]:
        continue  # 全部ゼロ
    if pos < rank:
        continue  # rank より下に 1 がない。どう頑張っても変えられない。(?)

    # 基準にする行
    pivot_row = A[pos]
    # 基準以外を全部ゼロにする
    A[bits1] ^= pivot_row
    A[pos] = pivot_row
    # 基準行を一番上に持ってくる
    A[pos], A[rank] = A[rank], A[pos]
    rank += 1

ans += reduce(xor, A) * 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))


# 逆から貪欲に操作可能
def solve():
    heap = [(-b, i) for i, b in enumerate(B)]
    heapq.heapify(heap)
    ret = 0
    while heap:
        b, i = heapq.heappop(heap)
        b *= -1
        a = A[i]
        if b < a:
            return -1
        if b == a:
            continue
        step = B[(i - 1) % N] + B[(i + 1) % N]
        if (b - a) // step == 0:
            return -1
        cnt = (b - a) // step
        ret += cnt
        b -= cnt * step
        B[i] = b
        heapq.heappush(heap, (-b, i))
    return ret


ans = solve()
print(ans)


Fixed submission:
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))


# 逆から貪欲に操作可能
def solve():
    heap = [(-b, i) for i, b in enumerate(B)]
    heapq.heapify(heap)
    ret = 0
    while heap:
        b, i = heapq.heappop(heap)
        b *= -1
        a = A[i]
        if b < a:
            return -1
        if b == a:
            continue
        step = B[(i - 1) % N] + B[(i + 1) % N]
        if (b - a) // step == 0:
            return -1
        cnt = (b - a) // step
        ret += cnt
        b -= cnt * step
        B[i] = b
        heapq.heappush(heap, (-b, i))
    return ret


ans = solve()
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def can_make(div):
    mods = []
    for a in A:
        mods.append(a % div)

    mods.sort()
    left = 0
    right = len(mods) - 1
    for k in range(K + 1):
        while left < len(mods) and mods[left] % div == 0:
            left += 1
        while right >= 0 and mods[right] % div == 0:
            right -= 1
        if right < left:
            return True
        mods[left] -= 1
        mods[right] += 1
    return False


N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))

# 答えは絶対 A の合計の約数になる
divs = get_divisors(sum(A))
for div in sorted(divs, reverse=True):
    if can_make(div):
        print(div)
        exit()
assert False


Fixed submission:
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def can_make(div):
    mods = []
    for a in A:
        mods.append(a % div)

    mods.sort()
    left = 0
    right = len(mods) - 1
    k = K
    while left <= right and k >= 0:
        while left < len(mods) and mods[left] % div == 0:
            left += 1
        while right >= 0 and mods[right] % div == 0:
            right -= 1
        if right < left:
            return True

        m = div - mods[right]
        if mods[left] >= m:
            mods[left] -= m
            mods[right] = 0
            right -= 1
            k -= m
        else:
            mods[right] += mods[left]
            k -= mods[left]
            mods[left] = 0
            left += 1
    return k >= 0


N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))

# 答えは絶対 A の合計の約数になる
divs = get_divisors(sum(A))
for div in sorted(divs, reverse=True):
    if can_make(div):
        print(div)
        exit()
assert False
Buggy python submission (verdict: Runtime Error):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]

a = list(itertools.accumulate(A, max))
b = list(itertools.accumulate(A[::-1], max))[::-1]

for i in range(len(A)):
    r = 0
    if 0 <= i - 1 < N:
        r = max(r, a[i - 1])
    if 0 <= i + 1 < N:
        r = max(r, b[i + 1])
    print(r)


Fixed submission:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]

a = list(itertools.accumulate(A, max))
b = list(itertools.accumulate(A[::-1], max))[::-1]

for i in range(len(A)):
    r = 0
    if 0 <= i - 1 < N:
        r = max(r, a[i - 1])
    if 0 <= i + 1 < N:
        r = max(r, b[i + 1])
    print(r)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]

a = np.array(list(itertools.accumulate(A, max)))
b = list(itertools.accumulate(A[::-1], max))[::-1]

for i in range(len(A)):
    r = 0
    if len(a[:i]) > 0:
        r = max(r, *a[:i])
    if len(b[i + 1:]) > 0:
        r = max(r, *b[i + 1:])
    print(r)


Fixed submission:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]

a = list(itertools.accumulate(A, max))
b = list(itertools.accumulate(A[::-1], max))[::-1]

for i in range(len(A)):
    r = 0
    if 0 <= i - 1 < N:
        r = max(r, a[i - 1])
    if 0 <= i + 1 < N:
        r = max(r, b[i + 1])
    print(r)
Buggy python submission (verdict: Runtime Error):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

if len(A) % 3 == 0:
    c = Counter(A)
    k = c.keys()
    s = len(c.keys())
    if len(k) == 3:
        ok = len(Counter(c.values()).keys()) == 1
    if len(k) == 2:
        ok = min(c.values()) * 2 == max(c.values())
    if len(k) == 1:
        ok = True
else:
    ok = False
if ok:
    print('Yes')
else:
    print('No')


Fixed submission:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

ok = False
counts = dict(Counter(A))
keys = counts.keys()
if len(counts) <= 3:
    for k1, k2, k3 in itertools.product(keys, repeat=3):
        cnt = counts.copy()
        s = k1
        cnt[k1] -= 1
        cnt[k2] -= 1
        if k1 ^ k2 != k3:
            continue
        n = 2
        while n < N:
            cnt[k3] -= 1
            k1, k2, k3 = k2, k3, k2 ^ k3
            n += 1
        if s == k3 and not any(cnt.values()):
            ok = True
            break

if ok:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
counts = defaultdict(int)
for i, (a, b) in enumerate(AB):
    graph[a].append((b, i))
    graph[b].append((a, i))
    counts[a] += 1
    counts[b] += 1

# 偶数なら全部出す
ans = []
used = [False] * (N + 1)
p = -1
while p != len(ans):
    p = len(ans)
    for v in range(1, N + 1):
        if counts[v] % 2 == 0:
            for u, i in graph[v]:
                if used[i]:
                    continue
                ans.append((v, u))
                used[i] = True
                counts[v] -= 1
                counts[u] -= 1
if len(ans) == M:
    for a in ans:
        print(*a)
else:
    print(-1)


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)


def spanning_tree(root, ret=None, seen=None):
    if ret is None:
        ret = [set() for _ in range(N + 1)]
    if seen is None:
        seen = [False] * (N + 1)
        seen[root] = True
    for v in graph[root]:
        if seen[v]:
            continue
        ret[root].add(v)
        seen[v] = True
        ret = spanning_tree(v, ret, seen)
    return ret


if M % 2 == 1:
    print(-1)
    exit()

# 全域木
root = 1
st = spanning_tree(root)

# 出次数
outdeg = [0] * (N + 1)
ans = []
# 使わなかった辺に向きをつける
for a, b in AB:
    if a not in st[b] and b not in st[a]:
        ans.append((a, b))
        outdeg[a] += 1


def dfs(par):
    # 全域木で par 以下の辺に向きをつける
    for v in st[par]:
        if st[v]:
            dfs(v)
        if outdeg[v] % 2 == 0:
            ans.append((par, v))
            outdeg[par] += 1
        else:
            ans.append((v, par))
            outdeg[v] += 1


dfs(root)
for r in ans:
    print(*r)
Buggy python submission (verdict: Runtime Error):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def bisect_left_callable(fn, x, lo, hi):
    """
    (memo) いっぱい呼ぶなら np.searchsorted のほうがベクトル化されててはやそう
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def solve(n, a=False):
    mts = A.copy()
    mts[0] -= n
    mts[-1] -= n
    hist = [n*2]
    for i in range(N):
        mts[(i + 1) % N] -= mts[i]
        hist.append(mts[i] * 2)
    if a:
        return hist
    else:
        return -mts[-1]


n = bisect_left_callable(solve, 0, 0, A[0] + 1)
print(*solve(n, True)[:-1])


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def bisect_left_callable(fn, x, lo, hi):
    """
    (memo) いっぱい呼ぶなら np.searchsorted のほうがベクトル化されててはやそう
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def solve(n, a=False):
    mts = A.copy()
    mts[0] -= n
    mts[-1] -= n
    hist = [n*2]
    for i in range(N):
        mts[(i + 1) % N] -= mts[i]
        hist.append(mts[i] * 2)
    if a:
        return hist
    else:
        return -mts[-1]


n = bisect_left_callable(solve, 0, 0, A[0] + 1)
print(*solve(n, True)[:-1])
Buggy python submission (verdict: Runtime Error):
import math
import os
import sys
from fractions import gcd
from decimal import *

from libs.debug import debug

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

A, B, C, D = list(map(int, sys.stdin.readline().split()))
A = Decimal(A)
B = Decimal(B)
C = Decimal(C)
D = Decimal(D)


def count(n):
    st = math.ceil(A / n)
    en = math.floor(B / n)
    return max(0, en - st + 1)


print(B - A + 1 - (count(C) + count(D) - count(C * D // gcd(C, D))))

#
# N = int(sys.stdin.readline())
# A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))


Fixed submission:
import math
import os
import sys
from decimal import *
from fractions import gcd

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

A, B, C, D = list(map(int, sys.stdin.readline().split()))
A = Decimal(A)
B = Decimal(B)
C = Decimal(C)
D = Decimal(D)


def count(n):
    st = math.ceil(A / n)
    en = math.floor(B / n)
    return max(0, en - st + 1)


print(B - A + 1 - (count(C) + count(D) - count(C * D // gcd(C, D))))

#
# N = int(sys.stdin.readline())
# A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))
Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7
N, M = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().split()))
T = list(map(int, sys.stdin.readline().split()))
S = [-1] + S
T = [-1] + T

# dp[i][j]: S[i] と T[j] で終わる組み合わせの数
# S[i] != T[j] のとき 0
# S[i] == T[j] のとき、sum(dp[:i][:j])
dp = np.zeros((len(S), len(T)), dtype=int)
dp[0][0] = 1
# dp の二次元累積和
cumsum = np.ones(len(T), dtype=int)
for i in range(1, len(S)):
    for j in range(1, len(T)):
        if S[i] != T[j]:
            continue
        # dp[i][j] = dp[:i, :j].sum() % MOD
        dp[i][j] = cumsum[j - 1] % MOD
    cumsum += dp[i].cumsum()
    cumsum %= MOD
print(cumsum[-1])


Fixed submission:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7
N, M = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().split()))
T = list(map(int, sys.stdin.readline().split()))
S = np.array([-1] + S)
T = np.array([-1] + T)

# # dp[i][j]: S[i] と T[j] で終わる組み合わせの数
# # S[i] != T[j] のとき 0
# # S[i] == T[j] のとき、sum(dp[:i][:j])
# dp = np.zeros((len(S), len(T)), dtype=int)
# dp[0][0] = 1
# # dp の二次元累積和
# cumsum = np.ones(len(T), dtype=int)
# for i in range(1, len(S)):
#     for j in range(1, len(T)):
#         if S[i] != T[j]:
#             continue
#         # dp[i][j] = dp[:i, :j].sum() % MOD
#         dp[i][j] = cumsum[j - 1] % MOD
#     cumsum += dp[i].cumsum()
#     cumsum %= MOD
# print(cumsum[-1])


cumsum = np.ones(len(T), dtype=int)
for i in range(1, len(S)):
    cumsum[1:] += ((T == S[i])[1:] * cumsum[:-1] % MOD).cumsum()
    cumsum %= MOD
print(cumsum[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
GA, SA, BA = list(map(int, sys.stdin.readline().split()))
GB, SB, BB = list(map(int, sys.stdin.readline().split()))

values = []
weights = []
if GB / GA > 1:
    values.append(GB - GA)
    weights.append(GA)
if SB / SA > 1:
    values.append(SB - SA)
    weights.append(SA)
if BB / BA > 1:
    values.append(BB - BA)
    weights.append(BA)
# dp[i]: 重さ i 以下で選ぶのの価値の最大値
dp = [0] * (N + 1)
dp[0] = N
if values:
    for i in range(1, N + 1):
        x = dp[i - 1]
        for w, v in zip(weights, values):
            if i - w >= 0:
                x = max(x, dp[i - w] + v)
        dp[i] = x
    N = dp[N]

values = []
weights = []
if GA / GB > 1:
    values.append(GA - GB)
    weights.append(GB)
if SA / SB > 1:
    values.append(SA - SB)
    weights.append(SB)
if BA / BB > 1:
    values.append(BA - BB)
    weights.append(BB)
# dp[i]: 重さ i 以下で選ぶのの価値の最大値
dp = [0] * (N + 1)
dp[0] = N
if values:
    for i in range(1, N + 1):
        x = dp[i - 1]
        for w, v in zip(weights, values):
            if i - w >= 0:
                x = max(x, dp[i - w] + v)
        dp[i] = x
    N = dp[N]
print(int(N))


Fixed submission:
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
GA, SA, BA = list(map(int, sys.stdin.readline().split()))
GB, SB, BB = list(map(int, sys.stdin.readline().split()))

values = []
weights = []
if GB / GA > 1:
    values.append(GB - GA)
    weights.append(GA)
if SB / SA > 1:
    values.append(SB - SA)
    weights.append(SA)
if BB / BA > 1:
    values.append(BB - BA)
    weights.append(BA)
# dp[i]: 重さ i 以下で選ぶのの価値の最大値
dp = [0] * (N + 1)
dp[0] = N
if values:
    for i in range(1, N + 1):
        x = dp[i - 1]
        for w, v in zip(weights, values):
            if i - w >= 0:
                x = max(x, dp[i - w] + v)
        dp[i] = x
    N = dp[N]

values = []
weights = []
if GA / GB > 1:
    values.append(GA - GB)
    weights.append(GB)
if SA / SB > 1:
    values.append(SA - SB)
    weights.append(SB)
if BA / BB > 1:
    values.append(BA - BB)
    weights.append(BB)
# dp[i]: 重さ i 以下で選ぶのの価値の最大値
dp = [0] * (N + 1)
dp[0] = N
if len(values) == 3:
    for i in range(1, N + 1):
        x = dp[i - 1]
        for w, v in zip(weights, values):
            if i - w >= 0:
                x = max(x, dp[i - w] + v)
        dp[i] = x
    N = dp[N]
if len(values) == 2:
    w1, w2 = weights
    v1, v2 = values
    if (v1 + w1) / w1 < (v2 + w2) / w2:
        v1, v2 = v2, v1
        w1, w2 = w2, w1
    c1 = N // w1
    c2 = (N - w1 * c1) // w2
    ret = N + v1 * c1 + v2 * c2
    while c1 >= 0:
        a = N - w1 * c1 - w2 * c2
        c1 -= max(1, math.ceil((w2 - a) / w1))
        c2 = (N - w1 * c1) // w2
        ret = max(ret, N + v1 * c1 + v2 * c2)
        if w1 * c1 + w2 * c2 == N:
            break
    N = ret
if len(values) == 1:
    N += N // weights[0] * values[0]
print(int(N))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import sys
from functools import reduce
from operator import mul

sys.setrecursionlimit(10000)
INF = float('inf')


def comb(n, r):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :rtype: int
    """
    assert n >= r
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


N, M, K = list(map(int, input().split()))

def pyramid(n):
    return n * (n + 1) * (n + 2) // 6


# K ==2 の場合
# print(pyramid(N - 1) * M ** 2 + pyramid(M - 1) * N ** 2)
a = comb(N * M-2, K-2)
b = pyramid(N - 1) * M ** 2 + pyramid(M - 1) * N ** 2
print(a*b% (10**9+7))


Fixed submission:
import math
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def inv(x):
    return pow(x, MOD - 2, MOD)


def comb(n, r, mod):
    # https://fushime2.hatenablog.com/entry/2016/11/12/155543
    return (math.factorial(n) * inv(math.factorial(n - r)) * inv(math.factorial(r))) % mod


N, M, K = list(map(int, input().split()))


def pyramid(n):
    return n * (n + 1) * (n + 2) // 6


MOD = 10 ** 9 + 7

# K ==2 の場合
# print(pyramid(N - 1) * M ** 2 + pyramid(M - 1) * N ** 2)
k2 = (pyramid(N - 1) * M ** 2 + pyramid(M - 1) * N ** 2) % MOD
# k2 を何回使うか
c = comb(N * M - 2, K - 2, mod=MOD)
print(k2 * c % MOD)