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

S_inv = S[::-1]

while(1):
    if S_inv=="":
        print("YES")
        sys.exit()
    
    elif len(S_inv)<=4:
        print("NO")
        sys.exit()
    
    elif len(S_inv)==5 and S_inv=="maerd":
        print("YES")
        sys.exit()
    
    elif len(S_inv)==5 and S_inv=="esare":
        print("YES")
        sys.exit()
    
    elif len(S_inv)==5 and (S_inv!="maerd" or S_inv!="esare"):
        print("NO")
        sys.exit()
        
    elif len(S_inv)==6 and S_inv!="resare":
        print("NO")
        sys.exit()
        
    elif len(S_inv)==7 and S_inv!="remaerd":
        print("NO")
        sys.exit()
        
    elif S_inv[:5] == "maerd":
        S_inv = S_inv[5:]
    
    elif S_inv[:5] == "esare":
        S_inv = S_inv[5:]
        
    elif S_inv[:6] == "resare":
        S_inv = S_inv[6:]
        
    elif S_inv[:7] == "remaerd":
        S_inv = S_inv[7:]
  

Fixed submission:
import re
s=input()
if re.search(r"^(dreamer|dream|erase|eraser)*$",s):
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Runtime Error):
import sys
sa=list(str(input()))
sb=list(str(input()))
sc=list(str(input()))

tmp="a"

while True:
    if tmp=="a":
        if len(sa)==0:
            print("A")
            sys.exit()
        else:
            tmp=sa[0]
            sa=sa.lstrip(sa[0])
    elif tmp=="b":
        if len(sb)==0:
            print("B")
            sys.exit()
        else:
            tmp=sb[0]
            sb=sb.lstrip(sb[0])
    elif tmp=="c":      
        if len(sc)==0:
            print("C")
            sys.exit()
        else:
            tmp=sc[0]
            sc=sc.lstrip(sc[0])

Fixed submission:
import sys
sa=list(str(input()))
sb=list(str(input()))
sc=list(str(input()))

tmp="a"

while True:
    if tmp=="a":
        if len(sa)==0:
            print("A")
            sys.exit()
        else:
            tmp=sa[0]
            sa.pop(0)
    elif tmp=="b":
        if len(sb)==0:
            print("B")
            sys.exit()
        else:
            tmp=sb[0]
            sb.pop(0)
    elif tmp=="c":      
        if len(sc)==0:
            print("C")
            sys.exit()
        else:
            tmp=sc[0]
            sc.pop(0)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
input = sys.stdin.readline

R,C,K = map(int,input().split())

tb = np.zeros((R+1,C+1),dtype=np.int32)
dp = np.zeros((C+1,4),dtype=np.int64)
prev = np.zeros(C+1,dtype=np.int64)

for i in range(K):
    r,c,v = map(int,input().split())
    tb[r][c] = v

for i in range(1,R+1):
    for j in range(1,C+1):
        for k in range(4):
            dp[j][k] = dp[j-1][k]
            if k > 0:
                dp[j][k] = max(dp[j][k],dp[j-1][k-1]+tb[i][j])
            if k == 0:
                dp[j][k] = max(dp[j][k],prev[j])
            elif k == 1:
                dp[j][k] = max(dp[j][k],prev[j]+tb[i][j])
    prev = np.max(dp,axis=1)

print(prev[C])


Fixed submission:
import sys
input = sys.stdin.readline

R,C,K = map(int,input().split())

dp = [[0]*4 for i in range(C+1)]
prev = [0]*(C+1)
tb = [[0]*(C+1) for i in range(R+1)]

for i in range(K):
    r,c,v = map(int,input().split())
    tb[r][c] = v

for i in range(1,R+1):
    for j in range(1,C+1):
        pmx = 0
        for k in range(4):
            mx = dp[j-1][k]
            if k > 0:
                mx = max(mx,dp[j-1][k-1]+tb[i][j])
            if k == 0:
                mx = max(mx,prev[j])
            elif k == 1:
                mx = max(mx,prev[j]+tb[i][j])
            dp[j][k] = mx
            pmx = max(pmx,mx)
        prev[j] = pmx

print(prev[C])

Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
input = sys.stdin.readline

R,C,K = map(int,input().split())

tb = np.zeros((R+1,C+1),dtype=np.int32)
dp = np.zeros((C+1,4),dtype=np.int64)
prev = np.zeros(C+1,dtype=np.int64)

for i in range(K):
    r,c,v = map(int,input().split())
    tb[r][c] = v

for i in range(1,R+1):
    for j in range(1,C+1):
        for k in range(4):
            dp[j][k] = dp[j-1][k]
            if k > 0:
                dp[j][k] = max(dp[j][k],dp[j-1][k-1]+tb[i][j])
            if k == 0:
                dp[j][k] = max(dp[j][k],prev[j])
            elif k == 1:
                dp[j][k] = max(dp[j][k],prev[j]+tb[i][j])
    prev = np.max(dp,axis=1)

print(prev[C])


Fixed submission:
import sys
input = sys.stdin.readline

R,C,K = map(int,input().split())

dp = [[0]*4 for i in range(C+1)]
prev = [0]*(C+1)
tb = [[0]*(C+1) for i in range(R+1)]

for i in range(K):
    r,c,v = map(int,input().split())
    tb[r][c] = v

for i in range(1,R+1):
    for j in range(1,C+1):
        pmx = 0
        for k in range(4):
            mx = dp[j-1][k]
            if k > 0:
                mx = max(mx,dp[j-1][k-1]+tb[i][j])
            if k == 0:
                mx = max(mx,prev[j])
            elif k == 1:
                mx = max(mx,prev[j]+tb[i][j])
            dp[j][k] = mx
            pmx = max(pmx,mx)
        prev[j] = pmx

print(prev[C])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

class DisjointSetUnion():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n

    def merge(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]: x, y = y, x
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        while self.par_size[x] >= 0:
            x = self.par_size[x]
        while self.par_size[a] >= 0:
            self.par_size[a] = x
            a = self.par_size[a]
        return x

    def size(self, a):
        #assert 0 <= a < self.n
        return -self.par_size[self.leader(a)]

    def groups(self):
        leader_buf = [0] * self.n
        group_size = [0] * self.n
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            leader_buf[i] = self.leader(i)
            group_size[leader_buf[i]] += 1
        for i in range(self.n):
            res[leader_buf[i]].append(i)
        res = [res[i] for i in range(self.n) if res[i]]
        return res

uf = DisjointSetUnion(N)

for _ in range(M):
    a, b = map(int, input().split())
    uf.merge(a, b)

l = len(uf.groups())
print(l - 1)

Fixed submission:
N, M = map(int, input().split())

class DisjointSetUnion():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n

    def merge(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]: x, y = y, x
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        while self.par_size[x] >= 0:
            x = self.par_size[x]
        while self.par_size[a] >= 0:
            self.par_size[a] = x
            a = self.par_size[a]
        return x

    def size(self, a):
        #assert 0 <= a < self.n
        return -self.par_size[self.leader(a)]

    def groups(self):
        leader_buf = [0] * self.n
        group_size = [0] * self.n
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            leader_buf[i] = self.leader(i)
            group_size[leader_buf[i]] += 1
        for i in range(self.n):
            res[leader_buf[i]].append(i)
        res = [res[i] for i in range(self.n) if res[i]]
        return res

uf = DisjointSetUnion(N)

for _ in range(M):
    a, b = map(int, input().split())
    uf.merge(a - 1, b - 1)

l = len(uf.groups())
print(l - 1)
Buggy python submission (verdict: Runtime Error):
D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(D)]

res = 0
last = [0 for _ in range(26)]

for d in range(D):
    maxtmp = 0
    contest = None
    for i in range(26):
        tmp = res
        lasttmp = last[:]
        tmp += S[d][i]
        lasttmp[i] = d + 1
        for j in range(26):
            tmp -= C[j] * ((d + 1) - lasttmp[j])
        if maxtmp <= tmp:
            maxtmp = tmp
            contest = i
    res += S[d][contest]
    last[contest] = d + 1
    for j in range(26):
        res -= C[j] * ((d + 1) - last[j])
    print(contest + 1)

Fixed submission:
D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(D)]

res = 0
last = [0 for _ in range(26)]

for d in range(D):
    maxtmp = -10**18
    contest = None
    for i in range(26):
        tmp = res
        lasttmp = last[:]
        tmp += S[d][i]
        lasttmp[i] = d + 1
        for j in range(26):
            tmp -= C[j] * ((d + 1) - lasttmp[j])
        if maxtmp <= tmp:
            maxtmp = tmp
            contest = i
    res += S[d][contest]
    last[contest] = d + 1
    for j in range(26):
        res -= C[j] * ((d + 1) - last[j])
    print(contest + 1)
Buggy python submission (verdict: Time Limit Exceeded):
class BinaryIndexedTree(): #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

class RAQandRSQ(): #1-indexed, BinaryIndexedTree
    def __init__(self, n):
        self.bit1 = BinaryIndexedTree(n)
        self.bit2 = BinaryIndexedTree(n)

    def add(self, lt, rt, x):
        self.bit1.add(lt, -x * (lt - 1))
        self.bit1.add(rt, x * (rt - 1))
        self.bit2.add(lt, x)
        self.bit2.add(rt, -x)

    def sum(self, lt, rt):
        rsum = self.bit2.sum(rt - 1) * (rt - 1) + self.bit1.sum(rt - 1)
        lsum = self.bit2.sum(lt - 1) * (lt - 1) + self.bit1.sum(lt - 1)
        return rsum - lsum

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

R = RAQandRSQ(N)

for i in range(N):
    R.add(i + 1, i + 2, A[i])

for i in range(K):
    query = []
    for j in range(N):
        s = R.sum(j + 1, j + 2)
        query.append((max(1, j - s + 1), min(N + 1, j + s + 2)))
    R = RAQandRSQ(N + 1)
    for l, r in query:
        R.add(l, r, 1)
    flag = False
    for j in range(N):
        if R.sum(j + 1, j + 2) < N:
            flag = True
    if not flag:
        break

res = [min(R.sum(i + 1, i + 2), N) for i in range(N)]

print(*res)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

for i in range(K):
    P = [0 for _ in range(N)] + [0]
    for j in range(N):
        P[max(0, j - A[j])] += 1
        P[min(N, j + A[j] + 1)] -= 1
    A = [0 for _ in range(N)]
    for j in range(N):
        P[j + 1] += P[j]
    flag = False
    for j in range(N):
        A[j] = P[j]
        if A[j] < N:
            flag = True
    if not flag:
        break

print(*A)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(lambda x:int(x) - 1, input().split()))
res = list(range(N))
while K:
    if K & 1:
        res = [res[A[i]] for i in range(N)]
    A = [A[A[i]] for i in range(N)]
    K >>= 1
print(res[0] + 1)

Fixed submission:
N, K = map(int, input().split())
A = list(map(lambda x:int(x) - 1, input().split()))
res = list(range(N))
while K:
    if K & 1:
        res = [res[A[i]] for i in range(N)]
    A = [A[A[i]] for i in range(N)]
    K >>= 1
print(res[0] + 1)
Buggy python submission (verdict: Time Limit Exceeded):
INF = 10**18

N, K, C = map(int, input().split())
S = input()

lt = [-INF for _ in range(K + 1)]
rt = [-INF for _ in range(K + 1)]

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[j] == 'o' and j - lt[i - 1] > C:
            lt[i] = j
            break

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[::-1][j] == 'o' and j - rt[i - 1] > C:
            rt[i] = j
            break

lt = lt[1:]
rt = rt[1:]
rt = [N - x - 1 for x in rt][::-1]

res = []

for i in range(K):
    if lt[i] == rt[i]:
        res.append(lt[i] + 1)

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

Fixed submission:
INF = 10**18

N, K, C = map(int, input().split())
S = input()

lt = [-INF for _ in range(K + 1)]
rt = [-INF for _ in range(K + 1)]

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[j] == 'o' and j - lt[i - 1] > C:
            lt[i] = j
            break

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[-1 - j] == 'o' and j - rt[i - 1] > C:
            rt[i] = j
            break

lt = lt[1:]
rt = rt[1:]
rt = [N - x - 1 for x in rt]
rt = rt[::-1]

res = []

for i in range(K):
    if lt[i] == rt[i]:
        res.append(lt[i] + 1)

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

Buggy python submission (verdict: Time Limit Exceeded):
INF = 10**18

N, K, C = map(int, input().split())
S = input()

lt = [-INF for _ in range(K + 1)]
rt = [-INF for _ in range(K + 1)]

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[j] == 'o' and j - lt[i - 1] > C:
            lt[i] = j
            break

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[::-1][j] == 'o' and j - rt[i - 1] > C:
            rt[i] = j
            break

lt = lt[1:]
rt = [N - x - 1 for x in rt[1:]][::-1]

for i in range(K):
    if lt[i] == rt[i]:
        print(lt[i] + 1)

Fixed submission:
INF = 10**18

N, K, C = map(int, input().split())
S = input()

lt = [-INF for _ in range(K + 1)]
rt = [-INF for _ in range(K + 1)]

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[j] == 'o' and j - lt[i - 1] > C:
            lt[i] = j
            break

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[-1 - j] == 'o' and j - rt[i - 1] > C:
            rt[i] = j
            break

lt = lt[1:]
rt = rt[1:]
rt = [N - x - 1 for x in rt]
rt = rt[::-1]

res = []

for i in range(K):
    if lt[i] == rt[i]:
        res.append(lt[i] + 1)

print('\n'.join(map(str, res)))
Buggy python submission (verdict: Time Limit Exceeded):
class FastModuloTransform():
    def __init__(self, omega, n, mod):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega, mod - 2, mod)

    def _bit_reverse_(self, d):
        n = len(d)
        ns = n >> 1
        nss = ns >> 1
        ns1 = ns + 1
        i = 0
        for j in range(0, ns, 2):
            if j < i:
                d[i], d[j] = d[j], d[i]
                d[i + ns1], d[j + ns1] = d[j + ns1], d[i + ns1]
            d[i + 1], d[j + ns] = d[j + ns], d[i + 1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d

    def _fmt_(self, A, base):
        halfpow = pow(base, self.n // 2, self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base, n, self.mod)
            wk = 1
            for j in range(m):
                for i in range(j, self.n, 2 * m):
                    U = A[i]
                    V = (A[i + m] * wk) % self.mod
                    A[i] = (U + V) % self.mod
                    A[i + m] = (U + V * halfpow) % self.mod
                wk = (wk * w) % self.mod
            m <<= 1
        return A

    def fmt(self, f):
        A = f + [0] * (self.n - len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A, self.omega)
        return F

    def ifmt(self, F):
        A = F + [0] * (self.n - len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n, self.mod - 2, self.mod)
        f = [(e * nrev) % self.mod for e in self._fmt_(A, self.rev)]
        return f

    def convolute(self, f, g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s * t) % self.mod for s, t in zip(F, G)]
        h = self.ifmt(H)
        return h

fmt = FastModuloTransform(299814, 2**13, 998244353)

MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))

F = [0]
res = 0

for i in range(N):
    F[0] += 1
    f = [0 for _ in range(A[i] + 1)]
    f[0] = 1
    f[-1] = 1
    F = fmt.convolute(F, f)
    F = F[:S + 1]
    res += F[S]
    res %= MOD

print(res)

Fixed submission:
MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))

F = [0 for _ in range(S + 1)]
res = 0

for i in range(N):
    F[0] += 1
    for j in range(S + 1)[::-1]:
        if j - A[i] >= 0:
            F[j] += F[j - A[i]]
    res += F[S]
    res %= MOD

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))

F = [0 for _ in range(S + 1)]
res = 0

for i in range(N):
    F[0] += 1
    for j in range(S + 1)[::-1]:
        if j - A[i] >= 0:
            F[j] += F[j - A[i]]
    res += F[S]
    res %= MOD

print(res)

Fixed submission:
MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))

F = [0 for _ in range(S + 1)]
res = 0

for i in range(N):
    F[0] += 1
    for j in range(S + 1)[::-1]:
        if j - A[i] >= 0:
            F[j] += F[j - A[i]]
    res += F[S]
    res %= MOD

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

N = int(input())
ans = []

for p in permutations(range(N)):
    D = [-1] * N
    A = []
    for i in range(N):
        for j in range(N):
            if D[j] < p[i]:
                D[j] = p[i]
                A.append(j)
                break
    ans.append(tuple(A))

ans = sorted(set(ans))

for a in ans:
    s = ''.join(map(lambda x:chr(x+97),a))
    print(s)

Fixed submission:
N = int(input())

def f(s):
    if len(s) == N:
        print(s)
        return
    for i in range(97, ord(max(list(s)))+1+1):
        ns = s + chr(i)
        f(ns)

f('a')
Buggy python submission (verdict: Runtime Error):
from collections import Counter
import sys
if sys.platform == 'ios' or 'darwin':
    sys.stdin = open('input_file.txt')

N, P = map(int, input().split())
S = input()

ans = 0

if P == 2 or P == 5:
    for i in range(N):
        if int(S[-1 - i]) % 2 == 0:
            ans += N - i
else:
    M = []
    cum = [0]

    for i in range(N):
        M.append(pow(10, i, P) * int(S[-1 - i]) % P)

    for i in range(N):
        cum.append((cum[-1] + M[i]) % P)

    C = Counter(cum)

    for v in C.values():
        ans += v * (v - 1) // 2

print(ans)

Fixed submission:
from collections import Counter

N, P = map(int, input().split())
S = input()

ans = 0

if P == 2 or P == 5:
    for i in range(N):
        if int(S[-1 - i]) % P == 0:
            ans += N - i
else:
    M = []
    cum = [0]

    for i in range(N):
        M.append(pow(10, i, P) * int(S[-1 - i]) % P)

    for i in range(N):
        cum.append((cum[-1] + M[i]) % P)

    C = Counter(cum)

    for v in C.values():
        ans += v * (v - 1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
INF = 10**18
MOD = 998244353

N = int(input())
robots = [(-INF, INF)]

for _ in range(N):
    x, d = map(int, input().split())
    robots.append((x, x + d))

robots.sort()
stack = list()

tree = [[] for _ in range(N + 1)]

for i in range(N + 1)[::-1]:
    x, r = robots[i]
    while stack and stack[-1][0] < r:
        y, j = stack.pop()
        tree[i].append(j)
    stack.append((x, i))

stack = list()
stack.append(0)

order = [None for _ in range(N + 1)]
order[0] = (0, 0)
od = 0

while stack:
    node = stack.pop()
    for adj in tree[node]:
        if order[adj] is None:
            od += 1
            order[adj] = (od, adj)
            stack.append(adj)

order.sort()
dp = [1 for _ in range(N + 1)]

for od, node in order[::-1]:
    for adj in tree[node]:
        dp[node] *= dp[adj]
    dp[node] += 1
    dp[node] %= MOD

print(dp[0] - 1)

Fixed submission:
INF = 10**18
MOD = 998244353

N = int(input())
robots = [(-INF, INF)]

for _ in range(N):
    x, d = map(int, input().split())
    robots.append((x, x + d))

robots.sort()
stack = list()

tree = [[] for _ in range(N + 1)]

for i in range(N + 1)[::-1]:
    x, r = robots[i]
    while stack and stack[-1][0] < r:
        y, j = stack.pop()
        tree[i].append(j)
    stack.append((x, i))

stack = list()
stack.append(0)

visited = [0 for _ in range(N + 1)]
visited[0] = 1
order = [None for _ in range(N + 1)]
order[0] = 0
od = 0

while stack:
    node = stack.pop()
    for adj in tree[node]:
        if not visited[adj]:
            visited[adj] = 1
            od += 1
            order[od] = adj
            stack.append(adj)

dp = [1 for _ in range(N + 1)]

for node in order[::-1]:
    for adj in tree[node]:
        dp[node] *= dp[adj]
    dp[node] += 1
    dp[node] %= MOD

print(dp[0] - 1)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache
g = [0,1,2,3,4,5,6,7,8,9,1]
import sys
sys.setrecursionlimit(1000000000)
@lru_cache(maxsize=None)
def solve(i,j):
    if i<0:
        if j==0:
            return 0
        else:
            return 1
    res = 10**18
    for d in range(10):
        n = int(N[i])+j
        sm = g[d]
        if d<n:
            sm += solve(i-1,1)+g[10+d-n]
        else:
            sm += solve(i-1,0)+g[d-n]
        res = min(res,sm)
    return res

N = input()
print(solve(len(N)-1,0))

Fixed submission:
INF = 10**18

S = '0'+input()
N = len(S)

dp = [[INF,INF] for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(2):
        s = int(S[-1-i])
        s += j

        for a in range(10):
            ni = i+1
            nj = 0
            b = a-s
            if b < 0:
                b += 10
                nj = 1
            dp[ni][nj] = min(dp[ni][nj],dp[i][j]+a+b)

print(dp[N][0])
Buggy python submission (verdict: Time Limit Exceeded):
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
            self.inv[i+1] = self.inv[i]*pow(i+1,mod-2,mod)%mod
    def comb(self,m,k): #組み合わせ 0<=k<=m<=n
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod
    def fact(self,m): #階乗
        return self.factorial[m]
    def perm(self,m,k): #順列
        if m < k: return 0
        return self.factorial[m]*self.inv[m-k]%self.mod
    def invfact(self,m): #階乗の逆数
        return self.inv[m]

MOD = 1000000007

r1,c1,r2,c2 = map(int,input().split())

f = Factorial(2000010,MOD)

ans = 0

for i in range(r2-r1+1):
    ans += f.comb(r1+c2+i+1,r1+i+1)-f.comb(r1+c1+i,r1+i+1)
    ans %= MOD

print(ans)

Fixed submission:
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod


    def comb(self,m,k): #組み合わせ 0<=k<=m<=n
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod

def solve():

    MOD = 1000000007

    r1,c1,r2,c2 = map(int,input().split())

    f = Factorial(2000010,MOD)

    ans = 0

    for i in range(r2-r1+1):
        ans += f.comb(r1+c2+i+1,r1+i+1)-f.comb(r1+c1+i,r1+i+1)
        ans %= MOD

    print(ans)

solve()