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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

D = INT()
C = LIST()
S = [[]] * D
for i in range(D):
    S[i]  = LIST()
T = [t-1 for t in LIST(D)]
M = 26

def check(T):
    last = [0] * M
    res = 0
    for i, t in enumerate(T):
        res += S[i][t]
        for j in range(M):
            last[j] += 1
        last[t] = 0
        for j in range(M):
            res -= C[j] * last[j]
    return res

Q = INT()
for i in range(Q):
    d, q = MAP()
    d -= 1; q -= 1

    T[d] = q
    res = check(T)
    print(res)


Fixed submission:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

D = INT()
C = LIST()
S = [[]] * D
for i in range(D):
    S[i]  = LIST()
T = [t-1 for t in LIST(D)]
M = 26

last = list2d(M, D+2, 0)
def check(T):
    score = 0
    for i, t in enumerate(T):
        score += S[i][t]
        for j in range(M):
            last[j][i+1] = last[j][i] + 1
        last[t][i+1] = 0
        for j in range(M):
            score -= C[j] * last[j][i+1]
    return score

def change(day, a, b):
    nxtday = last[a].index(0, day+2)
    w = nxtday - day - 1
    h = last[a][day] + 1
    a_change = C[a] * h * w
    for d in range(day, nxtday-1):
        last[a][d+1] = last[a][d] + 1

    nxtday = last[b].index(0, day+2)
    w = nxtday - day - 1
    h = last[b][day] + 1
    b_change = C[b] * h * w
    last[b][day+1] = 0
    for d in range(day+1, nxtday-1):
        last[b][d+1] = last[b][d] + 1

    res = -a_change + b_change - S[day][a] + S[day][b]
    return res

score = check(T)
Q = INT()
for i in range(Q):
    d, q = MAP()
    d -= 1; q -= 1

    prev = T[d]
    nxt = q
    score += change(d, prev, nxt)
    print(score)
    T[d] = q
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

ans = 1
for a in A:
    ans *= a
if ans > 10**18:
    print(-1)
else:
    print(ans)


Fixed submission:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

if A.count(0):
    print(0)
    exit()

ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

N, S = MAP()
A = LIST()

dp = list2d(N+1, S+1, 0)
dp[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j+a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
ans = dp[N][S]
print(ans)


Fixed submission:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

N, K = MAP()
A = LIST()

dp = list2d(N+1, K+1, 0)
dp[0][0] = 1
for i, a in enumerate(A):
    for j in range(K+1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j+a <= K:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
ans = dp[N][K]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = [a-1 for a in LIST()]

MAX = 64
nxt = list2d(MAX, N, -1)
for i, a in enumerate(A):
    nxt[0][i] = a

for k in range(1, MAX):
    for i in range(N):
        nxt[k][i] = nxt[k-1][nxt[k-1][i]]

ans = 0
for k in range(MAX-1, -1, -1):
    if K >> k & 1:
        ans = nxt[k][ans]
print(ans+1)


Fixed submission:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = [a-1 for a in LIST()]

MAX = 64
nxt = list2d(MAX, N, -1)
for i, a in enumerate(A):
    nxt[0][i] = a

for k in range(1, MAX):
    for i in range(N):
        nxt[k][i] = nxt[k-1][nxt[k-1][i]]

ans = 0
for k in range(MAX-1, -1, -1):
    if K >> k & 1:
        ans = nxt[k][ans]
print(ans+1)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

a, b, N = MAP()

ans = -INF
for x in range(N+1):
    ans = max(ans, a*x // b - a*(x//b))
print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

a, b, N = MAP()

# for x in range(N+1):
#     print(a*x // b - a*(x//b))

x = min(b-1, N)
ans = a*x // b - a*(x//b)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=1)

# dp[i][j] := 左にi人、右にj人確定した状態での最大値
dp = list2d(N+1, N+1, -INF)
dp[0][0] = 0
for i, (a, x) in enumerate(A):
    # j := 今左に確定してる人数
    for j in range(i+1):
        # k := 今右に確定してる人数
        k = i - j
        # このaを左にする遷移
        y = j
        dp[j+1][k] = max(dp[j+1][k], dp[j][k] + abs(x - y) * a)
        # このaを右にする遷移
        y = N - 1 - k
        dp[j][k+1] = max(dp[j][k+1], dp[j][k] + abs(x - y) * a)
ans = 0
for i in range(N+1):
    # 左右に計N人決まった状態での最大を取る
    ans = max(ans, dp[i][N-i])
print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=1)

# dp[i][j] := 左にi人、右にj人確定した状態での最大値
dp = list2d(N+1, N+1, -INF)
dp[0][0] = 0
for i, (a, x) in enumerate(A):
    # j := 今左に確定してる人数
    for j in range(i+1):
        # k := 今右に確定してる人数
        k = i - j
        # このaを左にする遷移
        y = j
        dp[j+1][k] = max(dp[j+1][k], dp[j][k] + abs(x - y) * a)
        # このaを右にする遷移
        y = N - 1 - k
        dp[j][k+1] = max(dp[j][k+1], dp[j][k] + abs(x - y) * a)
ans = 0
for i in range(N+1):
    # 左右に計N人決まった状態での最大を取る
    ans = max(ans, dp[i][N-i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
S = input()
A = [0] * N
for i, s in enumerate(S):
    if s == 'G':
        A[i] = 1
    elif s == 'B':
        A[i] = 2

acc = list2d(3, N, 0)
for i, a in enumerate(A):
    acc[a][i] = 1
for i in range(3):
    acc[i] = list(accumulate(acc[i][::-1]))[::-1]

ans = 0
for i, a1 in enumerate(A):
    for j in range(i+1, N):
        a2 = A[j]
        if a1 == a2:
            continue
        a3 = 3 - a1 - a2
        cnt = acc[a3][j]
        dist = j - i
        if j + dist < N and A[j+dist] == a3:
            cnt -= 1
        ans += cnt
print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
S = input()
A = [0] * N
for i, s in enumerate(S):
    if s == 'G':
        A[i] = 1
    elif s == 'B':
        A[i] = 2

acc = list2d(3, N, 0)
for i, a in enumerate(A):
    acc[a][i] = 1
for i in range(3):
    acc[i] = list(accumulate(acc[i][::-1]))[::-1]

ans = 0
for i, a1 in enumerate(A):
    for j in range(i+1, N):
        a2 = A[j]
        if a1 == a2:
            continue
        a3 = 3 - a1 - a2
        cnt = acc[a3][j]
        dist = j - i
        if j + dist < N and A[j+dist] == a3:
            cnt -= 1
        ans += cnt
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

# dp0[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使っていない時の最大値
dp0 = [defaultdict(lambda: -INF) for i in range(N+1)]
# dp1[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使った時の最大値
dp1 = [defaultdict(lambda: -INF) for i in range(N+1)]
dp0[0][0] = 0
for i, a in enumerate(A):
    for j in range(-2, 2):
        if j != -2:
            # 今回のaを使わない
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        # 今回のaを使う
        dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)
# 最終的に欲しい位置は偶奇で場合分け
if N % 2 == 0:
    # 偶数の時は使った数と使わなかった数が同じ
    ans = max(dp0[N][0], dp1[N][0])
else:
    # 奇数の時は使わなかった数が1つ多い
    ans = max(dp0[N][-1], dp1[N][-1])
print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

# dp0[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使っていない時の最大値
dp0 = [defaultdict(lambda: -INF) for i in range(N+1)]
# dp1[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使った時の最大値
dp1 = [defaultdict(lambda: -INF) for i in range(N+1)]
dp0[0][0] = 0
for i, a in enumerate(A):
    for j in range(-2, 2):
        if j != -2:
            # 今回のaを使わない
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        # 今回のaを使う
        dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)
# 最終的に欲しい位置は偶奇で場合分け
if N % 2 == 0:
    # 偶数の時は使った数と使わなかった数が同じ
    ans = max(dp0[N][0], dp1[N][0])
else:
    # 奇数の時は使わなかった数が1つ多い
    ans = max(dp0[N][-1], dp1[N][-1])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, x, y = MAP()
x -= 1; y -= 1

G = list2d(N, N, 0)
for i in range(N):
    for j in range(i+1, N):
        G[i][j] = min(j - i, abs(i - x) + abs(j - y) + 1, abs(j - x) + abs(i - y) + 1)
ans = [0] * N
for i in range(N):
    for j in range(i+1, N):
        ans[G[i][j]] += 1
[print(a) for a in ans[1:]]


Fixed submission:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(nodes, src):
    """ BFS(一般グラフ、重みなし) """
    from collections import deque

    N = len(nodes)
    que = deque([(src, 0)])
    dist = [INF] * N
    while que:
        u, c = que.popleft()
        if dist[u] != INF:
            continue
        dist[u] = c
        for v in nodes[u]:
            que.append((v, c+1))
    return dist

N, x, y = MAP()
x -= 1; y -= 1

nodes = [[] for i in range(N)]
for i in range(N-1):
    nodes[i].append(i+1)
    nodes[i+1].append(i)
nodes[x].append(y)
nodes[y].append(x)

distx = bfs(nodes, x)
disty = bfs(nodes, y)

G = list2d(N, N, 0)
for i in range(N):
    for j in range(i+1, N):
        G[i][j] = min(j - i, distx[i] + disty[j] + 1, distx[j] + disty[i] + 1)
ans = [0] * N
for i in range(N):
    for j in range(i+1, N):
        ans[G[i][j]] += 1
[print(a) for a in ans[1:]]
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
# 下の桁から見ていく
S = S[::-1]
N = len(S)

# dp0[i] := 下からi桁目まで見た時の最小値(直前で繰り上げなし)
dp0 = [INF] * (N+1)
# dp1[i] := 下からi桁目まで見た時の最小値(直前で繰り上げあり)
dp1 = [INF] * (N+1)
dp0[0] = 0
for i, s in enumerate(S):
    s = int(s)
    # この桁で繰り上げない遷移
    dp0[i+1] = min(dp0[i+1], dp0[i] + s)
    dp0[i+1] = min(dp0[i+1], dp1[i] + (s+1))
    # この桁で繰り上げる遷移
    dp1[i+1] = min(dp1[i+1], dp0[i] + 10-s)
    dp1[i+1] = min(dp1[i+1], dp1[i] + 10-(s+1))
# 繰り上げる方は最後の繰り上げ分を足す
ans = min(dp0[N], dp1[N]+1)
print(ans)


Fixed submission:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
S = S[::-1]
N = len(S)

dp0 = [INF] * (N+1)
dp1 = [INF] * (N+1)
dp0[0] = 0
for i, s in enumerate(S):
    s = int(s)
    dp0[i+1] = min(dp0[i+1], dp0[i] + s)
    dp1[i+1] = min(dp1[i+1], dp0[i] + 10-s)
    dp0[i+1] = min(dp0[i+1], dp1[i] + (s+1))
    dp1[i+1] = min(dp1[i+1], dp1[i] + 10-(s+1))
ans = min(dp0[N], dp1[N]+1)
print(ans)