Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
for i in range(q):
    si,ei=map(int,input().split())
    print(s[si-1:ei].count("AC"))

Fixed submission:
from bisect import bisect_left as b_l
n,q=map(int,input().split())
s=input()
pi=0
aci=[]
while 1:
    ni=s[pi:].find("AC")
    if ni==-1:
        break
    aci+=[ni+pi]
    pi+=ni+1
for i in range(q):
    si,ei=map(int,input().split())
    print(b_l(aci,ei-1)-b_l(aci,si-1))

Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
for i in range(n):
    si,ei=map(int,input().split())
    print(s[si-1:ei].count("AC"))

Fixed submission:
from bisect import bisect_left as b_l
n,q=map(int,input().split())
s=input()
pi=0
aci=[]
while 1:
    ni=s[pi:].find("AC")
    if ni==-1:
        break
    aci+=[ni+pi]
    pi+=ni+1
for i in range(q):
    si,ei=map(int,input().split())
    print(b_l(aci,ei-1)-b_l(aci,si-1))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n = int(input())
    cc = [int(input()) for _ in range(n)]
    dp = [0] * (n + 1)
    dp[0] = 1
    ll = defaultdict(list)
    pc = -1
    for r, c in enumerate(cc):
        dp[r + 1] = dp[r]
        if c == pc: continue
        for l in ll[c]:
            dp[r + 1] += dp[l]
        dp[r + 1] %= md
        ll[c].append(r)
        pc = c
    print(dp[n])

main()


Fixed submission:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n = int(input())
    cc = [int(input()) for _ in range(n)]
    dp = [0] * (n + 1)
    dp[0] = 1
    ll = defaultdict(int)
    pc = -1
    for r, c in enumerate(cc):
        dp[r + 1] = dp[r]
        if c == pc: continue
        dp[r + 1] = (dp[r + 1] + ll[c]) % md
        ll[c] = (ll[c] + dp[r]) % md
        pc = c
    print(dp[n])

main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n = int(input())
    cc = [int(input()) for _ in range(n)]
    dp = [0] * (n + 1)
    dp[0] = 1
    ll = defaultdict(list)
    pc = -1
    for r, c in enumerate(cc):
        dp[r + 1] = dp[r]
        if c == pc: continue
        for l in ll[c]:
            dp[r + 1] += dp[l]
        dp[r + 1] %= md
        ll[c].append(r)
        pc = c
    print(dp[n])

main()


Fixed submission:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n = int(input())
    cc = [int(input()) for _ in range(n)]
    dp = [0] * (n + 1)
    dp[0] = 1
    ll = defaultdict(int)
    pc = -1
    for r, c in enumerate(cc):
        dp[r + 1] = dp[r]
        if c == pc: continue
        dp[r + 1] = (dp[r + 1] + ll[c]) % md
        ll[c] = (ll[c] + dp[r]) % md
        pc = c
    print(dp[n])

main()
Buggy python submission (verdict: Time Limit Exceeded):
a,b=map(int,input().split(" "))
for i in range(a+1,b+1):
    a^=i
print(a)

Fixed submission:
def z_to_n(n):
    m4=n%4
    if m4==0:
        return n
    elif m4==1:
        return 1
    elif m4==2:
        return n+1
    else:
        return 0
a,b=map(int,input().split(" "))
print(z_to_n(a-1)^z_to_n(b))
Buggy python submission (verdict: Runtime Error):
sn,bn=map(int,input().split(" "))
fu=[int(sn*(sn-1)/2)]
gr_si=[n for n in range(sn+1)]
siL_gr=[[n] for n in range(sn+1)]
siL_br=[]
for _ in range(bn):
    siL_br.append(list(map(int, input().split(" "))))
siL_br=siL_br[::-1]

for bri in range(bn-1):
    si1,si2=siL_br[bri]
    gr1 = gr_si[si1]
    gr2 = gr_si[si2]
    if gr1==gr2:
        fu.append(fu[bri])
    else:
        lengr1 = len(siL_gr[gr1])
        lengr2 = len(siL_gr[gr2])
        if lengr1<lengr2:
            gr1,gr2=gr2,gr1
        fu.append(fu[bri]-lengr1*lengr2)
        for si in siL_gr[gr2]:
            gr_si[si]=gr1
        siL_gr[gr1]+=siL_gr[gr2]

print(*fu[::-1],sep="\n")


Fixed submission:
a,b,c=map(int,input().split(" "))
if a*c<=b:
    print(c)
else:
    print(b//a)
Buggy python submission (verdict: Runtime Error):
import math
a,b,k=map(int,input().split(" "))
g=math.gcd(a,b)
if k==1:
    print(g)
else:
    cnt = 1
    for n in range(2,g+1):
        if g%n==0:
            cnt+=1
            if cnt==k:
                print(int(g/n))
                break

Fixed submission:
def gcd(a,b):
    while a%b!=0:
        a,b=b,a%b
    return b

a,b,k=map(int,input().split(" "))
g=gcd(a,b)
if k==1:
    print(g)
else:
    cnt = 1
    for n in range(2,g+1):
        if g%n==0:
            cnt+=1
            if cnt==k:
                print(int(g/n))
                break
Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

def gcd_list(lst):
    if len(lst)==2:
        return gcd(lst[0],lst[1])
    else:
        return gcd_list([gcd(lst[0],lst[1])]+lst[2:])

n,*h=map(int,open(0).read().split())

print(gcd_list(h))

Fixed submission:
def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n,*h=map(int,open(0).read().split())

gh=gcd(h[0],h[1])
for i in range(2,n):
    gh=gcd(h[i],gh)

print(gh)

Buggy python submission (verdict: Time Limit Exceeded):
n,*h=map(int,open(0).read().split())
while len(h)>1:
    kh=set()
    for x in h:
        mn = min(h)
        md=x%mn
        if md!=0:
            kh.add(md)
        if len(kh)==mn-1:
            break
    kh.add(mn)
    h=kh
print(mn)

Fixed submission:
def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n,*h=map(int,open(0).read().split())

gh=gcd(h[0],h[1])
for i in range(2,n):
    gh=gcd(h[i],gh)

print(gh)

Buggy python submission (verdict: Time Limit Exceeded):
n,*h=map(int,open(0).read().split())
while len(h)>1:
    kh=set()
    for x in h:
        mn = min(h)
        md=x%mn
        if md!=0:
            kh.add(md)
        kh.add(mn)
    h=kh
print(mn)

Fixed submission:
def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n,*h=map(int,open(0).read().split())

gh=gcd(h[0],h[1])
for i in range(2,n):
    gh=gcd(h[i],gh)

print(gh)

Buggy python submission (verdict: Time Limit Exceeded):
n,*h=map(int,open(0).read().split())
while len(h)>1:
    kh=[]
    for i in range(len(h)):
        mn = min(h)
        md=h[i]%mn
        if md!=0:
            kh.append(md)
        kh.append(mn)
    h=list(set(kh))
print(mn)

Fixed submission:
def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n,*h=map(int,open(0).read().split())

gh=gcd(h[0],h[1])
for i in range(2,n):
    gh=gcd(h[i],gh)

print(gh)

Buggy python submission (verdict: Runtime Error):
while len(h)>1:
    kh=[]
    for i in range(len(h)):
        mn = min(h)
        md=h[i]%mn
        if md!=0:
            kh.append(md)
        kh.append(mn)
    h=list(set(kh))
print(mn)

Fixed submission:
def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n,*h=map(int,open(0).read().split())

gh=gcd(h[0],h[1])
for i in range(2,n):
    gh=gcd(h[i],gh)

print(gh)

Buggy python submission (verdict: Time Limit Exceeded):
n,*h=map(int,open(0).read().split())
while len(h)>1:
    kh=[]
    for i in range(len(h)):
        mn=min(h)
        md=h[i]%mn
        if md!=0:
            kh.append(md)
        else:
            kh.append(mn)
    h=list(set(kh))
print(mn)

Fixed submission:
def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n,*h=map(int,open(0).read().split())

gh=gcd(h[0],h[1])
for i in range(2,n):
    gh=gcd(h[i],gh)

print(gh)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    def dfs(u, ou=-1, d=0):
        if d < depth[u]: return
        parent[u] = ou + 1
        depth[u] = d
        for ku in to[u]:
            dfs(ku, u, d + 1)

    to = defaultdict(list)
    n, m = map(int, input().split())
    CntInDegree = [0] * n
    parent = [-1] * n
    depth = [-1] * n
    for _ in range(n + m - 1):
        a, b = map(int1, input().split())
        to[a].append(b)
        CntInDegree[b] += 1
    root = CntInDegree.index(0)
    # print(root)
    dfs(root)
    print(*parent, sep="\n")

main()


Fixed submission:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    to = defaultdict(set)
    ot = defaultdict(set)
    n, m = map(int, input().split())
    cnt_in_degree = [0] * n
    parent = [-1] * n
    for _ in range(n + m - 1):
        a, b = map(int1, input().split())
        cnt_in_degree[b] += 1
        to[a].add(b)
        ot[b].add(a)
    root = cnt_in_degree.index(0)
    parent[root] = -1
    part_roots = [root]
    cnt_decide = 1
    while cnt_decide < n:
        u = part_roots.pop()
        for ku in to[u]:
            if len(ot[ku]) == 1:
                parent[ku] = u
                part_roots.append(ku)
                cnt_decide += 1
            else:
                ot[ku].remove(u)
    for u in parent:
        print(u + 1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    def dfs(u, ou=-1, d=0):
        if d < depth[u]: return
        parent[u] = ou + 1
        depth[u] = d
        for ku in to[u]:
            dfs(ku, u, d + 1)

    to = defaultdict(list)
    n, m = map(int, input().split())
    CntInDegree = [0] * n
    parent = [-1] * n
    depth = [-1] * n
    for _ in range(n + m - 1):
        a, b = map(int1, input().split())
        to[a].append(b)
        CntInDegree[b] += 1
    root = CntInDegree.index(0)
    # print(root)
    dfs(root)
    print(*parent, sep="\n")

main()


Fixed submission:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    to = defaultdict(set)
    ot = defaultdict(set)
    n, m = map(int, input().split())
    cnt_in_degree = [0] * n
    parent = [-1] * n
    for _ in range(n + m - 1):
        a, b = map(int1, input().split())
        cnt_in_degree[b] += 1
        to[a].add(b)
        ot[b].add(a)
    root = cnt_in_degree.index(0)
    parent[root] = -1
    part_roots = [root]
    cnt_decide = 1
    while cnt_decide < n:
        u = part_roots.pop()
        for ku in to[u]:
            if len(ot[ku]) == 1:
                parent[ku] = u
                part_roots.append(ku)
                cnt_decide += 1
            else:
                ot[ku].remove(u)
    for u in parent:
        print(u + 1)

main()
Buggy python submission (verdict: Time Limit Exceeded):
sn, tn, *s = map(int, open(0).read().split())
sy_oi = [[s[i * 2], s[i * 2 + 1]] for i in range(sn)]
sy_oi.sort(key=lambda x: -x[1])
cho = sy_oi[tn - 1::-1]
zan = sy_oi[tn:]
zn = sn - tn
# チョイスした種類の辞書
sydic = {}
for x in cho:
    if x[0] in sydic:
        sydic[x[0]] += 1
    else:
        sydic[x[0]] = 1
ot = sum([x[1] for x in cho])  # おいしさポイント
mt = len(sydic)  # まんぞくポイント
ans = ot + mt ** 2
zi = 0
cnt = 0
while 1:
    # チョイスから削除できるものを探す
    for i in range(tn - cnt):
        if sydic[cho[i][0]] > 1:
            sydic[cho[i][0]] -= 1
            ot -= cho[i][1]
            del cho[i]
            break
    else:
        break
    # 残から加えるものを探す
    for i in range(zi, zn):
        if zan[i][0] not in sydic:
            sydic[zan[i][0]] = 1
            ot += zan[i][1]
            mt += 1
            zi = i
            break
    else:
        break
    # 得点計算して更新
    ans = max(ans, ot + mt ** 2)
    cnt += 1
print(ans)


Fixed submission:
sn, tn, *s = map(int, open(0).read().split())
sy_oi = [[s[i * 2], s[i * 2 + 1]] for i in range(sn)]
sy_oi.sort(key=lambda x: -x[1])
cho = sy_oi[tn - 1::-1]
zan = sy_oi[tn:]
zn = sn - tn
# チョイスした種類の辞書
sydic = {}
for x in cho:
    if x[0] in sydic:
        sydic[x[0]] += 1
    else:
        sydic[x[0]] = 1
ot = sum([x[1] for x in cho])  # おいしさポイント
mt = len(sydic)  # まんぞくポイント
ans = ot + mt ** 2
ci = 0
zi = 0
while 1:
    # チョイスから削除できるものを探す
    for i in range(ci, tn):
        if sydic[cho[i][0]] > 1:
            sydic[cho[i][0]] -= 1
            ot -= cho[i][1]
            ci = i + 1
            break
    else:
        break
    # 残から加えるものを探す
    for i in range(zi, zn):
        if zan[i][0] not in sydic:
            sydic[zan[i][0]] = 1
            ot += zan[i][1]
            mt += 1
            zi = i + 1
            break
    else:
        break
    # 得点計算して更新
    ans = max(ans, ot + mt ** 2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def main():
    h,w=MI()
    ss=[SI() for _ in range(h)]

    def dfs(i,j):
        bc=ss[i][j]=="#"
        wc=ss[i][j]=="."
        for di,dj in dij:
            ni,nj=i+di,j+dj
            if ni<0 or nj<0 or ni>=h or nj>=w:continue
            if fin[ni][nj] or ss[i][j]==ss[ni][nj]:continue
            fin[ni][nj]=True
            ret=dfs(ni,nj)
            bc+=ret[0]
            wc+=ret[1]
        return bc,wc

    ans=0
    fin=[[False]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if fin[i][j] or ss[i][j]==".":continue
            fin[i][j]=True
            bc,wc=dfs(i,j)
            ans+=bc*wc
    print(ans)

main()

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def main():
    h,w=MI()
    ss=[SI() for _ in range(h)]

    def dfs(i,j):
        stack=[(i,j)]
        bc,wc=0,0
        while stack:
            i,j=stack.pop()
            if ss[i][j]=="#":bc+=1
            else:wc+=1
            for di,dj in dij:
                ni,nj=i+di,j+dj
                if ni<0 or nj<0 or ni>=h or nj>=w:continue
                if fin[ni][nj] or ss[i][j]==ss[ni][nj]:continue
                fin[ni][nj]=True
                stack.append((ni,nj))
        return bc,wc

    ans=0
    fin=[[False]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if fin[i][j]:continue
            fin[i][j]=True
            bc,wc=dfs(i,j)
            ans+=bc*wc
    print(ans)

main()
Buggy python submission (verdict: Runtime Error):
inf = 10 ** 9
memo = {}


def cost(n):
    if n==2:
        return abs(h[2]-h[1])
    elif n == 1:
        return 0
    elif n < 1:
        return inf
    elif n in memo:
        return memo[n]
    else:
        re = min(cost(n - 2) + abs(h[n] - h[n - 2]), cost(n - 1) + abs(h[n] - h[n - 1]))
        memo[n] = re
        return re


n = int(input())
h = [0] + list(map(int, input().split()))
print(cost(n))
print(memo)


Fixed submission:
n = int(input())
h = [0] + list(map(int, input().split()))
cost = {1:0,2: abs(h[2] - h[1])}
for i in range(1, n):
    cost[i + 1] = min(cost[i + 1], cost[i] + abs(h[i + 1] - h[i]))
    if i==n-1:break
    cost[i + 2] = cost[i] + abs(h[i + 2] - h[i])

print(cost[n])

Buggy python submission (verdict: Runtime Error):
inf = 10 ** 9
memo = {}


def cost(n):
    if n == 1:
        return 0
    elif n < 1:
        return inf
    elif n in memo:
        return memo[n]
    else:
        re = min(cost(n - 2) + abs(h[n] - h[n - 2]), cost(n - 1) + abs(h[n] - h[n - 1]))
        memo[n] = re
        return re


n = int(input())
h = [0] + list(map(int, input().split()))
print(cost(n))


Fixed submission:
n = int(input())
h = [0] + list(map(int, input().split()))
cost = {1:0,2: abs(h[2] - h[1])}
for i in range(1, n):
    cost[i + 1] = min(cost[i + 1], cost[i] + abs(h[i + 1] - h[i]))
    if i==n-1:break
    cost[i + 2] = cost[i] + abs(h[i + 2] - h[i])

print(cost[n])

Buggy python submission (verdict: Runtime Error):
inf = 10 ** 9
memo = {}


def cost(n):
    if n == 1:
        return 0
    if n < 1:
        return inf
    if n in memo:
        return memo[n]
    re = min(cost(n - 2) + abs(h[n] - h[n - 2]), cost(n - 1) + abs(h[n] - h[n - 1]))
    memo[n] = re
    return re


n = int(input())
h = [0] + list(map(int, input().split()))
print(cost(n))


Fixed submission:
n = int(input())
h = [0] + list(map(int, input().split()))
cost = {1:0,2: abs(h[2] - h[1])}
for i in range(1, n):
    cost[i + 1] = min(cost[i + 1], cost[i] + abs(h[i + 1] - h[i]))
    if i==n-1:break
    cost[i + 2] = cost[i] + abs(h[i + 2] - h[i])

print(cost[n])
Buggy python submission (verdict: Runtime Error):
import sys

input = sys.stdin.readline


def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))


Fixed submission:
import sys

input = sys.stdin.readline


def nap(n, cap):
    mxk = 0
    inf = 10 ** 10
    wei = [0] + [inf] * 100000
    for _ in range(n):
        w, v = map(int, input().split())
        for vk in range(100000, v - 1, -1):
            nw = wei[vk - v] + w
            if nw > cap: continue
            if wei[vk] > nw:
                wei[vk] = nw
                if vk > mxk:
                    mxk = vk
    return mxk


n, cap = map(int, input().split())
print(nap(n, cap))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import *
import sys
import numpy as np
md=10**9+7
mis=map(int,sys.stdin.readline().split())

h,w=mis
t=np.zeros((h+1,w+1),dtype="uint64")
t[1][1]=1
s=[]
for _ in range(h):
    s+=[input()]

for i,j in product(range(h),range(w)):
    if i==0 and j==0:continue
    if s[i][j]==".":
        t[i+1][j+1]=(t[i][j+1]+t[i+1][j])%md
    else:
        t[i+1][j+1]=0

print(t[-1][-1])


Fixed submission:
from itertools import *
import sys
md=10**9+7
mis=map(int,sys.stdin.readline().split())

h,w=mis
t=[[0]*(w+1) for _ in range(h+1)]
s=[]
for _ in range(h):
    s+=[input()]

for i,j in product(range(h),range(w)):
    if i==0 and j==0:
        t[i+1][j+1]=1
    elif s[i][j]==".":
        t[i+1][j+1]=(t[i][j+1]+t[i+1][j])%md
    else:
        t[i+1][j+1]=0
print(t[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
def f(n):
    ps = list(map(float, input().split()))
    ans = 0
    for b in range(2 ** n):
        if format(b, "b").count("1") > n // 2:
            pi = 1
            for i in range(n):
                if b & 1:
                    pi *= ps[i]
                else:
                    pi *= 1 - ps[i]
                b = b >> 1
            ans += pi
    print(ans)

n = int(input())
f(n)


Fixed submission:
n=int(input())
ps=list(map(float,input().split()))
lim=(n+1)//2
dp=[0]*(lim+1)
dp[0]=1
for pi,p in enumerate(ps):
    if pi+1>=lim:
        st=lim-1
        dp[lim]=dp[lim]+dp[lim-1]*p
    else:
        st=pi+1
    for i in range(st,0,-1):
        dp[i]=dp[i-1]*p+dp[i]*(1-p)
    dp[0]=dp[0]*(1-p)
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
def f(n):
    ps = list(map(float, input().split()))
    ans = 0
    for b in range(2 ** n):
        if format(b, "b").count("1") > n // 2:
            pi = 1
            for i in range(n):
                if b & 1:
                    pi *= ps[i]
                else:
                    pi *= 1 - ps[i]
                b = b >> 1
            ans += pi
    print(ans)

n = int(input())
f(n)


Fixed submission:
n=int(input())
ps=list(map(float,input().split()))
lim=(n+1)//2
dp=[0]*(lim+1)
dp[0]=1
for pi,p in enumerate(ps):
    if pi+1>=lim:
        st=lim-1
        dp[lim]=dp[lim]+dp[lim-1]*p
    else:
        st=pi+1
    for i in range(st,0,-1):
        dp[i]=dp[i-1]*p+dp[i]*(1-p)
    dp[0]=dp[0]*(1-p)
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ps=list(map(float,input().split()))
ans=0
for b in range(2**n):
    if format(b,"b").count("1")>n//2:
        pi=1
        for i in range(n):
            if b & 1:
                pi*=ps[i]
            else:
                pi*=1-ps[i]
            b=b>>1
        ans+=pi
print(ans)

Fixed submission:
n=int(input())
ps=list(map(float,input().split()))
lim=(n+1)//2
dp=[0]*(lim+1)
dp[0]=1
for pi,p in enumerate(ps):
    if pi+1>=lim:
        st=lim-1
        dp[lim]=dp[lim]+dp[lim-1]*p
    else:
        st=pi+1
    for i in range(st,0,-1):
        dp[i]=dp[i-1]*p+dp[i]*(1-p)
    dp[0]=dp[0]*(1-p)
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [list(map(int, sys.stdin.readline().split())) for _ in range(rows_number)]

def main():
    md=10**9+7
    n=int(input())
    aa=LLI(n)
    lov=[[] for _ in range(n)]
    for i,ar in enumerate(aa):
        for j,a in enumerate(ar):
            if a:lov[i].append(j)
    dp=[0]*(1<<n)
    dp[0]=1
    for s in range((1<<n)-1):
        pre=dp[s]
        if pre==0:continue
        i=bin(s).count("1")
        for j in lov[i]:
            if s>>j&1:continue
            ns=s|1<<j
            dp[ns]=(dp[ns]+pre)%md
    print(dp[-1])
    #print(dp)

main()

Fixed submission:
def f(s, i):
    if i == n:
        return 1
    if memo[s] != -1:
        return memo[s]
    re = 0
    for j in range(n):
        if aij[i][j] and s & (1 << j):
            re += f(s - (1 << j), i + 1)
    re = memo[s] = re % md
    return re


md = 10 ** 9 + 7
n = int(input())
aij = [list(map(int, input().split())) for _ in range(n)]
memo = [-1] * (1 << n)
s = (1 << n) - 1
print(f(s, 0))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n = int(input())
    e = 1 << n
    to_love = []
    for _ in range(n):
        aa = list(map(int, input().split()))
        s = 0
        for i, a in enumerate(aa):
            if a: s += 1 << i
        to_love.append(s)
    # print(to_love)
    dp = [0] * e
    dp[e - 1] = 1
    for i in range(n):
        for j in range(e):
            pre = dp[j]
            if pre == 0: continue
            partners = to_love[i] & j
            for p in range(n):
                if partners & 1:
                    bitp = 1 << p
                    dp[j - bitp] = (dp[j - bitp] + pre) % md
                partners >>= 1
        # print(dp)
    print(dp[0])

main()


Fixed submission:
def f(s, i):
    if i == n:
        return 1
    if memo[s] != -1:
        return memo[s]
    re = 0
    for j in range(n):
        if aij[i][j] and s & (1 << j):
            re += f(s - (1 << j), i + 1)
    re = memo[s] = re % md
    return re


md = 10 ** 9 + 7
n = int(input())
aij = [list(map(int, input().split())) for _ in range(n)]
memo = [-1] * (1 << n)
s = (1 << n) - 1
print(f(s, 0))