Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#UnionFindクラス
class UnionFind(object):

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

  def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

n,k,l = map(int,input().split())
    
uf_road = UnionFind(n)
uf_rail = UnionFind(n)
for i in range(k):
  tmp1,tmp2 = map(int,input().split())
  uf_road.union(tmp1-1,tmp2-1)
  
for i in range(l):
  tmp1,tmp2 = map(int,input().split())
  uf_rail.union(tmp1-1,tmp2-1)

li = [[0]*n for i in range(n)]  
for i in range(n):
  li[uf_rail.find(i)][uf_road.find(i)] +=1

for i in range(n):
  print(li[uf_rail.find(i)][uf_road.find(i)],end=" ")
print()

Fixed submission:
#UnionFindクラス
class UnionFind(object):

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

  def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

n,k,l = map(int,input().split())
    
uf_road = UnionFind(n)
uf_rail = UnionFind(n)
for i in range(k):
  tmp1,tmp2 = map(int,input().split())
  uf_road.union(tmp1-1,tmp2-1)
  
for i in range(l):
  tmp1,tmp2 = map(int,input().split())
  uf_rail.union(tmp1-1,tmp2-1)

memo = {}
for i in range(n):
  if str(uf_rail.find(i))+" "+str(uf_road.find(i)) not in memo:
    memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))] = 1
  else:
    memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))] += 1

for i in range(n):
  print(memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))])
Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())

if max(a,b,c) == sum(a,b,c) - max(a,b,c):
  print("Yes")
else:
  print("No")

Fixed submission:
a,b,c = map(int,input().split())

if max(a,b,c) == a+b+c - max(a,b,c):
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
h,w,n = map(int,input().split())
coord = [list(map(int,input().split())) for i in range(n)]

num = {}

for i in range(n):
  for j,k in [[0,0],[0,1],[0,-1],[1,0],[1,1],[1,-1],[-1,0],[-1,1],[-1,-1]]:
    if not(2<=coord[i][0]+j<=h-1) or not(2<=coord[i][1]+k<=w-1):
      continue
    if not coord[i][0]+j in num:
      num[coord[i][0]+j] = {}
    if not coord[i][1]+k in num[coord[i][0]+j]:
      num[coord[i][0]+j][coord[i][1]+k] = 1
    else:
      num[coord[i][0]+j][coord[i][1]+k] += 1

ans = [0]*9
for i in num:
  for value in num[i].values():
    ans[value] +=1

print((h-2)*(w-2)-sum(ans))
for i in range(1,9):
  print(ans[i])

Fixed submission:
h,w,n = map(int,input().split())
coord = [list(map(int,input().split())) for i in range(n)]

num = {}

for i in range(n):
  for j,k in [[0,0],[0,1],[0,-1],[1,0],[1,1],[1,-1],[-1,0],[-1,1],[-1,-1]]:
    if not(2<=coord[i][0]+j<=h-1) or not(2<=coord[i][1]+k<=w-1):
      continue
    if not coord[i][0]+j in num:
      num[coord[i][0]+j] = {}
    if not coord[i][1]+k in num[coord[i][0]+j]:
      num[coord[i][0]+j][coord[i][1]+k] = 1
    else:
      num[coord[i][0]+j][coord[i][1]+k] += 1

ans = [0]*10
for i in num:
  for value in num[i].values():
    ans[value] +=1

print((h-2)*(w-2)-sum(ans))
for i in range(1,10):
  print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
n,x = map(int,input().split())
a = list(map(int,input().split()))

#p[i色のスライム][j回まで色を変えられる]=色変えのコストを含まない最小コスト
p = [[0]*n for i in range(n)]
cnt = [[0]*n for i in range(n)]
#print(p)
for i in range(n):
  p[i][0]=a[i]
  for j in range(1,n):
    if i-j>=0:
      p[i][j]=min(a[i-j],p[i][j-1])
    elif i-j == -1:
      p[i][j]=min(a[n-1],p[i][j-1])
    else:  
      p[i][j]=min(a[n-(j-i)],p[i][j-1])
p = list(zip(*p))
ans = sum(p[0])
for i in range(1,n):
  ans = min(ans,sum(p[i])+x*i)
print(ans)

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

#p[i色のスライム][j回まで色を変えられる]=色変えのコストを含まない最小コスト
p = [[0]*n for i in range(n)]

#print(p)
for i in range(n):
  p[i][0]=a[i]
  for j in range(1,n):
    if i-j>=0:
      p[i][j]=min(a[i-j],p[i][j-1])
    elif i-j == -1:
      p[i][j]=min(a[n-1],p[i][j-1])
    else:  
      p[i][j]=min(a[n-(j-i)],p[i][j-1])
p = list(zip(*p))
ans = sum(p[0])
for i in range(1,n):
  ans = min(ans,sum(p[i])+x*i)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,a = map(int,input().split())
x = list(map(int,input().split()))
x= sorted(x)
sho = sum(x)//a
dp = [[[[0]*(sho+1) for _ in range(a)]for _ in range(n+1)] for _ in range(n+1)]
#dp[i枚目まで選ぶ][選んだ枚数][aで割ったときの余り][aで割った商]=通り数

dp[0][0][0][0]=1 #何も選ばない

for i in range(0,n):
  j = x[i]%a
  kuwaeru = x[i]//a
  num = 0
  while num<=i:
    for k in range(a):
      for l in range(sho+1):
        if k+j<a and l+kuwaeru <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru] += dp[i][num][k][l]  #i番目のカードを選ぶ
        elif k+j>=a and l+kuwaeru+1 <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru+1] += dp[i][num][k][l]  #i番目のカードを選ぶ
  
        dp[i+1][num][k][l] += dp[i][num][k][l]  #i番目のカードを選ばない
    num +=1

ans = 0
for i in range(1,min(sho+1,n+1)):
  ans +=  dp[n][i][0][i]
print(ans)

Fixed submission:
n,a = map(int,input().split())
x = list(map(int,input().split()))
x= sorted(x)
sho = sum(x)//a
dp = [[[[0]*(sho+1) for _ in range(a)]for _ in range(n+1)] for _ in range(n+1)]
#dp[i枚目まで選ぶ][選んだ枚数][aで割ったときの余り][aで割った商]=通り数

dp[0][0][0][0]=1 #何も選ばない

for i in range(0,n):
  j = x[i]%a
  kuwaeru = x[i]//a
  num = 0
  while num<=i:
    for k in range(a):
      for l in range(sho+1):
        if k+j<a and l+kuwaeru <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru] += dp[i][num][k][l]  #i番目のカードを選ぶ
        elif k+j>=a and l+kuwaeru+1 <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru+1] += dp[i][num][k][l]  #i番目のカードを選ぶ
  
        dp[i+1][num][k][l] += dp[i][num][k][l]  #i番目のカードを選ばない
    num +=1

ans = 0
for i in range(1,min(sho+1,n+1)):
  ans +=  dp[n][i][0][i]
print(ans)
Buggy python submission (verdict: Runtime Error):
def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n % b

n = int(input())
s = int(input())

for i in range(2, int(n**0.5) + 3):
    if f(i, n) == s:
        print(i)
        exit()

ans = 10**12
for k in range(1, int(n**0.5) + 3):
    if (n-s) % k != 0 or n-s < 0:
        continue
    b = (n-s)//k + 1
    if f(b, n) == s:
        ans = min(b, ans)

if ans != 10**12:
    print(ans)
else:
    print(-1)

Fixed submission:
def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n % b

n = int(input())
s = int(input())
if n == s:
    print(n + 1)
    exit()
    
for i in range(2, int(n**0.5) + 3):
    if f(i, n) == s:
        print(i)
        exit()

ans = 10**13
for k in range(1, int(n**0.5) + 3):
    if (n-s) % k != 0 or n-s < 0:
        continue
    b = (n-s)//k + 1
    if b == 1:
        continue
    if f(b, n) == s:
        ans = min(b, ans)

if ans != 10**13:
    print(ans)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
n,x = map(int,input().split())
a = list(map(int,input().split()))

#p[i色のスライム][j回まで色を変えられる]=色変えのコストを含まない最小コスト
p = [[0]*n for i in range(n)]

#print(p)
for i in range(n):
  p[i][0]=a[i]
  for j in range(1,n):
    if i-j>=0:
      p[i][j]=min(a[i-j],p[i][j-1])
    elif i-j == -1:
      p[i][j]=min(a[n-1],p[i][j-1])
    else:  
      p[i][j]=min(a[n-(j-i)],p[i][j-1])
p = list(zip(*p))
ans = sum(p[0])
for i in range(1,n):
  ans = min(ans,sum(p[i])+x*i)
print(ans)

Fixed submission:
n = int(input())
a = [int(input()) for i in range(n)]
ans = 0
for i in range(n-1):
  if a[i]>=2:
    ans += a[i]//2
    a[i] = a[i]%2
  if a[i]==1:
    if a[i+1]>=1:
      ans += 1
      a[i] -= 1
      a[i+1] -=1
ans = ans +a[n-1]//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def get_anti_key(n: int):
    prime_factors = []
    for k in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while n % k == 0:
            cnt += 1
            n = n // k
        if cnt != 0:
            prime_factors.append((k, cnt))
    if n != 1:
        prime_factors.append((n, 1))
    anti_key = 1
    for key, cnt in prime_factors:
        anti_key *= key ** ((3 - cnt) % 3)
    return anti_key


n = int(input())
s = [int(input()) for i in range(n)]


# 立方数のリスト
pow3 = [i ** 3 for i in range(2, 50)]

# s[i] が立方数で割り切れるときは割る
for i in range(n):
    for div in pow3:
        while s[i] % div == 0:
            s[i] //= div

# key: s[i], val: 個数
cnts = {}
for key in s:
    if key not in cnts:
        cnts[key] = 0
    cnts[key] += 1

# 例えば、key = (2 ** 2) * (5 ** 1) と key = (2 ** 1) * (5 ** 2) は
# 片方しか選べないので、 cnts[key]が大きい方を選ぶと得する
ans = 0
used = set([])
for key in cnts:
    if key == 1:
        ans += 1
        continue
    if key in used:
        continue
    anti_key = get_anti_key(key)
    used.add(anti_key)
    if anti_key in cnts:
        ans += max(cnts[anti_key], cnts[key])
    else:
        ans += cnts[key]

print(ans)

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


def make_prime_numbers(n):
    """n以下の素数を列挙したリストを出力する
    計算量: O(NloglogN)
    入出力例: 30 -> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    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(2 * i, n + 1, i):
            is_prime[j] = False
    prime_numbers = [i for i in range(n + 1) if is_prime[i]]
    return prime_numbers


n = int(input())
s = [int(input()) for i in range(n)]


primes = make_prime_numbers(int((10 ** 10) ** (1 / 3) + 20))
pow2 = set([i ** 2 for i in range(10 ** 5 + 10)])
to_anti = {}

# s[i] が立方数で割り切れるときは割る
for i in range(n):
    anti = 1
    tmp_s = s[i]
    for div in primes:
        cnt = 0
        while tmp_s % div == 0:
            tmp_s //= div
            cnt += 1
        mod_cnt = cnt % 3
        cnt = cnt - mod_cnt
        s[i] //= (div ** cnt)
        anti *= div ** ((3 - mod_cnt) % 3)
    if tmp_s in pow2:
        to_anti[s[i]] = anti * int(tmp_s ** 0.5)
    else:
        to_anti[s[i]] = anti * (tmp_s ** 2)

# key: s[i], val: 個数
cnts = {}
for key in s:
    if key not in cnts:
        cnts[key] = 0
    cnts[key] += 1

# 例えば、key = (2 ** 2) * (5 ** 1) と key = (2 ** 1) * (5 ** 2) は
# 片方しか選べないので、 cnts[key]が大きい方を選ぶと得する
ans = 0
used = set([])
for key in cnts:
    if key == 1:
        ans += 1
        continue
    if key in used:
        continue
    anti_key = to_anti[key]
    used.add(anti_key)
    if anti_key in cnts:
        ans += max(cnts[anti_key], cnts[key])
    else:
        ans += cnts[key]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()

for i in range(len(s)):
  for j in range(i,len(s)):
    if i !=j:
      li = {}
      for k in range(i,j+1):
        if s[k] not in li:
          li[s[k]] = 1
        else:
          li[s[k]] += 1
      if j-i+1 - max(li.values()) < max(li.values()):
        print(i+1,j+1)
        exit()
print(-1,-1)

Fixed submission:
s = input()

if len(s) == 2:
  if s[0]==s[1]:
    print(1,2)
    exit()
  else:
    print(-1,-1)
    exit()

for i in range(len(s)-2):
  if s[i]==s[i+1]:
    print(i+1,i+2)
    exit()
  if s[i]==s[i+2]:
    print(i+1,i+3)
    exit()
print(-1,-1)
Buggy python submission (verdict: Runtime Error):
a,b = map(int,input().split())

if a<=0 or 0<=b:
  print("Zero)
elif a<0:
  print("Positive" if abs(a-b)%2==1 else "Negative")
else:
  print("Positive")

Fixed submission:
a,b = map(int,input().split())

if a<=0 and 0<=b:
  print("Zero")
elif a<0:
  print("Positive" if abs(a-b)%2==1 else "Negative")
else:
  print("Positive")
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
alst = list(map(int, input().split()))

if k == 0:
    print(max(alst))
    exit()

l = 0
r = max(alst)

while r != l:
    pos = (r + l) // 2
    cnt = 0
    for a in alst:
        cnt += (a - 1) // pos
    if cnt <= k:
        r = pos
    else:
        l = pos + 1
print(r)

Fixed submission:
n, k = map(int, input().split())
alst = list(map(int, input().split()))

if k == 0:
    print(max(alst))
    exit()

l = 1
r = max(alst)

while r != l:
    pos = (r + l) // 2
    cnt = 0
    for a in alst:
        cnt += (a - 1) // pos
    if cnt <= k:
        r = pos
    else:
        l = pos + 1
print(r)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
alst = list(map(int, input().split()))

l = 0
r = max(alst)

while r != l:
    pos = (r + l) // 2
    cnt = 0
    for a in alst:
        cnt += (a - 1) // pos
    if cnt <= k:
        r = pos
    else:
        l = pos + 1
print(r)

Fixed submission:
n, k = map(int, input().split())
alst = list(map(int, input().split()))

if k == 0:
    print(max(alst))
    exit()

l = 1
r = max(alst)

while r != l:
    pos = (r + l) // 2
    cnt = 0
    for a in alst:
        cnt += (a - 1) // pos
    if cnt <= k:
        r = pos
    else:
        l = pos + 1
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
import time, random
now = time.time()

d = int(input())
clst = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
last = [0 for _ in range(26)]

def score_minus(d, q):
    minus = 0
    for i, (c, ls) in enumerate(zip(clst, last)):
        if i == q:
            continue
        minus += c * (d + 1 - ls)
    return minus

def check(t):
    def score_minus(d):
        minus = 0
        for c, ls in zip(clst, last):
            minus += c * (d - ls)
        return minus
        
    last = [0 for _ in range(26)]
    ans = 0
    for d, num in enumerate(t, start = 1):
        ans += s[d - 1][num - 1]
        last[num - 1] = d
        ans -= score_minus(d)
    return ans
    
t_lst = []
for i in range(d):
    tmp = -10 ** 10
    for q in range(26):
        tmp_score = s[i][q] - score_minus(i, q)
        if tmp_score > tmp:
            tmp = tmp_score
            max_q = q
    last[max_q] = i
    t_lst.append(max_q + 1)

ans = check(t_lst)

while time.time() - now < 1.9:
    d_change = random.randint(0, d - 1)
    q_change = random.randint(1, 26)
    old_d = t_lst[d_change]
    if old_d == q_change:
        continue
    t_lst[d_change]  = q_change
    ans_tmp = check(t_lst)
    if ans_tmp > ans:
        ans = ans_tmp
    else:
        t_lst[d_change] = old_d

for t in t_lst:
    print(t)


Fixed submission:
d = int(input())
clst = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
last = [0 for _ in range(26)]

def score_minus(d, q):
    minus = 0
    for c, ls in zip(clst, last):
        minus += c * (d - ls)
    minus -= clst[q] * (d - last[q])
    return minus
    
ans = 0
for i in range(d):
    tmp = 0
    for q in range(26):
        tmp_score = s[i][q] - score_minus(i, q)
        if tmp_score > tmp:
            tmp = tmp_score
            max_q = q
    print(max_q + 1)
    last[max_q] = i
Buggy python submission (verdict: Runtime Error):
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

if alst.count(1) == n:
    if n % 2 == 0:
        print(0)
    else:
        print(-1)
    exit()
    
if alst.count(1) == n - 1:
    if n % 2 == 1:
        print(0)
    else:
        print(-1)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()

if alst[0] == 1:
    if xor == alst[0] ^ alst[1]:
        print(0)
    else:
        print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) < alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans >= alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Fixed submission:
n, m = map(int, input().split())

N = m + 100
MOD = 10 ** 9 + 7
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = i * fact[i - 1] % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
    
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD
        
def nPk(n, k):
    return fact[n] * invfact[n - k] % MOD
    
ans = 0
sign = 1

for i in range(n + 1):
    ans = (ans + nPk(m, i) * nCk(n, i) * nPk(m - i, n - i) ** 2 * sign) % MOD
    sign *= -1
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
s = input()

l = len(s)

N = k + l + 100
MOD = 10 ** 9 + 7
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = i * fact[i - 1] % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
    
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD

ex_25 = [0 for _ in range(N)]
ex_26 = [0 for _ in range(N)]
ex_25[0] = 1
ex_26[0] = 1
for i in range(1, N):
    ex_25[i] = ex_25[i - 1] * 25 % MOD
    ex_26[i] = ex_26[i - 1] * 26 % MOD

ans = 0
for i in range(k + 1):
    ans += ex_25[i] * ex_26[k - i] * nCk(i + l - 1, i)
    ans %= MOD
    
print(ans)
    

Fixed submission:
k = int(input())
s = input()

l = len(s)

N = k + l + 100
MOD = 10 ** 9 + 7
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = i * fact[i - 1] % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
    
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD

ex_25 = [0 for _ in range(N)]
ex_26 = [0 for _ in range(N)]
ex_25[0] = 1
ex_26[0] = 1
for i in range(1, N):
    ex_25[i] = ex_25[i - 1] * 25 % MOD
    ex_26[i] = ex_26[i - 1] * 26 % MOD

ans = 0
for i in range(k + 1):
    ans += ex_25[i] * ex_26[k - i] * nCk(i + l - 1, i)
    ans %= MOD
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, c, d = map(int, input().split())
mod = 998244353

dp = [[0 for _ in range(c - a + 1)] for _ in range(d - b + 1)]
dp[0][0] = 1
for j in range(c - a + 1):
    for i in range(d - b + 1):
        if i == j == 0:
            dp[i][j] = 1
        elif i == 0:
            dp[i][j] = dp[i][j - 1] * b % mod
        elif j == 0:
            dp[i][j] = dp[i - 1][j] * a % mod
        else:
            dp[i][j] = ((j + a - 1) * dp[i - 1][j] + (i + b - 1) * dp[i][j - 1] - dp[i - 1][j - 1] * (i + b - 1) * (j + a - 1) + dp[i - 1][j] + dp[i][j - 1]) % mod
print(dp[-1][-1])

Fixed submission:
a, b, c, d = map(int, input().split())
mod = 998244353

dp = [[0 for _ in range(c - a + 1)] for _ in range(d - b + 1)]
dp[0][0] = 1
for j in range(c - a + 1):
    for i in range(d - b + 1):
        if i == j == 0:
            dp[i][j] = 1
        elif i == 0:
            dp[i][j] = dp[i][j - 1] * b % mod
        elif j == 0:
            dp[i][j] = dp[i - 1][j] * a % mod
        else:
            tmp1 = (j + a - 1) * dp[i - 1][j] % mod
            tmp2 = (i + b - 1) * dp[i][j - 1] % mod
            tmp3 = -dp[i - 1][j - 1] * (i + b - 1) * (j + a - 1) % mod
            tmp4 = (dp[i - 1][j] + dp[i][j - 1]) % mod
            dp[i][j] = (tmp1 + tmp2 + tmp3 + tmp4) % mod
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
alst = list(map(int, input().split()))

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if tmp[0] == n and tmp[-1] == -n:
        break
print(*alst)

Fixed submission:
n, k = map(int, input().split())
alst = list(map(int, input().split()))

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if tmp[0] == n and tmp[-1] == -n:
        break
print(*alst)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
alst = list(map(int, input().split()))

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if min(alst) == n:
        break
print(*alst)

Fixed submission:
n, k = map(int, input().split())
alst = list(map(int, input().split()))

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if tmp[0] == n and tmp[-1] == -n:
        break
print(*alst)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from itertools import combinations_with_replacement
import sys
sys.setrecursionlimit(10 ** 9)

mod = 998244353

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

bin = [1]
for _ in range(n - 1):
    bin.append((bin[-1] * 2) % mod)
    
lst = []

zero = 0
for num in a:
    if num > s:
        continue
    if num == s:
        zero += 1
        continue
    lst.append(num % s)
lst.sort()
ans = (zero * bin[-1]) % mod
length = len(lst)

def knapsack(pos, total, num):
    global ans
    if total == s:
        ans = (ans + bin[-num]) % mod
        return
    if pos == length:
        return
    if total + lst[pos] <= s:
        knapsack(pos + 1, total + lst[pos], num + 1)
        knapsack(pos + 1, total, num)

knapsack(0, 0, 0)
print(ans)


Fixed submission:
mod = 998244353

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

dp = [[0 for _ in range(s + 1)] for _ in range(n + 1)]
dp[0][0] = 1
for i, num in enumerate(a, start = 1):
    for j in range(s + 1):
        dp[i][j] = (dp[i - 1][j] * 2) % mod
        if j - num >= 0:
            dp[i][j] += dp[i - 1][j - num]

print(dp[-1][-1] % mod)