Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()

l=["A","B","C","D","E","F","G","H","I","J","K","L","M","","O","P","Q","R","S","T","U","V","W","X","Y","Z"]

ans=""

for a in s:
  index = l.index(a)
  index=(index+n)%26
  ans += l[index]

print(ans)

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

l=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]

ans=""

for a in s:
  index = l.index(a)
  index=(index+n)%26
  ans += l[index]

print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()

l=["A","B","C","D","E","F","G","H","I","J","K","L","M","L","O","P","Q","R","S","T","U","V","W","X","Y","Z"]

ans=""

for a in s:
  index = l.index(a)
  index=(index+n)%26
  ans += l[index]

print(ans)

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

l=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]

ans=""

for a in s:
  index = l.index(a)
  index=(index+n)%26
  ans += l[index]

print(ans)
Buggy python submission (verdict: Runtime Error):
import math

a, b = map(int, input().split())

ans = 0
g = math.gcd(a, b)

i = 2
table = []

while i * i <= g:
    while g % i == 0:
        g //= i
        table.append(i)
    i += 1
if g > 1:
    table.append(g)

print(len(set(table)) + 1)

Fixed submission:
import fractions

a, b = map(int, input().split())

ans = 0
g = fractions.gcd(a, b)

i = 2
table = []

while i * i <= g:
    while g % i == 0:
        g //= i
        table.append(i)
    i += 1
if g > 1:
    table.append(g)

print(len(set(table)) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
# print(dic)

ans = 0
l = []
for j in range(1, m+1):
    if j in dic.keys():
        l += dic[j]
        l.sort()
    #print(l)
    if l:
        ans += l[-1]
        l.pop()

print(ans)

Fixed submission:
import heapq

n, m = map(int, input().split())

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]

ans = 0
l = []
heapq.heapify(l)
for j in range(1, m+1):
    if j in dic.keys():
        for x in dic[j]:
            heapq.heappush(l, -x)
    if l:
        ans += -l[0]
        heapq.heappop(l)

print(ans)

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

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
# print(dic)

ans = 0
l = []
for j in range(1, m+1):
    if j in dic.keys():
        l += dic[j]
        l.sort()
    #print(l)
    if l:
        ans += l[-1]
        l.pop()

print(ans)

Fixed submission:
import heapq

n, m = map(int, input().split())

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]

ans = 0
l = []
heapq.heapify(l)
for j in range(1, m+1):
    if j in dic.keys():
        for x in dic[j]:
            heapq.heappush(l, -x)
    if l:
        ans += -l[0]
        heapq.heappop(l)

print(ans)

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

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
# print(dic)

ans = 0
l = []
for j in range(1, m+1):
    if j in dic.keys():
        l += dic[j]
        l.sort()
    #print(l)
    if l:
        ans += l[-1]
        l = l[:-1]

print(ans)

Fixed submission:
import heapq

n, m = map(int, input().split())

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]

ans = 0
l = []
heapq.heapify(l)
for j in range(1, m+1):
    if j in dic.keys():
        for x in dic[j]:
            heapq.heappush(l, -x)
    if l:
        ans += -l[0]
        heapq.heappop(l)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]
l = []

for i in range(n):
    if i == 0:
        l.append(a[i])
        continue
    for j in range(len(l)):
        if l[j] < a[i]:
            l[j]=(a[i])
            break
    else:
        l.append(a[i])

print(len(l))

Fixed submission:
from bisect import bisect_left
from collections import deque

n = int(input())
A = [int(input()) for _ in range(n)]

D = deque([])

for a in A:
    i = bisect_left(D, a)
    if i == 0:
        D.appendleft(a)
    else:
        D[i-1] = a

print(len(D))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
while a:
    b = a[:]
    for i in range(len(a)):
        if i == 0:
            b.remove(a[i])
        elif a[i] > a[i-1]:
            b.remove(a[i])
    ans += 1
    a = b

print(ans)

Fixed submission:
from bisect import bisect_left
from collections import deque

n = int(input())
A = [int(input()) for _ in range(n)]

D = deque([])

for a in A:
    i = bisect_left(D, a)
    if i == 0:
        D.appendleft(a)
    else:
        D[i-1] = a

print(len(D))
Buggy python submission (verdict: Runtime Error):
l, r = map(int, input().split())

numbers = list(range(l, r+1))

if r-l>2019:
    print(0)
    exit()


amari = list(set([x%2019 for x in numbers]))


cnt = 2019
for i in range(len(amari)):
    for j in range(len(amari)):
        if i == j:
            continue
        if amari[i]*amari[j]%2019 < cnt:
            cnt = amari[i]*amari[j]%2019


print(cnt)

Fixed submission:
l, r = map(int, input().split())

if r-l>2019:
    print(0)
    exit()

numbers = list(range(l, r+1))


amari = list(set([x%2019 for x in numbers]))
#print(amari)


cnt = 2019
for i in range(len(amari)):
    for j in range(len(amari)):
        if i == j:
            continue
        if amari[i]*amari[j]%2019 < cnt:
            cnt = amari[i]*amari[j]%2019


print(cnt)

Buggy python submission (verdict: Runtime Error):
l, r = map(int, input().split())

numbers = list(range(l, r+1))

amari = list(set([x%2019 for x in numbers]))

mods = []
for i in range(len(amari)):
    for j in range(len(amari)):
        if i == j:
            continue
        mods.append((amari[i]*amari[j]%2019))

print(min(mods))

Fixed submission:
l, r = map(int, input().split())

if r-l>2019:
    print(0)
    exit()

numbers = list(range(l, r+1))


amari = list(set([x%2019 for x in numbers]))
#print(amari)


cnt = 2019
for i in range(len(amari)):
    for j in range(len(amari)):
        if i == j:
            continue
        if amari[i]*amari[j]%2019 < cnt:
            cnt = amari[i]*amari[j]%2019


print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))
all_rain = sum(l)
ans = []

for i in range(n):
    now = (i+2)%n
    others = 0
    while now%n != (i+1)%n:
        others += l[(now-1)%n]
        now = (now+2)%n
    ans.append(str(all_rain-others*2))

print(" ".join(ans))

Fixed submission:
n = int(input())
l = list(map(int, input().split()))
ans = []

cnt =1
rain_others = 0
while cnt != n:
    rain_others += l[cnt] * 2
    cnt += 2
ans.append(sum(l)-rain_others)

for i in range(1, n):
    ans.append(l[i-1]*2-ans[i-1])

print(" ".join(list(map(str, ans))))
Buggy python submission (verdict: Runtime Error):
import math

n, k = map(int, input().split())

def cmb(n, r):
    return math.factorial(n)// (math.factorial(n-r) * math.factorial(r))

for i in range(k):
    if i <= k:
        print(cmb(n-k+1, i+1) * cmb(k-1, i) % 1000000007)
    else:
        print(0)

Fixed submission:
import math

n, k = map(int, input().split())

def cmb(n, r):
    return math.factorial(n)// (math.factorial(n-r) * math.factorial(r))

for i in range(k):
    if i <= n-k:
        print(cmb(n-k+1, i+1) * cmb(k-1, i) % 1000000007)
    else:
        print(0)
Buggy python submission (verdict: Runtime Error):
import math

def lcm(x, y):
    return x*y//math.gcd(x, y)

def func(n, p, q):
    return n - (n//p + n//q - n//lcm(p, q))

a, b, c, d = map(int,input().split())

print(func(b, c, d) - func(a-1, c, d))

Fixed submission:
import fractions

def lcm(x, y):
    return x*y//fractions.gcd(x, y)

def func(n, p, q):
    return n - (n//p + n//q - n//lcm(p, q))

a, b, c, d = map(int,input().split())

print(func(b, c, d) - func(a-1, c, d))

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

def lcm(x, y):
    return x*y//math.gcd(x, y)

def func(n, p, q):
    return n - (n//p + n//q - n//lcm(p, q))

a, b, c, d = map(int,input().split())

print(func(b, c, d) - func(a-1, c, d))

Fixed submission:
import fractions

def lcm(x, y):
    return x*y//fractions.gcd(x, y)

def func(n, p, q):
    return n - (n//p + n//q - n//lcm(p, q))

a, b, c, d = map(int,input().split())

print(func(b, c, d) - func(a-1, c, d))
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
s = set(range(1, n+1))

for i in range(m):
    l, r = map(int, input().split())
    s &= set(range(l, r+1))

print(len(s))

Fixed submission:
n, m = map(int, input().split())
l, r = 1, n
for i in range(m):
    li, ri = map(int, input().split())
    if ri<l or r<li:
        print(0)
        exit()
    if l<=li and ri<=r:
        l, r = li, ri
    elif l<=ri<=r:
        r = ri
    elif l<=li<=r:
        l = li
    else:
        continue

print(r-l+1)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
s = set(range(1, n+1))

for i in range(m):
    l, r = map(int, input().split())
    s &= set(range(l, r+1))

print(len(s))

Fixed submission:
n, m = map(int, input().split())
l, r = 1, n
for i in range(m):
    li, ri = map(int, input().split())
    if ri<l or r<li:
        print(0)
        exit()
    if l<=li and ri<=r:
        l, r = li, ri
    elif l<=ri<=r:
        r = ri
    elif l<=li<=r:
        l = li
    else:
        continue

print(r-l+1)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]

BC.sort(reverse=True)
cnt = 0
L = []
for b, c in BC:
    if cnt == n:
        break
    if cnt + b > n:
        b = n-cnt
    for _ in range(b):
        A.append(c)

A.sort(reverse=True)

print(sum(A[:n]))

Fixed submission:
from operator import itemgetter

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]


BC.sort(reverse=True, key=itemgetter(1))
cnt = 0
for b, c in BC:
    if cnt + b > n:
        b = n-cnt
    for _ in range(b):
        A.append(c)
    cnt += b
    if cnt == n:
        break

A.sort(reverse=True)

print(sum(A[:n]))

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

n, m = map(int, input().split())
A = list(map(int, input().split()))

heapq.heapify(A)

for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        tmp = heapq.heappop(A)
        if tmp >= c:
            heapq.heappush(A, tmp)
            break
        heapq.heappush(A, c)

print(sum(A))

Fixed submission:
from operator import itemgetter

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]


BC.sort(reverse=True, key=itemgetter(1))
cnt = 0
for b, c in BC:
    if cnt + b > n:
        b = n-cnt
    for _ in range(b):
        A.append(c)
    cnt += b
    if cnt == n:
        break

A.sort(reverse=True)

print(sum(A[:n]))

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

for _ in range(m):
    b, c = map(int, input().split())
    a += [c]*b

a.sort(reverse=True)

print(sum(a[:n]))

Fixed submission:
from operator import itemgetter

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]


BC.sort(reverse=True, key=itemgetter(1))
cnt = 0
for b, c in BC:
    if cnt + b > n:
        b = n-cnt
    for _ in range(b):
        A.append(c)
    cnt += b
    if cnt == n:
        break

A.sort(reverse=True)

print(sum(A[:n]))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = list(map(int,input().split()))
ans = 0

for _ in range(m):
    b, c = map(int, input().split())
    a += [c]*b

a.sort(reverse=True)

for i in range(n):
    ans += a[i]

print(ans)

Fixed submission:
from operator import itemgetter

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]


BC.sort(reverse=True, key=itemgetter(1))
cnt = 0
for b, c in BC:
    if cnt + b > n:
        b = n-cnt
    for _ in range(b):
        A.append(c)
    cnt += b
    if cnt == n:
        break

A.sort(reverse=True)

print(sum(A[:n]))
Buggy python submission (verdict: Runtime Error):
s = input()

front = s[:2]
back =s[2:]

if (front == "00" or back == "00") or (front > 13 and back >13):
    print("NA")
elif 1 <= int(back) <= 12:
    if 1 <= int() <= 12:
        print("AMBIGUOUS")
    else:
        print("YYMM")
else:
    print("MMYY")

Fixed submission:
s = input()

front = int(s[:2])
back = int(s[2:])

if 1 <= front <= 12:
    if 1 <= back <=12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if 1<= back <= 12:
        print("YYMM")
    else:
        print("NA")
Buggy python submission (verdict: Runtime Error):
from collections import deque

n = int(input())

distance = [-1] * n

length = [[0] * n for _ in range(n)]
edge = [[] for _ in range(n)]


for _ in range(n-1):
    u, v, w = map(int, input().split())
    u, v = u-1, v-1
    edge[u].append(v)
    edge[v].append(u)
    length[u][v] = w
    length[v][u] = w

D = deque([0])
distance[0] = 0

while D:
    now = D.popleft()
    for i in edge[now]:
        if distance[i] == -1:
            distance[i] = (distance[now] + length[now][i]) % 2
            D.append(i)

for i in distance:
    print(i)

Fixed submission:
from collections import deque

n = int(input())

distance = [-1] * n

edge = [dict() for _ in range(n)]

for _ in range(n-1):
    u, v, w = map(int, input().split())
    u, v = u-1, v-1
    edge[u][v] = w
    edge[v][u] = w

D = deque([0])
distance[0] = 0

while D:
    now = D.popleft()
    for i in edge[now]:
        if distance[i] == -1:
            distance[i] = (distance[now] + edge[now][i]) % 2
            D.append(i)

for i in distance:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()

cnt = [0]*(n-1)

for i in range(n-1):
    if s[i:i+2] == "AC":
        cnt[i] = 1

for j in range(q):
    l, r = map(int, input().split())
    print(sum(cnt[l-1:r-1]))

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

cnt = [0]*(n)

plus = 0
for i in range(n-1):
    if s[i:i+2] == "AC":
        plus += 1
    cnt[i+1] = plus

for j in range(q):
    l, r = map(int, input().split())
    print(cnt[r-1]-cnt[l-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
h = list(map(int, input().split()))

def jump(x):
    if x == 1:
        return 0
    elif x == 2:
        return abs(h[1]-h[0])
    return min(jump(x-2)+abs(h[x-1]-h[x-3]), jump(x-1)+abs(h[x-1]-h[x-2]))

print(jump(n))

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

cost0 = 0
cost1 = abs(h[1]-h[0])
if n ==1:
    print(cost0)
else:
    for i in range(n-2):
        cost0, cost1 = cost1, min(cost0+abs(h[i+2]-h[i]), cost1+abs(h[i+2]-h[i+1]))
    print(cost1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
h = tuple(map(int,input().split()))

dp = [0] + [float("inf")]*(n-1)
for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])

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

dp = [0] + [float("inf")]*(n-1)

for i in range(1, n):
    for j in range(max(0, i-k), i):
        dp[i] = min(dp[i], dp[j]+abs(h[i]-h[j]))

print(dp[-1])

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

dp = [0] + [float("inf")]*(n-1)

for i in range(1, n):
    for j in range(max(0, i-k), i):
        dp[i] = min(dp[i], dp[j]+abs(h[i]-h[j]))

print(dp[-1])

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

dp = [0] + [float("inf")]*(n-1)

for i in range(1, n):
    for j in range(max(0, i-k), i):
        dp[i] = min(dp[i], dp[j]+abs(h[i]-h[j]))

print(dp[-1])

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

dp = [0] * n

for i in range(1, min(n,k)):
    memo = []
    for j in range(i):
        memo.append(dp[j]+abs(h[i]-h[j]))
    dp[i] = min(memo)

for i in range(k, n):
    memo = []
    for j in range(i-k, i):
        memo.append(dp[j]+abs(h[i]-h[j]))
    dp[i] = min(memo)
    
print(dp[n-1])

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

dp = [0] + [float("inf")]*(n-1)

for i in range(1, n):
    for j in range(max(0, i-k), i):
        dp[i] = min(dp[i], dp[j]+abs(h[i]-h[j]))

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [0]*(w+1)

for i in range(n):
    for j in range(w, wv[i][0]-1, -1):
        dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])

print(max(dp))

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

dp = [0]*(w+1)

for i in range(n):
    for j in range(w, wv[i][0]-1, -1):
        dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

v_total = sum([x[1] for x in wv])
dp = [0] + [float("inf")]*v_total

for i in range(n):
    for j in range(v_total, wv[i][1]-1, -1):
        dp[j] = min(dp[j], dp[j-wv[i][1]]+wv[i][0])

ans = 0
for i in range(v_total+1):
    if dp[i] <= w:
        ans = i
print(ans)

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

v_total = sum([x[1] for x in wv])
dp = [0] + [float("inf")]*v_total

for i in range(n):
    for j in range(v_total, wv[i][1]-1, -1):
        dp[j] = min(dp[j], dp[j-wv[i][1]]+wv[i][0])

ans = 0
for i in range(v_total+1):
    if dp[i] <= w:
        ans = i
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = tuple(input())
t = tuple(input())
n = len(s)
m = len(t)

dp = [[0]*(m+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

res = ''
while n != 0 and m != 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        n -= 1
        m -= 1
        res = s[n] + res
print(res)

Fixed submission:
s = tuple(input())
t = tuple(input())
n = len(s)
m = len(t)

dp = [[0]*(m+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

res = ''
while n != 0 and m != 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        n -= 1
        m -= 1
        res = s[n] + res
print(res)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())

root = [[] for _ in range(n)]

for i in range(m):
    x, y = map(int, input().split())
    root[x-1].append(y-1)

memo = ["empty" for _ in range(n)]

def dp(x):
    if memo[x] == "empty":
        res = 0
        for i in root[x]:
            res = max(res, dp(i)+1)
        memo[x] = res

    return memo[x]

for j in range(n):
    dp(j)

print(max(memo))

Fixed submission:
import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())

root = [[] for _ in range(n)]

for i in range(m):
    x, y = map(int, input().split())
    root[x-1].append(y-1)

memo = ["empty" for _ in range(n)]

def dp(x):
    if memo[x] == "empty":
        res = 0
        for i in root[x]:
            res = max(res, dp(i)+1)
        memo[x] = res

    return memo[x]

for j in range(n):
    dp(j)

print(max(memo))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

mod = 10**9+7

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]

cnt = [[0]*w for _ in range(h)]
cnt[0][0] = 1

D = deque()
D.append((0, 0))

dxdy = [(0, 1), (1, 0)]

appended =  [[False]*w for _ in range(h)]
appended[0][0] = True
while D:
  p = D.popleft()
  if p == (h-1, w-1):
    break
  for k in range(2):
    nx = p[0] + dxdy[k][0]
    ny = p[1] + dxdy[k][1]
    if 0<=nx<h and 0<=ny<w and maze[nx][ny]==".":
      cnt[nx][ny] += cnt[p[0]][p[1]]
      cnt[nx][ny] %= mod
      if appended[nx][ny]==False:
        D.append((nx, ny))
        appended[nx][ny] = True

print(cnt[h-1][w-1])

Fixed submission:
from collections import deque

mod = 10**9+7

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]

cnt = [[0]*w for _ in range(h)]
cnt[0][0] = 1

D = deque()
D.append((0, 0))

dxdy = [(0, 1), (1, 0)]

appended =  [[False]*w for _ in range(h)]
appended[0][0] = True
while D:
  p = D.popleft()
  if p == (h-1, w-1):
    break
  for k in range(2):
    nx = p[0] + dxdy[k][0]
    ny = p[1] + dxdy[k][1]
    if 0<=nx<h and 0<=ny<w and maze[nx][ny]==".":
      cnt[nx][ny] += cnt[p[0]][p[1]]
      cnt[nx][ny] %= mod
      if appended[nx][ny]==False:
        D.append((nx, ny))
        appended[nx][ny] = True

print(cnt[h-1][w-1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
P = list(map(float, input().split()))

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

for i in range(n):
  for j in range(n+1):
    if j==0:
      DP[0][i+1] = DP[0][i] * (1-P[i])
    else:
      DP[j][i+1] = DP[j][i] * (1-P[i]) + DP[j-1][i] * P[i]

ans = 0
for k in range(n//2+1, n+1):
  ans += DP[k][n]

print(ans)

Fixed submission:
n = int(input())
P = list(map(float, input().split()))

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

for i in range(n):
  for j in range(n+1):
    if j==0:
      DP[0][i+1] = DP[0][i] * (1-P[i])
    else:
      DP[j][i+1] = DP[j][i] * (1-P[i]) + DP[j-1][i] * P[i]

ans = 0
for k in range(n//2+1, n+1):
  ans += DP[k][n]

print(ans)