Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03476 (python)

Fixed submission:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


q = int(input())
lrl = []
for _ in range(q):
    lrl.append(list(map(int, input().split())) )

primes = set(get_sieve_of_eratosthenes(10**5))
like2017s = []
cnt_dict = {}
cnt_dict[-1] = 0
for i in range(10**5//2):
    num = i*2+1
    num2 = (num+1)//2
    if num in primes and num2 in primes:
        cnt_dict[num] = cnt_dict[num-2]+1
    else:
        cnt_dict[num] = cnt_dict[num-2]

for lr in lrl:
    l,r = lr
    print(cnt_dict[r]-cnt_dict[l-2])

Buggy submission (verdict: Runtime Error):
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

sums = [0,0,0]
curr_sum = 0
ps = primes(10**3)
pset = set(ps)
for i in range(3,10**2+1):
    for p in ps:
        if i%p == 0 and i not in pset:
            break
        if ((i+1)//2)%p == 0 and ((i+1)//2) not in pset:
            break
    else:
        curr_sum += 1
        # print(i)
    sums.append(curr_sum)
    

q = int(input())
ansl = []
for _ in range(q):
    l,r = map(int, input().split())
    ans = sums[r] - sums[l-1]
    ansl.append(ans)

for a in ansl: print(a)

# print(sums[:54])
Problem p03557 (python)

Fixed submission:
import bisect
n = int(input())
al = list(map(int,input().split()))
bl = list(map(int,input().split()))
cl = list(map(int,input().split()))

al.sort()
bl.sort()
cl.sort()

cnt = 0
for b in bl:
    a_num = bisect.bisect_left(al,b)
    c_num = n - bisect.bisect_right(cl,b)
    cnt += a_num*c_num
    # cnt += c_num

print(cnt)

Buggy submission (verdict: Runtime Error):
import bisect

n = int(input())
al = list(map(int,input().split())).sort()
bl = list(map(int,input().split())).sort()
cl = list(map(int,input().split())).sort()

ans = 0
for b in bl:
    a_num = bisect.bisect_left(al,b)
    c_num = n - bisect.bisect_right(cl,b)
    ans += a_num*c_num

print(ans)
Problem p04006 (python)

Fixed submission:
n,x = map(int, input().split())
al = list(map(int, input().split()))

costs = al[:]
curr_sums = sum(costs)

# curr_mins = al[:]
curr_mins = al[:]

ans = 10**18
for i in range(0,n): # move cnt
    curr_i_ans = 0
    for j in range(n): # ind
        ind = j-i
        if ind < 0: ind+=n
        # xcost = i*x
        next_a = al[ind]
        if curr_mins[j] > next_a:
            curr_mins[j] = next_a
        cost = curr_mins[j]
        curr_i_ans += cost
    ans = min(ans, curr_i_ans+i*x)

print(ans)

Buggy submission (verdict: Runtime Error):
# 0-indexed
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  # init leaf
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  # bottom-up
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    # [l,r)
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)


'''
def add(a,b): return a+b
st = SegTree(vl,add,0)
st = SegTree(vl,(lambda a,b: a+b),0)
st = SegTree(vl,min,10**10)

print(st.query(2,4))
st.update(4,-4)
print(st.query(2,5))
st.update(0,-10)
print(st.query(0,5))
'''
n,x = map(int, input().split())
al = list(map(int, input().split()))

st = SegTree(al, min, 10**18)
ans = 10**18
for i in range(0,n): # move cnt
    curr_i_ans = i*x
    for j in range(n): # ind
        l = j-i
        if l >= 0:
            amin = st.query(l,j+1)
        else:
            amin1 = st.query(0,j+1)
            amin2 = st.query(l+n,n+1)
            amin = min(amin1,amin2)
        curr_i_ans += amin
    ans = min(ans, curr_i_ans) 
print(ans)
Problem p02648 (python)

Fixed submission:
import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np
from numba import njit


@njit('i8[:](i8,i8[:],i8[:],i8,i8[:],i8[:])')
def solve(n, vvv, www, q, uuu, lll):
    weight_limit = 10 ** 5
    precalc_limit = min(1 << 9, n + 1)
    precalc = [np.zeros(weight_limit + 1, dtype=np.int64)]

    for u in range(1, precalc_limit):
        v = vvv[u]
        w = www[u]
        parent_dp = precalc[u >> 1]
        dp = parent_dp.copy()
        dp[w:] = np.maximum(parent_dp[w:], parent_dp[:-w] + v)
        precalc.append(dp)

    buf = np.zeros(q, dtype=np.int64)
    for i in range(q):
        u = uuu[i]
        l = lll[i]
        if u < precalc_limit:
            buf[i] = precalc[u][l]
            continue
        dp = {0: 0}
        while u >= precalc_limit:
            v = vvv[u]
            w = www[u]
            for cw, cv in list(dp.items()):
                nw = cw + w
                nv = cv + v
                if nw > weight_limit:
                    continue
                if nw not in dp or dp[nw] < nv:
                    dp[nw] = nv
            u >>= 1
        ans = 0
        for w, v in dp.items():
            ans = max(ans, v + precalc[u][l - w])
        buf[i] = ans

    return buf


n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = np.array([0] + inp[0:n * 2:2], dtype=np.int64)
www = np.array([0] + inp[1:n * 2:2], dtype=np.int64)
q = inp[n * 2]
uuu = np.array(inp[n * 2 + 1::2], dtype=np.int64)
lll = np.array(inp[n * 2 + 2::2], dtype=np.int64)
ans = solve(n, vvv, www, q, uuu, lll)
print('\n'.join(map(str, ans)))
Problem p02697 (python)

Fixed submission:
n, m = map(int, input().split())
if n % 2 == 1:
    for i in range(1, m + 1):
        print(i, n + 1 - i)
else:
    turning_point = (m + 1) // 2
    for i in range(1, turning_point + 1):
        print(i, n + 1 - i)
    for i in range(turning_point + 1, m + 1):
        print(i, n - i)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
if n % 2 == 1:
    for i in range(1, m + 1):
        print(i, n + 1 - i)
else:
    used = [False] * (n + 1)
    i = 1
    count = 0
    while count < m:
        while used[i]:
            i += 1
        print(i, i + count + 1)
        used[i] = True
        used[i + count + 1] = True
        count += 1
Problem p02698 (python)

Fixed submission:
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, links, state, ans):
    ans[v] = len(state)
    for u in links[v]:
        if u == p:
            continue
        a = aaa[u]
        b, i = -1, -1
        if state[-1] < a:
            state.append(a)
        else:
            i = bisect_left(state, a)
            b = state[i]
            state[i] = a
        dfs(u, v, links, state, ans)
        if b == -1:
            state.pop()
        else:
            state[i] = b


n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    u, v = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
ans = [0] * n
dfs(0, -1, links, [aaa[0]], ans)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left


def dfs(v, p, links, state, ans):
    # print(v, p, state, ans)
    ans[v] = len(state)
    for u in links[v]:
        if u == p:
            continue
        a = aaa[u]
        b = -1
        i = bisect_left(state, aaa[u])
        if i == len(state):
            state.append(a)
        else:
            b = state[i]
            state[i] = a
        dfs(u, v, links, state, ans)
        if b == -1:
            state.pop()
        else:
            state[i] = b


n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    u, v = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
ans = [0] * n
dfs(0, -1, links, [aaa[0]], ans)
print('\n'.join(map(str, ans)))
Problem p02734 (python)

Fixed submission:
import numpy as np

n, s = map(int, input().split())
aaa = list(map(int, input().split()))

fwd_acc = np.zeros((n + 1, s + 1), dtype=np.int64)
fwd_acc[0][0] = 1

ans = 0
MOD = 998244353
for i, a in enumerate(aaa, start=1):
    fwd_acc[i] = fwd_acc[i - 1]
    fwd_acc[i][0] = i
    if a <= s:
        fwd_acc[i][a:] = fwd_acc[i][a:] + fwd_acc[i][:-a]
    fwd_acc[i] %= MOD
    ans = (ans + fwd_acc[i][s]) % MOD
    # print(fwd_acc)
    # print(ans)
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

n, s = map(int, input().split())
aaa = list(map(int, input().split()))

fwd_acc = np.zeros((n + 1, s + 1), dtype=np.int64)
fwd_acc[0][0] = 1

ans = 0
MOD = 998244353
for i, a in enumerate(aaa, start=1):
    fwd_acc[i] = fwd_acc[i - 1]
    fwd_acc[i][0] = i
    if a <= s:
        fwd_acc[i][a:] += fwd_acc[i][:-a]
    ans = (ans + fwd_acc[i - 1][s - a] * (n - i + 1)) % MOD
print(ans)
Problem p02750 (python)

Fixed submission:
import sys
from bisect import bisect
from itertools import accumulate

n, t = map(int, input().split())
constant = []
variable = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a == 0:
        constant.append(b + 1)
    else:
        variable.append((a / (b + 1), a, b))
constant.sort()
variable.sort(reverse=True)
INF = 10 ** 10
t += 1
t2 = t.bit_length() + 1
# dp[j]: (i番目まで見て) j件の店で買い物を完了した時の、次の店に到着できる最短時間
dp = [INF] * t2
dp[0] = 1
for _, a, b in variable:
    for j in range(t2 - 1, -1, -1):
        if dp[j] == INF:
            continue
        tmp = (a + 1) * dp[j] + b + 1
        if tmp > t:
            continue
        if dp[j + 1] > tmp:
            dp[j + 1] = tmp

const_acc = list(accumulate(constant))
ans = 0

for i, c in enumerate(dp):
    if c == INF:
        break
    remaining = t - c
    k = bisect(const_acc, remaining)
    ans = max(ans, i + k)

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
from itertools import accumulate

n, t = map(int, input().split())
constant = []
variable = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a == 0:
        constant.append(b + 1)
    else:
        variable.append((a / (b + 1), a, b))
constant.sort()
variable.sort(reverse=True)
INF = 10 ** 10
t += 1
t2 = t.bit_length() + 1
# dp[j]: (i番目まで見て) j件の店で買い物を完了した時の、次の店に到着できる最短時間
dp = [INF] * t2
dp[0] = 1
for _, a, b in variable:
    for j in range(t2 - 1, -1, -1):
        if dp[j] == INF:
            continue
        tmp = (a + 1) * dp[j] + b + 1
        if tmp > t:
            continue
        if dp[j + 1] > tmp:
            dp[j + 1] = tmp

const_acc = list(accumulate(constant))
ans = 0

k = len(constant) - 1
for i, c in enumerate(dp):
    if c == INF:
        break
    remaining = t - c
    while const_acc[k] <= remaining:
        k -= 1
    ans = max(ans, i + k + 1)

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect
from itertools import accumulate

n, t = map(int, input().split())
constant = []
variable = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a == 0:
        constant.append(b + 1)
    else:
        variable.append((a / (b + 1), a, b + 1))
constant.sort()
variable.sort(reverse=True)
INF = 10 ** 10
t += 1
t2 = t.bit_length() + 1
# dp[j]: (i番目まで見て) j件の店で買い物を完了した時の、次の店に到着できる最短時間
dp = [INF] * t2
dp[0] = 1
for _, a, b in variable:
    for j in range(t2 - 1, -1, -1):
        if dp[j] == INF:
            continue
        tmp = a * dp[j] + b
        if tmp > t:
            continue
        if dp[j + 1] > tmp:
            dp[j + 1] = tmp

const_acc = list(accumulate(constant))
ans = 0

for i, c in enumerate(dp):
    if c == INF:
        break
    remaining = t - c
    k = bisect(const_acc, remaining)
    ans = max(ans, i + k)

print(ans)
Problem p02787 (python)

Fixed submission:
import sys

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = [INF] * (20201)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for i in range(10000):
        if dp[i] == INF:
            continue
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))

Buggy submission (verdict: Runtime Error):
import sys


def solve(h, n, ab):
    ab.sort(key=lambda x: x[1] / x[0])
    INF = 10 ** 18
    cache = {}
    # とりあえず一番コスパいいやつだけを使った結果を暫定最良値としておく
    best = ((h - 1) // ab[0][0] + 1) * ab[0][1]

    def dp(k, i=0, cost=0):
        nonlocal best
        if k <= 0:
            return cost
        if (k, i) in cache:
            return cache[k, i] + cost
        a, b = ab[i]
        if k / a * b + cost >= best:
            # どう足掻いても残りでbestより良い結果は得られない
            return INF
        c = (k - 1) // a + 1
        if i == n - 1:
            ret = cost + b * c
        else:
            ret = min(dp(k - a * j, i + 1, cost + b * j) for j in range(c + 1))
        cache[k, i] = ret - cost
        best = min(best, ret)
        return ret

    dp(h)
    return best


sys.setrecursionlimit(1001)

h, n = map(int, input().split())
ab = [tuple(map(int, line.split())) for line in sys.stdin]
print(solve(h, n, ab))

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = np.full(h + 10001, INF, dtype=np.int64)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for s in range(0, h, a):
        sa = s + a
        s2a = s + 2 * a
        dp[sa:s2a] = np.minimum(dp[sa:s2a], dp[s:sa] + b)
print(dp[h:].min())

Buggy submission (verdict: Runtime Error):
import sys

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = [INF] * (h + 10001)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for i in range(10000):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))
Problem p02798 (python)

Fixed submission:
def iter_bit(k, LIMIT):
    v = (1 << k) - 1

    while v < LIMIT:
        yield v
        x = v & -v
        y = v + x
        v = (v & ~y) // x >> 1 | y


def solve(n, cards):
    dp = [{} for _ in range(1 << n)]
    dp[-1][0] = 0
    LIMIT = 1 << n

    for d in range(n):
        for state in iter_bit(n - d, LIMIT):
            scores = dp[state]
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                next_dp = dp[state ^ b]
                for left_num, score in scores.items():
                    if left_num > num:
                        continue
                    ns = score + curr
                    if num not in next_dp or next_dp[num] > ns:
                        next_dp[num] = ns
                k ^= b
                curr += 1

    if len(dp[0]) > 0:
        return min(dp[0].values())
    else:
        return -1


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict


def solve(n, cards):
    dp = {(1 << n) - 1: {0: 0}}
    for d in range(n):
        ndp = defaultdict(lambda: defaultdict(lambda: 1000000))
        for state, scores in dp.items():
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                curr_dp = ndp[state ^ b]
                for score, left_num in scores.items():
                    if left_num > num:
                        continue
                    curr_dp[score + curr] = min(curr_dp[score + curr], num)
                k ^= b
                curr += 1
        if len(ndp) == 0:
            return -1
        dp = ndp
    return min(dp[0].keys())


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))
Problem p02805 (python)

Fixed submission:
import sys
from itertools import combinations

import numpy as np

n = int(input())
points = np.array([np.fromiter(map(int, line.split()), dtype=np.float64) for line in sys.stdin])

if n == 2:
    p1, p2 = points
    print(np.sqrt(((p1 - p2) ** 2).sum()) / 2)
    exit()

ans = 10 ** 18
for p1, p2, p3 in combinations(points, 3):
    A = ((p2 - p3) ** 2).sum()
    B = ((p3 - p1) ** 2).sum()
    C = ((p1 - p2) ** 2).sum()
    sa, sb, sc = sorted([A, B, C])
    if sa + sb <= sc + 1e-7:
        c = (p2 + p3 if A == sc else p1 + p3 if B == sc else p1 + p2) / 2
        R2 = sc / 4
    else:
        T = A * (B + C - A)
        U = B * (C + A - B)
        W = C * (A + B - C)
        c = (T * p1 + U * p2 + W * p3) / (T + U + W)
        R2 = ((c - p1) ** 2).sum()
    if ((points - c) ** 2).sum(axis=1).max() <= R2 + 1e-7:
        print(np.sqrt(R2))
        break
else:
    raise AssertionError

Buggy submission (verdict: Runtime Error):
import sys
from itertools import combinations

import numpy as np

n = int(input())
points = np.array([np.fromiter(map(int, line.split()), dtype=np.float64) for line in sys.stdin])

if n == 2:
    p1, p2 = points
    print(np.sqrt(((p1 - p2) ** 2).sum()) / 2)
    exit()

ans = 10 ** 18
for p1, p2, p3 in combinations(points, 3):
    A = ((p2 - p3) ** 2).sum()
    B = ((p3 - p1) ** 2).sum()
    C = ((p1 - p2) ** 2).sum()
    sa, sb, sc = sorted([A, B, C])
    if sa + sb <= sc:
        c = (p2 + p3 if A == sc else p1 + p3 if B == sc else p1 + p2) / 2
        R2 = sc / 4
    else:
        T = A * (B + C - A)
        U = B * (C + A - B)
        W = C * (A + B - C)
        c = (T * p1 + U * p2 + W * p3) / (T + U + W)
        R2 = ((c - p1) ** 2).sum()
    if ((points - c) ** 2).sum(axis=1).max() <= R2:
        print(np.sqrt(R2))
        break
else:
    raise AssertionError
Problem p02840 (python)

Fixed submission:
from fractions import gcd
from itertools import accumulate

n, x, d = map(int, input().split())

if d == 0:
    if x == 0:
        print(1)
    else:
        print(n + 1)
    exit()
elif d < 0:
    x, d = -x, -d

g = gcd(x, d)
back_k = d // g
offset = x // g

lowers = [0] + list(accumulate(range(n)))
uppers = [0] + list(accumulate(range(n - 1, -1, -1)))
min_memo = [10 ** 18] * min(n + 1, back_k)
max_memo = [-(10 ** 18)] * min(n + 1, back_k)
# print(n, x, d, g, back_k, offset)
# print(lowers)
# print(uppers)

ans = 0
for k in range(n + 1):
    min_acc = lowers[k]
    max_acc = uppers[k]

    if k < back_k:
        min_memo[k] = min_acc - offset
        max_memo[k] = max_acc - offset
        ans += max_acc - min_acc + 1
        # print(k, ans, min_acc, max_acc, max_acc - min_acc + 1)
        continue

    kk = k % back_k
    back_min = min_memo[kk]
    back_max = max_memo[kk]

    if back_max < min_acc or max_acc < back_min:
        min_memo[kk] = min_acc - offset
        max_memo[kk] = max_acc - offset
        ans += max_acc - min_acc + 1
    else:
        current = max_acc - min_acc + 1
        duplicated = min(max_acc, back_max) - max(min_acc, back_min) + 1
        ans += current - duplicated
        min_memo[kk] = min(min_acc, back_min) - offset
        max_memo[kk] = max(max_acc, back_max) - offset

    # print(k, ans, min_acc, max_acc, back_min, back_max)

print(ans)

Buggy submission (verdict: Runtime Error):
from fractions import gcd
from itertools import accumulate

n, x, d = map(int, input().split())
g = gcd(x, d)
back_k = d // g
offset = x // g

min_memo = [0] + list(accumulate(range(n)))
max_memo = [0] + list(accumulate(range(n - 1, -1, -1)))

ans = 0
for k in range(n + 1):
    min_acc = min_memo[k]
    max_acc = max_memo[k]

    if k < back_k:
        ans += max_acc - min_acc + 1
        continue

    back_max = max_memo[k - back_k] - offset
    ans += max_acc - max(min_acc - 1, back_max)

print(ans)

Buggy submission (verdict: Runtime Error):
from fractions import gcd
from itertools import accumulate

n, x, d = map(int, input().split())
g = gcd(x, d)
back_k = d // g
offset = x // g

min_memo = [0] + list(accumulate(range(n)))
max_memo = [0] + list(accumulate(range(n - 1, -1, -1)))
ans = 1
# print(back_k, offset)
# print(min_memo)
# print(max_memo)

for k in range(1, n + 1):
    min_acc = min_memo[k]
    max_acc = max_memo[k]

    if k < back_k:
        ans += max_acc - min_acc + 1
        continue

    back_min = min_memo[k - back_k] - offset
    back_max = max_memo[k - back_k] - offset
    ans += max_acc - max(min_acc, back_max) + 1
    # print(ans, min_acc, max_acc, back_min, back_max)

print(ans)