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

N,K = map(int,input().split())
A = sorted([int(i) for i in input().split()]) # 消化コスト
F = sorted([int(i) for i in input().split()],reverse = True) # 食べにくさ
# K: 修行の回数

cost = [a*f for a,f in zip(A,F)]

# にぶたん
# K回以下の修行でチーム成績がMになるか
# Mを固定して考える
def grade_is(M:int):
    training = 0
    for i in range(N):
        if cost[i] > M:
            training += ceil((cost[i] - M) / F[i])
        if training > K:
            return False
    return True

ok = 10 ** 18 + 1
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if grade_is(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Fixed submission:
from math import ceil
 
N, K = map(int,input().split())
A = sorted([int(i) for i in input().split()])
F = sorted([int(i) for i in input().split()],reverse=True)
# メンバーそれぞれが完食にかかる時間のリスト
cost = [A[i]*F[i] for i in range(N)]
 
# K回の修行でチーム成績がxになるか
def grade_is_x(x):
    training = 0
    for i in range(N):
        if cost[i] > x:
            training += ceil((cost[i]-x)/F[i])
            if training > K:
                return False
    return True
 
# 二分探索でxの最小値を求める
cost_max = max(cost)
ok = cost_max
ng = max(-1,max(cost)-K*F[cost.index(cost_max)])
while (ok - ng) != 1:
    mid = (ok + ng) // 2
    if grade_is_x(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil

N,K = map(int,input().split())
A = sorted([int(i) for i in input().split()]) # 消化コスト
F = sorted([int(i) for i in input().split()],reverse = True) # 食べにくさ
# K: 修行の回数

cost = [a*f for a,f in zip(A,F)]

# にぶたん
# K回以下の修行でチーム成績がMになるか
# Mを固定して考える
def grade_is(M:int):
    training = 0
    for i in range(N):
        if cost[i] > M:
            training += ceil((cost[i] - M) / F[i])
    return training <= K

ok = 10 ** 18 + 1
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if grade_is(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Fixed submission:
from math import ceil
 
N, K = map(int,input().split())
A = sorted([int(i) for i in input().split()])
F = sorted([int(i) for i in input().split()],reverse=True)
# メンバーそれぞれが完食にかかる時間のリスト
cost = [A[i]*F[i] for i in range(N)]
 
# K回の修行でチーム成績がxになるか
def grade_is_x(x):
    training = 0
    for i in range(N):
        if cost[i] > x:
            training += ceil((cost[i]-x)/F[i])
            if training > K:
                return False
    return True
 
# 二分探索でxの最小値を求める
cost_max = max(cost)
ok = cost_max
ng = max(-1,max(cost)-K*F[cost.index(cost_max)])
while (ok - ng) != 1:
    mid = (ok + ng) // 2
    if grade_is_x(mid):
        ok = mid
    else:
        ng = mid
print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
sort_A = [0]*N

num = N
for i in range(N)[::-1]:
    sort_A[i] = A.index(num) + 1
    num -= 1

print(' '.join(list(map(str,sort_A))))

Fixed submission:
from operator import itemgetter

N = int(input())
A = list(map(int,input().split()))
index_A = sorted([[i+1,x] for i,x in enumerate(A)],key=itemgetter(1))
A = [i[0] for i in index_A]

print(" ".join(list(map(str,A))))

Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter

N = int(input())
A = list(map(int,input().split()))
sort_A = [0]*N

num = N
for i in range(N)[::-1]:
    sort_A[i] = A.index(num) + 1
    num -= 1

print(' '.join(list(map(str,sort_A))))

Fixed submission:
from operator import itemgetter

N = int(input())
A = list(map(int,input().split()))
index_A = sorted([[i+1,x] for i,x in enumerate(A)],key=itemgetter(1))
A = [i[0] for i in index_A]

print(" ".join(list(map(str,A))))
Buggy python submission (verdict: Runtime Error):
from fractions import gcd

A,B = map(int,input().split())
GCD = gcd(A,B)

# エラスとてネスの篩
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

answer = 0
for i in ([1]+primes(GCD)):
    if A%i == B%i == 0:
        answer += 1
print(answer)

Fixed submission:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            if not i in arr:
                arr.append(i)

    if temp!=1:
        if not temp in arr:
                arr.append(temp)

    return arr

A,B = map(int,input().split())
common = len(set(factorization(A)) & set(factorization(B)))
print(common+1)

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

A,B = map(int,input().split())
GCD = gcd(A,B)

# エラスとてネスの篩
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

answer = 0
for i in ([1]+primes(GCD)):
    if A%i == B%i == 0:
        answer += 1
print(answer)

Fixed submission:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            if not i in arr:
                arr.append(i)

    if temp!=1:
        if not temp in arr:
                arr.append(temp)

    return arr

A,B = map(int,input().split())
common = len(set(factorization(A)) & set(factorization(B)))
print(common+1)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
AB, C = [], []
for _ in range(M):
    AB.append(tuple(int(i) for i in input().split()))
    C.append(sum(1<<(int(i)-1) for i in input().split()))

INF = 10**18

# dp[i]: 状態がbin(i)のときの費用の最小値
# bin(i)のj桁が1: j番目の宝箱を開けられる
dp = [INF] * (1<<N)

# 初期条件(全ての宝箱を開けられない)
dp[0] = 0

for i in range(1<<N):
    for (a, _), c in zip(AB,C):
        # 状態iで状態cにする鍵を買ったときの状態
        dp[i | c] = min(dp[i | c], dp[i] + a)

if dp[-1] == INF:
    ans = -1
else:
    ans = dp[-1]
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in input().split()))
    C.append(sum(1<<(int(i)-1) for i in input().split()))

INF = 10**18
# dp[i]: 状態がbin(i)のときの費用の最小値
# bin(i)のj桁が1: j番目の宝箱を開けられる
# 1<<N == 2**N
dp = [INF] * (1<<N)

# 初期条件(全ての宝箱を開けられない)
dp[0] = 0

for i in range(1<<N):
    for (a,b),c in zip(AB,C):
        # 状態iで状態cにする鍵を買ったときの状態
        state = i | c
        dp[state] = min(dp[state], dp[i]+a)

answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from bisect import insort_left

N,M = map(int,input().split())
A = sorted([int(i) for i in input().split()])

for _ in range(M):
    maximum = A.pop()
    insort_left(A, maximum>>1)

print(sum(A))

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

N,M = map(int,input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)

for _ in range(M):
    tmp = heapq.heappop(A)
    # 計算誤差を減らすためにtmpを正に直してシフト演算している
    heapq.heappush(A, (-1)*(-tmp >> 1))

print(-sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from bisect import insort_left

N,M = map(int,input().split())
A = sorted([int(i) for i in input().split()])

for _ in range(M):
    maximum = A.pop()
    insort_left(A, maximum>>1)

print(sum(A))

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

N,M = map(int,input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)

for _ in range(M):
    tmp = heapq.heappop(A)
    # 計算誤差を減らすためにtmpを正に直してシフト演算している
    heapq.heappush(A, (-1)*(-tmp >> 1))

print(-sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
# tree[i] += 1 O(logN)
def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

# sum(tree[1:i+1]) O(logN)
def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

# 二分探索 O(logN)
# 和がx以上となる最小のインデックス(>= 1)を返す
def BIT_search(x):
    # 求めるインデックス
    i = 0
    # 和
    s = 0
    # step = 2^i  (2^i <= N)
    step = 1<<(N.bit_length()-1)
    while step:
        if i+step <= N and s + tree[i+step] < x:
            i += step
            s += tree[i]
        step >>= 1
    # 1-indexed
    return i+1


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())

# 1-indexed
P = [None] + [int(x) for x in input().split()]

# p_to_i[i] = P.index(i)
# 1-indexed
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

"""
大きい数から挿入していく
左隣にあるインデックスを取得できるようにしておく
そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ
"""

# BIT (1-indexed)
tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    # 左にある既に書き込んだ数の個数
    L = BIT_sum(c)
    # 右にある既に書き込んだ数の個数
    R = BIT_sum(N) - L
    # tree[c] += 1 
    BIT_add(c)
    # 左側
    a = BIT_search(L-1) if L > 1 else 0
    b = BIT_search(L) if L > 0 else 0
    # 右側
    d = BIT_search(L+2) if R > 0 else N+1
    e = BIT_search(L+3) if R > 1 else N+1

    # xとなる個数
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef

print(answer)

Fixed submission:
# tree[i] += 1 O(logN)
def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

# sum(tree[1:i+1]) O(logN)
def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

# 二分探索 O(logN)
# 和がx以上となる最小のインデックス(>= 1)を返す
def BIT_search(x):
    # 求めるインデックス
    i = 0
    # 和
    s = 0
    # step = 2^i  (2^i <= N)
    step = 1<<(N.bit_length()-1)
    while step:
        if i+step <= N and s + tree[i+step] < x:
            i += step
            s += tree[i]
        step >>= 1
    # 1-indexed
    return i+1


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())

# 1-indexed
P = [None] + [int(x) for x in input().split()]

# p_to_i[i] = P.index(i)
# 1-indexed
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

"""
大きい数から挿入していく
左隣にあるインデックスを取得できるようにしておく
そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ
"""

# BIT (1-indexed)
tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    # 左にある既に書き込んだ数の個数
    L = BIT_sum(c)
    # 右にある既に書き込んだ数の個数
    R = BIT_sum(N) - L
    # tree[c] += 1 
    BIT_add(c)
    # 左側
    a = BIT_search(L-1) if L > 1 else 0
    b = BIT_search(L) if L > 0 else 0
    # 右側
    d = BIT_search(L+2) if R > 0 else N+1
    e = BIT_search(L+3) if R > 1 else N+1

    # xとなる個数
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

print(sum(range(N)))

Fixed submission:
N = int(input())

print(N*(N-1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())
s = [None] + [list(input()) for _ in range(N)]

count = [None]*(N+1)

answer = 0
for i in range(1,N+1):
    count[i] = Counter(s[i])
    answer += count[:i].count(count[i])

print(answer)

Fixed submission:
from collections import Counter,defaultdict
import sys
input = sys.stdin.readline

N = int(input())
s = [None] + [list(input()) for _ in range(N)]

count = defaultdict(int)

answer = 0
for i in range(1,N+1):
    c = Counter(s[i])
    c = sorted(c.items(), key=lambda x:x[0])
    # O(len(c))
    str_c = ""
    for key,item in c:
        str_c += key*item
    answer += count[str_c]
    count[str_c] += 1

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]
AB.sort(reverse=True)

answer = 0
for j in range(M-1,-1,-1):
    maxB = 0
    index = -1
    for i in range(len(AB)-1,-1,-1):
        a,b = AB[i]
        if a + j <= M:
            if maxB < b:
                maxB = b
                index = i
            if i == 0:
                AB.pop(index)
                answer += maxB
        else:
            if index < 0:
                break
            else:
                AB.pop(index)
                answer += maxB
                break

print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappushpop

N,M = map(int,input().split())
# task[締切][価値]
tasks = [[] for _ in range(M)] 
for _ in range(N):
    a,b = map(int,input().split())
    if a <= M:
        tasks[M-a].append(b)

# 受注したバイト
q = []
# 締切=dayとなる最大の価値をqに格納
for day in range(M):
    # その日締切のバイト
    for v in tasks[day]:
        # まだ今日は受注してない
        if len(q) < day+1:
            heappush(q,v)
        else:
            heappushpop(q,v)

answer = sum(q)
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]
AB.sort(key=itemgetter(0,1),reverse=True)

answer = 0
for j in range(M-1,-1,-1):
    maxB = 0
    index = -1
    for i in range(len(AB)-1,-1,-1):
        a,b = AB[i]
        if a + j <= M:
            if maxB < b:
                maxB = b
                index = i
            if i == 0:
                AB.pop(index)
                answer += maxB
        else:
            if index < 0:
                break
            else:
                AB.pop(index)
                answer += maxB
                break

print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappushpop

N,M = map(int,input().split())
# task[締切][価値]
tasks = [[] for _ in range(M)] 
for _ in range(N):
    a,b = map(int,input().split())
    if a <= M:
        tasks[M-a].append(b)

# 受注したバイト
q = []
# 締切=dayとなる最大の価値をqに格納
for day in range(M):
    # その日締切のバイト
    for v in tasks[day]:
        # まだ今日は受注してない
        if len(q) < day+1:
            heappush(q,v)
        else:
            heappushpop(q,v)

answer = sum(q)
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = input().rstrip("\n")

# dp[i][j]: i文字目でjになる個数 (S[-i])
# 1-indexed
dp = [[0]*13 for _ in range(len(S)+1)]

# 初期条件(1桁目)
if S[-1] == "?":
    dp[1][:10] = [1]*10
else:
    dp[1][int(S[-1])] += 1

# i: i桁目
for i in range(1,len(S)+1):
    if S[-i] == "?":
        # j: S[-i]がとる値 (?のとき0~9)
        for j in range(10):
            jmod = j*(10**(i-1)) % 13
            # (i-1)桁目で余りがkとなる個数x
            for k,x in enumerate(dp[i-1]):
                dp[i][(k+jmod)%13] += x
    else:
        jmod = int(S[-i])*(10**(i-1)) % 13
        for k,x in enumerate(dp[i-1]):
            dp[i][(k+jmod)%13] += x

print(dp[-1][5] % (10**9+7))

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9+7

S = input().rstrip("\n")

# dp[i][j]: i文字目でjになる個数 (S[-i])
# 1-indexed
dp = [[0]*13 for _ in range(len(S)+1)]

# 初期条件(1桁目)
if S[-1] == "?":
    dp[1][:10] = [1]*10
else:
    dp[1][int(S[-1])] += 1

# mul = 10**(i-1)
mul = 10
# i: i桁目
for i in range(2,len(S)+1):
    if S[-i] == "?":
        # j: S[-i]がとる値 (?のとき0~9)
        for j in range(10):
            jmod = j*mul % 13
            # (i-1)桁目で余りがkとなる個数x
            for k,x in enumerate(dp[i-1]):
                dp[i][(k+jmod)%13] = (dp[i][(k+jmod)%13] + x) % MOD
    else:
        jmod = int(S[-i])*mul % 13
        for k,x in enumerate(dp[i-1]):
            dp[i][(k+jmod)%13] = (dp[i][(k+jmod)%13] + x) % MOD
    mul = (mul * 10) % 13

print(dp[-1][5])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = input().rstrip("\n")

# dp[i][j]: i文字目でjになる個数 (S[-i])
# 1-indexed
dp = [[0]*13 for _ in range(len(S)+1)]

# 初期条件(1桁目)
if S[-1] == "?":
    dp[1][:10] = [1]*10
else:
    dp[1][int(S[-1])] += 1

# i: i桁目
for i in range(1,len(S)+1):
    if S[-i] == "?":
        # j: S[-i]がとる値 (?のとき0~9)
        for j in range(10):
            jmod = j*(10**(i-1)) % 13
            # (i-1)桁目で余りがkとなる個数x
            for k,x in enumerate(dp[i-1]):
                dp[i][(k+jmod)%13] += x
    else:
        jmod = int(S[-i])*(10**(i-1)) % 13
        for k,x in enumerate(dp[i-1]):
            dp[i][(k+jmod)%13] += x

print(dp[-1][5] % (10**9+7))

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9+7

S = input().rstrip("\n")

# dp[i][j]: i文字目でjになる個数 (S[-i])
# 1-indexed
dp = [[0]*13 for _ in range(len(S)+1)]

# 初期条件(1桁目)
if S[-1] == "?":
    dp[1][:10] = [1]*10
else:
    dp[1][int(S[-1])] += 1

# mul = 10**(i-1)
mul = 10
# i: i桁目
for i in range(2,len(S)+1):
    if S[-i] == "?":
        # j: S[-i]がとる値 (?のとき0~9)
        for j in range(10):
            jmod = j*mul % 13
            # (i-1)桁目で余りがkとなる個数x
            for k,x in enumerate(dp[i-1]):
                dp[i][(k+jmod)%13] = (dp[i][(k+jmod)%13] + x) % MOD
    else:
        jmod = int(S[-i])*mul % 13
        for k,x in enumerate(dp[i-1]):
            dp[i][(k+jmod)%13] = (dp[i][(k+jmod)%13] + x) % MOD
    mul = (mul * 10) % 13

print(dp[-1][5])
Buggy python submission (verdict: Runtime Error):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i - 1)
            if i != n // i:
                divisors.append(n//i - 1)
    return divisors

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np

N = int(input())
# 1-indexed
a = [int(i) for i in input().split()]

now = [0] * N
for i in range(N-1,-1,-1):
    if now[i] != a[i]:
        div = make_divisors(i+1)
        for j in div:
            now[j] += 1
            now[j] %= 2

print(M)

answer = [i+1 for i,x in enumerate(now) if x == 1]
if answer:
    print(" ".join(list(map(str,answer))))

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
a = [int(i) for i in input().split()]

box = [0] * N

for i in range(N-1, -1, -1):
    # (i+1)の倍数が書かれた箱を探索
    count = 0
    n = i+1
    while n <= N:
        count += box[n-1]
        n += i + 1

    if count % 2 != a[i]:
        box[i] = 1

M = box.count(1)
print(M)

answer = [i+1 for i,x in enumerate(box) if x == 1]
if M > 0:
    print(' '.join(list(map(str,answer))))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
a = [0] * M
for i in range(M):
    a[i] = int(input())

MOD = 10**9 + 7

# dp[i]: i段目の移動方法の合計
dp = [0] * (N+1)

# 初期条件
dp[0] = 1

for i in range(N):
    if i == N-1:
        dp[i+1] += dp[i]
        continue

    if not (i+1) in a:
        dp[i+1] += dp[i] % MOD
    if not (i+2) in a:
        dp[i+2] += dp[i] % MOD

print(dp[-1] % MOD)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from bisect import bisect_left

N,M = map(int,input().split())
a = [0] * M
for i in range(M):
    a[i] = int(input())
a.sort()
len_a = len(a)

MOD = 10**9 + 7

# dp[i]: i段目の移動方法の合計
dp = [0] * (N+1)

# 初期条件
dp[0] = 1

for i in range(N):
    if i == N-1:
        dp[i+1] = dp[i+1] + dp[i] % MOD
        continue

    index = bisect_left(a,i+1)
    if index == len_a or a[index] != i + 1:
        dp[i+1] = dp[i+1] + dp[i] % MOD
    index = bisect_left(a,i+2)
    if index == len_a or a[index] != i + 2:
        dp[i+2] = dp[i+2] + dp[i] % MOD

print(dp[-1] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
a = [0] * M
for i in range(M):
    a[i] = int(input())

MOD = 10**9 + 7

# dp[i]: i段目の移動方法の合計
dp = [0] * (N+1)

# 初期条件
dp[0] = 1

for i in range(N):
    if i == N-1:
        dp[i+1] += dp[i]
        continue

    if not (i+1) in a:
        dp[i+1] += dp[i] % MOD
    if not (i+2) in a:
        dp[i+2] += dp[i] % MOD

print(dp[-1] % MOD)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from bisect import bisect_left

N,M = map(int,input().split())
a = [0] * M
for i in range(M):
    a[i] = int(input())
a.sort()
len_a = len(a)

MOD = 10**9 + 7

# dp[i]: i段目の移動方法の合計
dp = [0] * (N+1)

# 初期条件
dp[0] = 1

for i in range(N):
    if i == N-1:
        dp[i+1] = dp[i+1] + dp[i] % MOD
        continue

    index = bisect_left(a,i+1)
    if index == len_a or a[index] != i + 1:
        dp[i+1] = dp[i+1] + dp[i] % MOD
    index = bisect_left(a,i+2)
    if index == len_a or a[index] != i + 2:
        dp[i+2] = dp[i+2] + dp[i] % MOD

print(dp[-1] % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from itertools import groupby
import sys
input = sys.stdin.readline

H, W = map(int,input().split())
S = np.array([[0 if i == "." else 1 for i in list(input())] for _ in range(H)])
rot_S = np.rot90(S, -1)

answer = np.array([[-1]*W for _ in range(H)])
for i,s in enumerate(S):
    j = 0
    for key, group in groupby(s):
        group_len = len(list(group))
        if key == 0:
            answer[i][j:j+group_len] += group_len
        j += group_len

for i,s in enumerate(rot_S):
    j = H
    for key, group in groupby(s):
        group_len = len(list(group))
        if key == 0:
            answer[j-group_len:j, i:i+1] += group_len
        j -= group_len

print(answer.max())

Fixed submission:
import numpy as np
import sys
input = sys.stdin.readline

H,W = map(int,input().split())
S=np.array([list(input().rstrip("\n")) for _ in range(H)]) == '.'

D = np.zeros((H,W),dtype=int)
U = np.zeros((H,W),dtype=int)
L = np.zeros((H,W),dtype=int)
R = np.zeros((H,W),dtype=int)

# 上下
for i in range(H):
  U[i] = (U[i-1] + 1) * S[i]
  D[-i-1] = (D[-i] + 1) * S[-i-1]

# 左右
for i in range(W):
  L[:,i] = (L[:,i-1] + 1) * S[:,i]
  R[:,-i-1] = (R[:,-i] + 1) * S[:,-i-1]

print(np.max(U+D+L+R)-3)
Buggy python submission (verdict: Runtime Error):
N,A,B,C,D = map(int, input().split())
S = [""] + list(input())

def can(start, end):
    for i in range(start, end):
        if S[i] == S[i + 1] == "#":
            return False
    return True

def main():
    if not (can(A, C) and can(B, D)):
        return False

    if C < D:
        flag = False
        for i in range(B, D + 1):
            if S[i - 1] == S[i] == S[i + 1] == ".":
                flag = True
        if not flag:
            return False
    
    return True

if __name__ == "__main__":
    if main():
        print('Yes')
    else:
        print('No')

Fixed submission:
N,A,B,C,D = map(int,input().split())
# 1-indexed
S = ["$"] + list(input())

if A < B < D < C:
    flag = False

    for i in range(B+1,D+2):
        if S[i-2] == S[i-1] == S[i] == ".":
            flag = True
            break
    for i in range(A+1,C+1):
        if S[i] == S[i-1] == "#":
            flag = False
            break
    
    if flag:
        print("Yes")
    else:
        print("No")

elif A < B < C < D:
    flag = True
    for i in range(A+1,D+1):
        if S[i] == S[i-1] == "#":
            flag = False
            break
    
    if flag:
        print("Yes")
    else:
        print("No")
        
elif A < C < B < D:
    flag = True
    for i in range(A+1,C+1):
        if S[i] == S[i-1] == "#":
            flag = False
            break
    for i in range(B+1,D+1):
        if S[i] == S[i-1] == "#":
            flag = False
            break
    if flag:
        print("Yes")
    else:
        print("No")