Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
s = input().rstrip()
t = input().rstrip()
len_s = len(s)
len_t = len(t)

# Get longest LCS num
dp = [[0] * (len_t+1) for _ in range(len_s+1)]
for i in range(1, len_s+1):
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

# Restore LCS
h, w = len_s, len_t
ans = ""
while dp[h][w] != 0:
    while dp[h][w] == dp[h-1][w]:
        h -= 1
    while dp[h][w] == dp[h][w-1]:
        w -= 1
    h -= 1
    w -= 1
    ans += t[w]

print(ans[::-1])

Fixed submission:
s = input().rstrip()
t = input().rstrip()
len_s = len(s)
len_t = len(t)

# Get longest LCS num
dp = [[0] * (len_t+1) for _ in range(len_s+1)]
for i in range(1, len_s+1):
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

# Restore LCS
h, w = len_s, len_t
ans = ""
while dp[h][w] != 0:
    while dp[h][w] == dp[h-1][w]:
        h -= 1
    while dp[h][w] == dp[h][w-1]:
        w -= 1
    h -= 1
    w -= 1
    ans += t[w]

print(ans[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input().rstrip()
t = input().rstrip()
len_s = len(s)
len_t = len(t)
lcs = [[""] * (len_t+1) for _ in range(len_s+1)]
for i in range(1, len_s+1):
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1]:
            lcs[i][j] = lcs[i-1][j-1] + s[i-1]
        else:
            if len(lcs[i][j-1]) > len(lcs[i-1][j]):
                lcs[i][j] = lcs[i][j-1] 
            else:
                lcs[i][j] = lcs[i-1][j] 
print(lcs[-1][-1])

Fixed submission:
s = input().rstrip()
t = input().rstrip()
len_s = len(s)
len_t = len(t)

# Get longest LCS num
dp = [[0] * (len_t+1) for _ in range(len_s+1)]
for i in range(1, len_s+1):
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

# Restore LCS
h, w = len_s, len_t
ans = ""
while dp[h][w] != 0:
    while dp[h][w] == dp[h-1][w]:
        h -= 1
    while dp[h][w] == dp[h][w-1]:
        w -= 1
    h -= 1
    w -= 1
    ans += t[w]

print(ans[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, e = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
source_num = [0] * n
distance = [0] * n
for i in range(e):
    f, t = map(int, input().split())
    f -= 1
    t -= 1
    source_num[t] += 1
    edge[f].append(t)
while e > 0:
    for i, item in enumerate(source_num):
        if item != 0:
            continue
        source_num[i] = -1
        for v in edge[i]:
            distance[v] = max(distance[v], distance[i] + 1)
            source_num[v] -= 1
            e -= 1
print(max(distance))

Fixed submission:
from collections import deque
n, e = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
source_num = [0] * n
distance = [0] * n
for i in range(e):
    f, t = map(int, input().split())
    f -= 1
    t -= 1
    source_num[t] += 1
    edge[f].append(t)

dq = deque()
for i, item in enumerate(source_num):
    if item == 0:
        dq.append(i)
        source_num[i] = -1
while(dq):
    i = dq.pop()
    source_num[i] = -1
    for v in edge[i]:
        distance[v] = max(distance[v], distance[i] + 1)
        source_num[v] -= 1
        if source_num[v] == 0:
            dq.append(v)
print(max(distance))
Buggy python submission (verdict: Runtime Error):
INF = 10**9

class RMQ:
    def __init__(self, n):
        self.n = n 
        self.size = 2**(self.n - 1).bit_length()
        self.data = [INF] * (2*self.size-1)

    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n = int(input())
h_s = [int(item) for item in input().split()]
a_s = [int(item) for item in input().split()]

rmq = RMQ(10**5 + 10)
for i, (h, a) in enumerate(zip(h_s, a_s)):
    beaut = rmq.query(0, h)
    if beaut == INF:
        rmq.update(h-1, -a)
    else:
        rmq.update(h-1, beaut - a)

print(-rmq.data[0])

Fixed submission:
class RMQ:
    def __init__(self, n):
        self.n = n 
        self.size = 2**(self.n - 1).bit_length()
        self.data = [0] * (2*self.size-1)

    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n = int(input())
h = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

rmq = RMQ(2*10**5 + 10)
for i in range(n):
    beaut = rmq.query(0, h[i])
    rmq.update(h[i] - 1, beaut - a[i])
print(-rmq.data[0])
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
s = input().rstrip()

dp = [[0] * n for _ in range(n)]
dp[0] = [1] * n

used = 0
for i, ch in enumerate(s):
    if ch == "<":
        for j in range(n - used - 1, -1, -1):
            if j-1 >= 0:
                dp[i+1][j-1] = dp[i][j]
        for j in range(n - 1, 0, -1):
            dp[i+1][j-1] += dp[i+1][j]
            dp[i+1][j-1] %= MOD
    else:
        for j in range(n - used - 2, -1, -1):
            dp[i+1][j] = dp[i][j]
        for j in range(1, n - used - 1):
            dp[i+1][j] += dp[i+1][j-1]
            dp[i+1][j] %= MOD
    used += 1

# for line in dp:
#     print(line)
print(sum(dp[-1]) % MOD)

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
s = input().rstrip()

dp = [[0] * n for _ in range(n)]
dp[0] = [1] * n

used = 0
for i, ch in enumerate(s):
    if ch == "<":
        for j in range(n - used - 1, -1, -1):
            if j-1 >= 0:
                dp[i+1][j-1] = dp[i][j]
        for j in range(n - 1, 0, -1):
            dp[i+1][j-1] += dp[i+1][j]
            dp[i+1][j-1] %= MOD
    else:
        for j in range(n - used - 2, -1, -1):
            dp[i+1][j] = dp[i][j]
        for j in range(1, n - used - 1):
            dp[i+1][j] += dp[i+1][j-1]
            dp[i+1][j] %= MOD
    used += 1

# for line in dp:
#     print(line)
print(sum(dp[-1]) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
from itertools import combinations
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
cost = []
for i in range(n):
    cost.append([int(item) for item in input().split()])
score = [0] * 2**n
for i in range(1, 2**n):
    lsb = i & -i
    index = lsb.bit_length() - 1
    other = i ^ lsb
    diff = 0
    for j in range(n):
        if other & 1 << j:
            diff += cost[index][j]
    score[i] = score[other] + diff

memo = [-1] * 2**n
memo[0] = 0
for i in range(n):
    memo[1<<i] = 0

def dfs(st):
    if memo[st] != -1:
        return memo[st]
    sst = st
    val = score[st] 
    while True:
        sst = (sst - 1) & st
        if sst == 0:
            break
        val = max(val, dfs(sst) + dfs(sst ^ st))
    memo[st] = val
    return val

ret = dfs(2**n - 1)
print(ret)

Fixed submission:
#!/usr/bin/env python3
from itertools import combinations
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
cost = []
for i in range(n):
    cost.append([int(item) for item in input().split()])
score = [0] * 2**n
for i in range(1, 2**n):
    lsb = i & -i
    index = lsb.bit_length() - 1
    other = i ^ lsb
    diff = 0
    for j in range(n):
        if other & 1 << j:
            diff += cost[index][j]
    score[i] = score[other] + diff

memo = [-1] * 2**n
memo[0] = 0
for i in range(n):
    memo[1<<i] = 0

def dfs(st):
    if memo[st] != -1:
        return memo[st]
    sst = st
    val = score[st] 
    while True:
        sst = (sst - 1) & st
        if sst == 0:
            break
        val = max(val, dfs(sst) + dfs(sst ^ st))
    memo[st] = val
    return val

ret = dfs(2**n - 1)
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)

ans = 0
for item in a[::-1]:
    if ca[item] == 0:
        continue
    for i in range(31, 0, -1):
        inv = (1 << i) - item
        if inv < 0:
            continue
        if ca[inv] > 0 and item != inv:
            ans += 1 
            ca[inv] -=1
            ca[item] -=1
            break
        if ca[inv] > 1 and item == inv:
            ans += 1 
            ca[inv] -= 2
            break
print(ans)

Fixed submission:
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)
max_a = a[-1] 

ans = 0
for item in a[::-1]:
    if ca[item] == 0:
        continue
    for i in range(31, 0, -1):
        inv = (1 << i) - item
        if inv < 0 or inv > max_a:
            continue
        if item == inv:
            if ca[inv] > 1:
                ans += 1 
                ca[inv] -= 2
                break
        else:
            if ca[inv] > 0:
                ans += 1 
                ca[inv] -=1
                ca[item] -=1
                break
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
n, m = [int(item) for item in input().split()]

ans = 1
for i in range(1, int(math.sqrt(m))+1):
  if m%i == 0 
    if m >= i*n:
      ans = max(ans, i)
    else:
      ans = max(ans, m%i)
    
print(ans)

Fixed submission:
import math
n, m = [int(item) for item in input().split()]

ans = 0
for i in range(1, int(math.sqrt(m))+1):
  if m%i == 0:
    if m >= i*n:
      ans = max(ans, i)
    if i>= n:
      ans = max(ans, m//i)
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import collections
import math
n, m = [int(item) for item in input().split()]

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1
 
    return prime_count

cnt = trial_division_sqrt(m)

ans = 1
for item in cnt:
  ans *= int(math.factorial(n + cnt[item] - 1) // int(math.factorial(cnt[item]) * math.factorial(n-1)))
  ans = int(ans) % (1000000000 + 7)
print(ans)

Fixed submission:
import collections
import math
n, m = [int(item) for item in input().split()]

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1
    return prime_count

cnt = trial_division_sqrt(m)

ans = 1
for item in cnt:
  h = 1
  k_fact = 1
  for i in range(cnt[item]):
    h *= n + cnt[item] - 1 - i
    k_fact *= (i+1)
  ans *= h
  ans = ans // k_fact
  ans = ans % (1000000000 + 7)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import collections
import math
n, m = [int(item) for item in input().split()]

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return collections.Counter(table)

cnt = prime_decomposition(m)

ans = 1
for item in cnt:
  ans *= int(math.factorial(n + cnt[item] - 1) // int(math.factorial(cnt[item]) * math.factorial(n-1)))
  ans = int(ans) % (1000000000 + 7)
print(ans)

Fixed submission:
import collections
import math
n, m = [int(item) for item in input().split()]

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1
    return prime_count

cnt = trial_division_sqrt(m)

ans = 1
for item in cnt:
  h = 1
  k_fact = 1
  for i in range(cnt[item]):
    h *= n + cnt[item] - 1 - i
    k_fact *= (i+1)
  ans *= h
  ans = ans // k_fact
  ans = ans % (1000000000 + 7)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
a.sort(reverse=True)
# 1-indexed
cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i+1] = cumsum[i] + a[i]
coef = [0] * (n + 1)
for i in range(n + 1):
    coef[i] = (2 + i) ** 2 - (1 + i) ** 2
coef[0] += 2

ans = 10**18
for trip in range(1, n+1):
    collected = 0
    to_take = (n + trip - 1) // trip
    score = k * trip + k * n
    for i in range(to_take):
        val = cumsum[min((i+1) * trip, n)] - cumsum[i * trip]
        score += val * coef[i]
    ans = min(ans, score)
print(ans)

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

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
a.sort(reverse=True)
# 1-indexed
cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i+1] = cumsum[i] + a[i]
coef = [0] * (n + 1)
for i in range(n + 1):
    coef[i] = (2 + i) ** 2 - (1 + i) ** 2
coef[0] += 2

ans = 10**18
for trip in range(1, n+1):
    collected = 0
    to_take = (n + trip - 1) // trip
    score = k * trip + k * n
    for i in range(to_take):
        val = cumsum[min((i+1) * trip, n)] - cumsum[i * trip]
        score += val * coef[i]
    ans = min(ans, score)
print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect

N, K = [int(item) for item in input().split()]
x = [int(item) for item in input().split()]

sep = bisect.bisect(x, 0)

R = x[:sep][::-1] + [-10**7]
L = x[sep:] + [10**7]

for i in range(len(R)):
  R[i] = -R[i]
  
ans = 10**6
if K < len(R):
  ans = min(R[K-1], ans)
if K < len(L):
  ans = min(L[K-1], ans)
  
for i in range(len(R)):
  if K-(i+1)-1 >= 0 and len(L) is not 0:
    ans = min(ans, R[i]*2 + L[K-(i+1)-1])
for i in range(len(L)):
  if K-(i+1)-1 >= 0 and len(R) is not 0:
    ans = min(ans, L[i]*2 + R[K-(i+1)-1])
  
print(ans)

Fixed submission:
import bisect
n, k = [int(item) for item in input().split()]
x = [int(item) for item in input().split()]

lft_num = bisect.bisect(x, 0)
rgt_num = n - lft_num

ans = 10**10
for i in range(min(rgt_num, k)):
    r = x[lft_num + i]
    distance = abs(r)
    if i+1 == k: 
        ans = min(ans, distance)
        continue
    if lft_num - (k-i-1) >= 0:
        l = x[lft_num - (k-i-1)]
        distance += abs(r - l)
        ans = min(ans, distance)
for i in range(min(lft_num, k)):
    l = x[lft_num - i - 1]
    distance = abs(l)
    if i+1 == k: 
        ans = min(ans, distance)
        continue
    if lft_num + (k-i-2) < n:
        r = x[lft_num + (k-i-2)]
        distance += abs(r - l)
        ans = min(ans, distance)
    
print(ans)

Buggy python submission (verdict: Runtime Error):
import bisect

N, K = [int(item) for item in input().split()]
x = [int(item) for item in input().split()]

sep = bisect.bisect(x, 0)

R = x[:sep][::-1]
L = x[sep:]

for i in range(len(R)):
  R[i] = -R[i]

ans = 10**6
for i, r in enumerate(R):
  ans = min(ans, r*2+ L[K-(i+1)-1])
for i, l in enumerate(L):
  ans = min(ans, l*2+ R[K-(i+1)-1])
  
print(ans)

Fixed submission:
import bisect
n, k = [int(item) for item in input().split()]
x = [int(item) for item in input().split()]

lft_num = bisect.bisect(x, 0)
rgt_num = n - lft_num

ans = 10**10
for i in range(min(rgt_num, k)):
    r = x[lft_num + i]
    distance = abs(r)
    if i+1 == k: 
        ans = min(ans, distance)
        continue
    if lft_num - (k-i-1) >= 0:
        l = x[lft_num - (k-i-1)]
        distance += abs(r - l)
        ans = min(ans, distance)
for i in range(min(lft_num, k)):
    l = x[lft_num - i - 1]
    distance = abs(l)
    if i+1 == k: 
        ans = min(ans, distance)
        continue
    if lft_num + (k-i-2) < n:
        r = x[lft_num + (k-i-2)]
        distance += abs(r - l)
        ans = min(ans, distance)
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(item) for item in input().split()]
a_sorted = sorted(a)

def can_be_midofmid(b):
    high_low_cum = [0] * (n + 1)
    for i, item in enumerate(a):
        if item >= b:
            high_low_cum[i+1] = 1
        else:
            high_low_cum[i+1] = -1
    for i in range(n):
        high_low_cum[i+1] += high_low_cum[i]
    bit_n = 1 << n.bit_length()
    bit = [0] * (bit_n+1)

    def bit_add(x, w):
        while x <= bit_n:
            bit[x] += w
            x += x & -x

    def bit_sum(x):
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= x & -x
        return ret

    val = 0
    dic = dict(zip(sorted(high_low_cum), [item for item in range(len(high_low_cum))]))
    for i, item in enumerate(high_low_cum):
        val += bit_sum(dic[item] + 1)
        bit_add(dic[item] + 1, 1)
    return val  >= ((n+1) * n + 2)// 4  

l = -1; r = n
while r - l > 1:
    mid = (r + l) // 2
    if can_be_midofmid(a_sorted[mid]):
        l = mid
    else:
        r = mid
print(a_sorted[r-1])

Fixed submission:
n = int(input())
a = [int(item) for item in input().split()]
a_sorted = sorted(a)

def can_be_midofmid(b):
    high_low_cum = [0] * (n + 1)
    for i, item in enumerate(a):
        if item >= b:
            high_low_cum[i+1] = 1
        else:
            high_low_cum[i+1] = -1
    for i in range(n):
        high_low_cum[i+1] += high_low_cum[i]
    bit_n = 1 << n.bit_length()
    bit = [0] * (bit_n+1)

    def bit_add(x, w):
        while x <= bit_n:
            bit[x] += w
            x += x & -x

    def bit_sum(x):
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= x & -x
        return ret

    val = 0
    dic = dict(zip(sorted(high_low_cum), [item for item in range(len(high_low_cum))]))
    for i, item in enumerate(high_low_cum):
        val += bit_sum(dic[item] + 1)
        bit_add(dic[item] + 1, 1)
    return val  >= ((n+1) * n + 2)// 4  

l = -1; r = n
while r - l > 1:
    mid = (r + l) // 2
    if can_be_midofmid(a_sorted[mid]):
        l = mid
    else:
        r = mid
print(a_sorted[r-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())

get = []
for i in range(10):
  npow6 = 6**(i+1)
  npow9 = 9**(i+1)
  if npow6 <= 100000:
    get.append(npow6)
  if npow9 <= 100000:
    get.append(npow9)
  
get = sorted(get)

memo = [-1] * 110000
for i in range(6):
  memo[i] = i
  
def dfs(money):
  if memo[money] != -1:
    return memo[money]
  if money == 0:
    return 0
  
  ret = 110000
  for g in get:
    if g > money:
      continue
    ret0 = dfs(money-g) + 1
    ret = min(ret, ret0)
  memo[money] = ret
  return ret

print(dfs(n))

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

n = int(input())

get = []
for i in range(10):
  npow6 = 6**(i+1)
  npow9 = 9**(i+1)
  if npow6 <= 100000:
    get.append(npow6)
  if npow9 <= 100000:
    get.append(npow9)
  
get = sorted(get)

memo = [-1] * 110000
for i in range(6):
  memo[i] = i
  
def dfs(money):
  if memo[money] != -1:
    return memo[money]
  ret = 110000
  for g in get:
    if g > money:
      continue
    ret0 = dfs(money-g) + 1
    ret = min(ret, ret0)
  memo[money] = ret
  return ret

print(dfs(n))
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353
n, a, b, k = [int(item) for item in input().split()]

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

if a < b:
    a, b = b, a
max_a_num = k // a + 1
ans = 0
for a_num in range(max_a_num):
    lest = k - (a_num * a)
    if lest % b != 0 or lest < 0:
        continue
    b_num = lest // b
    ans += mod_nCr(n, a_num) * mod_nCr(n, b_num)
    ans %= MOD
print(ans)

Fixed submission:
MOD = 998244353
n, a, b, k = [int(item) for item in input().split()]

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

if a < b:
    a, b = b, a
max_a_num = k // a + 1
ans = 0
for a_num in range(max_a_num):
    lest = k - (a_num * a)
    if lest % b != 0 or lest < 0:
        continue
    b_num = lest // b
    ans += mod_nCr(n, a_num) * mod_nCr(n, b_num)
    ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353
N = 3 * 10**5 + 1

fac = [1] + [0] * N
fac_inv = [1] + [0] * N
for i in range(1, N+1):
    fac[i] = fac[i-1] * (i) % MOD
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

n, a, b, k = [int(item) for item in input().split()]
if a < b:
    a, b = b, a
max_a_num = k // a + 1
ans = 0
for a_num in range(max_a_num):
    lest = k - (a_num * a)
    if lest % b != 0 or lest < 0:
        continue
    b_num = lest // b
    ans += mod_nCr(n, a_num) * mod_nCr(n, b_num)
    ans %= MOD
print(ans)

Fixed submission:
MOD = 998244353
n, a, b, k = [int(item) for item in input().split()]

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

if a < b:
    a, b = b, a
max_a_num = k // a + 1
ans = 0
for a_num in range(max_a_num):
    lest = k - (a_num * a)
    if lest % b != 0 or lest < 0:
        continue
    b_num = lest // b
    ans += mod_nCr(n, a_num) * mod_nCr(n, b_num)
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(item) for item in input().split()] + [0]

ans = 0
for i in range(1, n):
  j = 0
  xor = a[i+j-1]
  while not xor & a[i+j] and i+j < n:
    xor ^= a[i+j]
    j += 1
    ans += 1
    
print(ans + n)


Fixed submission:
n = int(input())
a = [int(item) for item in input().split()] + [0]

ans = 0
s = 0
j = 0
for i in range(n):
  while not s & a[j] and j < n:
    s += a[j]
    j += 1
  ans += j - i
  s -= a[i]
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())

length = len(s)
sub = []
for item in "abcdefghijklmnopqrstuvwxyz":
  if item in s:
    for i, c in enumerate(s):
      if c == item:
        for j in range(0,length - i + 1):
          if j==0:
            if s[i] not in sub:
              sub.append(s[i])
          else: 
            if s[i:i+j] not in sub:
              sub.append(s[i:i+j])
    if len(sub) >= k:
      break
print(sorted(sub)[k-1])

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

length = len(s)
sub = []
for item in "abcdefghijklmnopqrstuvwxyz":
  if item in s:
    for i, c in enumerate(s):
      if c == item:
        for j in range(0,length - i + 1):
          if j > 5:
            break
          if j==0:
            if s[i] not in sub:
              sub.append(s[i])
          else: 
            if s[i:i+j] not in sub:
              sub.append(s[i:i+j])
    if len(sub) >= k:
      break
print(sorted(sub)[k-1])