Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    k = ni()

    for i in range(len(s)):
        if si == "a":
            continue
        si = ord(s[i]) - 97
        if k >= 26 - si:
            s[i] = "a"
            k -= 97 + 26 - si
            if k == 0:
                break

    s[-1] = chr(97 + (ord(s[-1]) - 97 + k) % 26)

    print(*s, sep="")


if __name__ == '__main__':
    main()


Fixed submission:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    k = ni()

    for i in range(len(s)):
        if s[i] == "a":
            continue
        si = ord(s[i]) - 97
        if k >= 26 - si:
            s[i] = "a"
            k -= 26 - si
            if k == 0:
                break

    s[-1] = chr(97 + (ord(s[-1]) - 97 + k) % 26)

    print(*s, sep="")


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

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

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

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

uf1=UnionFind(n)
for i in range(m):
    a,b=map(int, input().split()) #a,b:つながっている辺
    uf1.union(a-1,b-1)

for i in range(n):
    uf1.find(i)
from collections import Counter
c=Counter(uf1.par)
print(max(c.values()))


Fixed submission:
d,t,s=map(int, input().split())
if t*s>=d:
    print('Yes')
else: print('No')
Buggy python submission (verdict: Runtime Error):
n,k=map(int, input().split())
P = list(map(int, input().split()))
P=[i-1 for i in P]
C = list(map(int, input().split()))
visited=[-1]*n
group=[]

for i in range(n):
    if visited[i]!=-1:
        continue
    visited[i]=0
    group.append([i])
    now=P[i]
    while now!=i:
        group[-1].append(now)
        visited[now]=0
        now=P[now]
dp=[[0] for i in range(n)]

from collections import defaultdict
d=defaultdict(list)
for g in group:
    for i in g:
        now=i
        point=0
        for j in range(len(g)):
            now=P[now]
            point+=C[now]
            d[i].append(point)
ans=-float('inf')

for i in range(n):
    dic=d[i]
    leng=len(dic)
    if k<=leng:
        ans=max(ans, max(dic[:k]))
    else:
        if dic[-1]<=0:
            ans=max(ans, max(dic))
        else:
            ans=max(ans,(k//leng)*dic[-1]+max(dic[:k%leng]))
            ans=max(ans,(k//leng-1)*dic[-1]+max(dic))
print(ans)

Fixed submission:
n,k=map(int, input().split())
P = list(map(int, input().split()))
P=[i-1 for i in P]
C = list(map(int, input().split()))
visited=[-1]*n
group=[]

for i in range(n):
    if visited[i]!=-1:
        continue
    visited[i]=0
    group.append([i])
    now=P[i]
    while now!=i:
        group[-1].append(now)
        visited[now]=0
        now=P[now]
dp=[[0] for i in range(n)]

from collections import defaultdict
d=defaultdict(list)
for g in group:
    for i in g:
        now=i
        point=0
        for j in range(len(g)):
            now=P[now]
            point+=C[now]
            d[i].append(point)
ans=-float('inf')

for i in range(n):
    dic=d[i]
    leng=len(dic)
    if k<=leng:
        ans=max(ans, max(dic[:k]))
    else:
        if dic[-1]<=0:
            ans=max(ans, max(dic))
        else:
            if k%leng!=0:
                ans=max(ans,(k//leng)*dic[-1]+max(dic[:k%leng]))
            ans=max(ans,(k//leng-1)*dic[-1]+max(dic))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
def decomp(m):
    pf=defaultdict(int)
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]+=1
            m//=i
    if m>1:pf[m]=1
    return (pf[2], pf[5])

n=int(input())
table=[[0]*50 for _ in range(50)]
ans=0
for i in range(n):
    a=input()
    ax=round(float(a)*(10**9))
    p2,p5=decomp(ax)
    if i!=0:
        for j in range(18-p2,19):
            ans+=sum(table[j][18-p5:])
    table[p2][p5]+=1

print(ans)

Fixed submission:
def decomp(m):
    p2=0
    p5=0
    while m%2==0:
        m//=2
        p2+=1
    while m%5==0:
        m//=5
        p5+=1
    return p2,p5

n=int(input())
table=[[0]*50 for _ in range(50)]
ans=0
for i in range(n):
    a=input().split('.')
    if len(a)==1:
        ax=int(a[0]+'0'*9)
    else:
        ax=int(a[0]+a[1]+'0'*(9-len(a[1])))
    p2,p5=decomp(ax)
    if i!=0:
        for j in range(18-p2,50):
            ans+=sum(table[j][18-p5:])
    table[p2][p5]+=1

print(ans)
Buggy python submission (verdict: Runtime Error):
n,k=map(int, input().split())
a = list(map(int, input().split()))
a=sorted(a)
if k==0:
    print(max(a))
    exit()

lo=0
hi=2*(10**9)
oldmid=0
while True:
    mid=(hi+lo)//2
    cnt=0
    for i in range(n):
        cnt+=(a[i]*2)//mid
    if cnt>k:
        lo=mid
    elif cnt<=k:
        hi=mid
    if oldmid==mid:
        print(mid//2+mid%2)
        break
    oldmid=mid


Fixed submission:
n,k=map(int, input().split())
a = list(map(int, input().split()))
a=sorted(a,reverse=True)
if k==0:
    print(max(a))
    exit()
import math
lo=0
hi=10**9
oldmid=0
while True:
    mid=(hi+lo)/2
    cnt=0
    for i in range(n):
        cnt+=round(a[i]/mid-0.5)
    if cnt>k:
        lo=mid
    elif cnt<=k:
        hi=mid
    if oldmid-0.000001<=(hi+lo)/2<=oldmid+0.000001:
        print(min(math.ceil(lo), max(a)))
        break
    oldmid=mid
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = list(input())
x=[1 if s=='1' else 0 for s in x]
sumx=sum(x)

neg=0
pos=0

for i in range(n):
    neg+=pow(2,(n-i-1),sumx-1)*x[i]
    neg%=sumx-1
    pos+=pow(2,(n-i-1),sumx+1)*x[i]
    pos%=sumx+1

pops=[]

for i in range(n):
    if x[i]==1:
        if sumx==1:
            pops.append(-1)
        else:
            pops.append((neg-pow(2,(n-i-1),sumx-1)+sumx-1)%(sumx-1))
    elif x[i]==0:
        pops.append((pos+pow(2,(n-i-1),sumx+1))%(sumx+1))

ans=[0]*(2*10**5+1)

for i in range(1,2*10**5+1):
    cnt=0
    tmp=i+0
    while tmp>0:
        cnt+=1
        b=bin(tmp)[2:]
        b=sum([1 if s=='1' else 0 for s in b])
        tmp%=b
    ans[i]=cnt

for p in pops:
    if p!=-1:
        print(ans[p]+1)
    else:
        print(0)

Fixed submission:
n = int(input())
x = list(input())
x=[1 if s=='1' else 0 for s in x]
sumx=sum(x)

neg=0
pos=0

for i in range(n):
    if sumx-1!=0:
        neg+=pow(2,(n-i-1),sumx-1)*x[i]
        neg%=sumx-1
    pos+=pow(2,(n-i-1),sumx+1)*x[i]
    pos%=sumx+1

pops=[]

for i in range(n):
    if x[i]==1:
        if sumx==1:
            pops.append(-1)
        else:
            pops.append((neg-pow(2,(n-i-1),sumx-1)+sumx-1)%(sumx-1))
    elif x[i]==0:
        pops.append((pos+pow(2,(n-i-1),sumx+1))%(sumx+1))

ans=[0]*(2*10**5+1)

for i in range(1,2*10**5+1):
    cnt=0
    tmp=i+0
    while tmp>0:
        cnt+=1
        b=bin(tmp)[2:]
        b=sum([1 if s=='1' else 0 for s in b])
        tmp%=b
    ans[i]=cnt

for p in pops:
    if p!=-1:
        print(ans[p]+1)
    else:
        print(0)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

D=int(input())
*c,=map(int,input().split())
c=np.array(c)
s=[]
for i in range(D):
    *x,=map(int,input().split())
    s.append(x)

s=np.array(s).reshape((D,26))

def score(T):
    last=[-1]*26
    v=0
    for d in range(D):
        v+=s[d][T[d]-1]
        last[T[d]-1]=d
        for i in range(26):
            v-=c[i]*(d-last[i])
    return v

import random
best=0

for x in range(4000):
    if x==0:
        tmp=[random.randint(1, 26) for _ in range(D)]
        tbest=tmp+[]
    else:
        tmp=[random.randint(1, 26) for _ in range(D)]
    sc=score(tmp)
    if (10**6+sc)>best:
        tbest=tmp+[]
        best=10**6+sc
    else:
        continue

for i in range(D):
    print(tbest[i])

Fixed submission:
D=int(input())
*c,=map(int,input().split())
s=[]
for i in range(D):
    *x,=map(int,input().split())
    s.append(x)

def score(T):
    last=[-1]*26
    v=0
    for d in range(D):
        v+=s[d][T[d]-1]
        last[T[d]-1]=d
        for i in range(26):
            v-=c[i]*(d-last[i])
    return v

import random
best=0

for x in range(4000):
    if x==0:
        tmp=[random.randint(1, 26) for _ in range(D)]
        tbest=tmp
    else:
        tmp=[random.randint(1, 26) for _ in range(D)]
    if score(tmp)>best:
        tbest=tmp
    else:
        continue

for t in tbest:
    print(t)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
table=[[] for _ in range(n+1)]
import copy
from collections import defaultdict
def yaku(m):
    pf=defaultdict(int)
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
            if table[m]!=[]:
                tmp=copy.deepcopy(table[m])
                for key in pf.keys():
                    tmp[key]+=pf[key]
                return tmp
    if m>1:pf[m]=1
    return pf

ans=1
for m in range(2,n+1):
    table[m]=yaku(m)
    tmp=1
    for k in table[m].keys():
        tmp*=(table[m][k]+1)
    ans+=m*tmp

print(ans)

Fixed submission:
n = int(input())
table=[1 for _ in range(n+1)]
ans=0
for x in range(1,n+1):
    y=n//x
    ans+=y*(y+1)*x//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,s=map(int,input().split())
*A,=map(int,input().split())
mod=998244353
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(s+1):
        if A[i]+j<s+1:
            dp[i+1][j+A[i]]+=dp[i][j]
        dp[i+1][j]+=2*dp[i][j]
        dp[i+1][j]%=mod
print(dp[-1][-1])


Fixed submission:
n,s=map(int,input().split())
*A,=map(int,input().split())
mod=998244353
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(s+1):
        if A[i]+j<s+1:
            dp[i+1][j+A[i]]=(dp[i+1][j+A[i]]+dp[i][j])%mod
        dp[i+1][j]=(dp[i+1][j]+2*dp[i][j])%mod
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,k=map(int, input().split())
ans=0
for i in range(k):
    if a>0:
        ans+=1
        a-=1
    elif b>0:
        b-=1
    elif c>0:
        ans-=1
        c-=1
print(ans)

Fixed submission:
a,b,c,k=map(int, input().split())
ans=0
if a>=k:
    print(k)
    exit()
if b>=k-a:
    print(a)
    exit()
else:
    print(a-(k-b-a))
    exit()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A=list(map(int,input().split()))
cnt=0
import numpy as np
table=np.array([[0]*(n+1) for i in range(n)])
B=[]
C=[]
for i,a in enumerate(A):
    B.append(A[i]+i)
    C.append(A[i]-i)
from collections import Counter
Bd=dict(Counter(B))
Cd=dict(Counter(C))
cnt=0
for k in Bd.keys():
    try:
        cnt+=Bd[k]*Cd[-k]
    except KeyError:
        continue
print(cnt)

Fixed submission:
n = int(input())
A=list(map(int,input().split()))
cnt=0
B=[]
C=[]
for i,a in enumerate(A):
    B.append(A[i]+i)
    C.append(A[i]-i)
from collections import Counter
Bd=dict(Counter(B))
Cd=dict(Counter(C))
cnt=0
for k in Bd.keys():
    try:
        cnt+=Bd[k]*Cd[-k]
    except KeyError:
        continue
print(cnt)

Buggy python submission (verdict: Runtime Error):
n = int(input())
A=list(map(int,input().split()))
cnt=0
import numpy as np
table=np.array([[0]*(n+1) for i in range(n)])
B=[]
C=[]
for i,a in enumerate(A):
    B.append(A[i]+i)
    C.append(A[i]-i)
from collections import Counter
Bd=dict(Counter(B))
Cd=dict(Counter(C))
cnt=0
for k in Bd.keys():
    try:
        cnt+=Bd[k]*Cd[-k]
    except KeyError:
        continue
print(cnt)

Fixed submission:
n = int(input())
A=list(map(int,input().split()))
cnt=0
B=[]
C=[]
for i,a in enumerate(A):
    B.append(A[i]+i)
    C.append(A[i]-i)
from collections import Counter
Bd=dict(Counter(B))
Cd=dict(Counter(C))
cnt=0
for k in Bd.keys():
    try:
        cnt+=Bd[k]*Cd[-k]
    except KeyError:
        continue
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A=list(map(int,input().split()))
cnt=0
for i in range(1,n):
    for j in range(n-i):
        if j+i>n-1:
            break
        if A[j]+A[j+i]==i:
            cnt+=1
print(cnt)

Fixed submission:
n = int(input())
A=list(map(int,input().split()))
cnt=0
B=[]
C=[]
for i,a in enumerate(A):
    B.append(A[i]+i)
    C.append(A[i]-i)
from collections import Counter
Bd=dict(Counter(B))
Cd=dict(Counter(C))
cnt=0
for k in Bd.keys():
    try:
        cnt+=Bd[k]*Cd[-k]
    except KeyError:
        continue
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())
s=[int(i) for i in s]
last_mod=0
from collections import defaultdict
c=defaultdict(int)
c[0]+=1
for i in range(len(s)):
    now=(s[-1-i]*(10**i))%2019
    c[(last_mod+now)%2019]+=1
    last_mod=(last_mod+now)%2019
ans=0
for k in c.keys():
    ans+=c[k]*(c[k]-1)//2
print(ans)

Fixed submission:
s=list(input())
s=[int(i) for i in s]
now=0
c=[0]*2019
c[0]=1
for n,i in enumerate(s[::-1]):
    now+=i*pow(10,n,2019)
    c[now%2019]+=1
ans=0
for k in range(2019):
    ans+=c[k]*(c[k]-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())
s=[int(i) for i in s]
mods=[0]
for i in range(len(s)):
    now=(s[-1-i]*(10**i))%2019
    mods.append((mods[-1]+now)%2019)
mods=mods[::-1]
from collections import Counter
c=dict(Counter(mods))
ans=0
for k in c.keys():
    ans+=c[k]*(c[k]-1)//2
print(ans)

Fixed submission:
s=list(input())
s=[int(i) for i in s]
now=0
c=[0]*2019
c[0]=1
for n,i in enumerate(s[::-1]):
    now+=i*pow(10,n,2019)
    c[now%2019]+=1
ans=0
for k in range(2019):
    ans+=c[k]*(c[k]-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
s=[int(i) for i in s]

from collections import defaultdict
import copy
d=defaultdict(int)
ans=0
for i in range(len(s)):
    newd=defaultdict(int)
    now=s[i]
    for k in d.keys():
        newd[(k*10+now)%2019]+=d[k]
    newd[now]+=1
    ans+=newd[0]
    d=copy.deepcopy(newd)

print(ans)

Fixed submission:
s=list(input())
s=[int(i) for i in s]
now=0
c=[0]*2019
c[0]=1
for n,i in enumerate(s[::-1]):
    now+=i*pow(10,n,2019)
    c[now%2019]+=1
ans=0
for k in range(2019):
    ans+=c[k]*(c[k]-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
p=3.1415

print(2*n*p)

Fixed submission:
n,m=map(int, input().split())
A = list(map(int, input().split()))
if n-sum(A)<0:
    print(-1)
    exit()

print(n-sum(A))

Buggy python submission (verdict: Runtime Error):
n = int(input())
p=3.142
print(2*n*p)

Fixed submission:
n,m=map(int, input().split())
A = list(map(int, input().split()))
if n-sum(A)<0:
    print(-1)
    exit()

print(n-sum(A))

Buggy python submission (verdict: Runtime Error):
n = int(input())
p=3.142
print(2*n*p)


Fixed submission:
n,m=map(int, input().split())
A = list(map(int, input().split()))
if n-sum(A)<0:
    print(-1)
    exit()

print(n-sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
from fractions import gcd

ans=0
for i in range(k):
    ans+=i+1
    for j in range(i+1, k):
        x=gcd(i+1,j+1)
        ans+=6*gcd(i+1,j+1)
        for l in range(j+1, k):
            ans+=6*gcd(x,l+1)
print(ans)


Fixed submission:
k = int(input())
from fractions import gcd

ans=0
for i in range(k):
    ans+=i+1
    for j in range(i+1, k):
        x=gcd(i+1,j+1)
        ans+=6*gcd(i+1,j+1)
        for l in range(j+1, k):
            ans+=6*gcd(x,l+1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
from fractions import gcd

# when input is list type
def list_gcd(a):
    x=a[0]
    for i in range(1,len(a)):
        x=gcd(x,a[i])
    return x

ans=0
for i in range(k):
    ans+=i+1
    for j in range(i+1, k):
        ans+=3*list_gcd([i+1,j+1])
        ans+=3*list_gcd([i+1,j+1])
        for l in range(j+1, k):
            ans+=6*list_gcd([i+1,j+1,l+1])
print(ans)

Fixed submission:
k = int(input())
from fractions import gcd

ans=0
for i in range(k):
    ans+=i+1
    for j in range(i+1, k):
        x=gcd(i+1,j+1)
        ans+=6*gcd(i+1,j+1)
        for l in range(j+1, k):
            ans+=6*gcd(x,l+1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = list(input())

R=[0]*n
G=[0]*n
B=[0]*n

for i in range(n):
    if s[i]=='R':
        R[i]=1
    elif s[i]=='G':
        G[i]=1
    elif s[i]=='B':
        B[i]=1

ans=0
for i in range(n):
    if R[i]==1:
        lG=sum(G[:i])
        lB=sum(B[:i])
        rG=sum(G[i:])
        rB=sum(B[i:])
        ans+=(lG+rG)*(lB+rB)
        for j in range(1,n//2+1):
            if R[i]==1:
                if 0<=i-j<n and 0<=i+j<n:
                    if G[i-j]==1 and B[i+j]==1:
                        ans-=1
                    if B[i-j]==1 and G[i+j]==1:
                        ans-=1
                if 0<=i-2*j<n:
                    if G[i-j]==1 and B[i-2*j]==1:
                        ans-=1
                    if B[i-j]==1 and G[i-2*j]==1:
                        ans-=1
                if 0<=i+2*j<n:
                    if G[i+j]==1 and B[i+2*j]==1:
                        ans-=1
                    if B[i+j]==1 and G[i+2*j]==1:
                        ans-=1

print(ans)


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

R=[0]*n
G=[0]*n
B=[0]*n

for i in range(n):
    if s[i]=='R':
        R[i]=1
    elif s[i]=='G':
        G[i]=1
    elif s[i]=='B':
        B[i]=1

ans=0
for i in range(n):
    if R[i]==1:
        lG=sum(G[:i])
        lB=sum(B[:i])
        rG=sum(G[i:])
        rB=sum(B[i:])
        ans+=(lG+rG)*(lB+rB)
        for j in range(1,n//2+1):
            if R[i]==1:
                if 0<=i-j<n and 0<=i+j<n:
                    if G[i-j]==1 and B[i+j]==1:
                        ans-=1
                    if B[i-j]==1 and G[i+j]==1:
                        ans-=1
                if 0<=i-2*j<n:
                    if G[i-j]==1 and B[i-2*j]==1:
                        ans-=1
                    if B[i-j]==1 and G[i-2*j]==1:
                        ans-=1
                if 0<=i+2*j<n:
                    if G[i+j]==1 and B[i+2*j]==1:
                        ans-=1
                    if B[i+j]==1 and G[i+2*j]==1:
                        ans-=1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
inf = 10**16
N = int(input())
A = list(map(int, input().split()))
dp0=[[-inf]*(2+N//2) for _ in range(N+1)]
dp1=[[-inf]*(2+N//2) for _ in range(N+1)]
dp0[0][0] = 0

for i, x in enumerate(A):
    j = i//2
    for n in (j, j + 1):
        dp0[i+1][n] = max(dp0[i][n], dp1[i][n])
        dp1[i+1][n] = dp0[i][n - 1] + x
    #print(dp0)
    #print(dp1)

print(max(dp0[N][N//2], dp1[N][N//2]))


Fixed submission:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])

Buggy python submission (verdict: Runtime Error):
inf = 10**18
N = int(input())
A = list(map(int, input().split()))
dp0=[[-inf]*(2+N//2) for _ in range(N+1)]
dp1=[[-inf]*(2+N//2) for _ in range(N+1)]
dp0[0][0] = 0

for i, x in enumerate(A):
    j = i//2
    for n in (j, j + 1):
        dp0[i+1][n] = max(dp0[i][n], dp1[i][n])
        dp1[i+1][n] = dp0[i][n - 1] + x
    #print(dp0)
    #print(dp1)

print(max(dp0[N][N//2], dp1[N][N//2]))


Fixed submission:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])

Buggy python submission (verdict: Time Limit Exceeded):
inf = float('inf')
N = int(input())
A = list(map(int, input().split()))
dp0=[[-inf]*(2+N//2) for _ in range(N+1)]
dp1=[[-inf]*(2+N//2) for _ in range(N+1)]
dp0[0][0] = 0

for i, x in enumerate(A):
    j = i//2
    for n in (j, j + 1):
        dp0[i+1][n] = max(dp0[i][n], dp1[i][n])
        dp1[i+1][n] = dp0[i][n - 1] + x
    #print(dp0)
    #print(dp1)

print(max(dp0[N][N//2], dp1[N][N//2]))


Fixed submission:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])

Buggy python submission (verdict: Time Limit Exceeded):
inf = float('inf')
N = int(input())
A = list(map(int, input().split()))
dp0=[[-inf]*(2+N//2) for _ in range(N+1)]
dp1=[[-inf]*(2+N//2) for _ in range(N+1)]
dp0[0][0] = 0

for i, x in enumerate(A):
    j = i // 2
    for n in (j, j + 1):
        dp0[i+1][n] = max(dp0[i][n], dp1[i][n])
        dp1[i+1][n] = dp0[i][n - 1] + x
    #print(dp0)
    #print(dp1)

print(max(dp0[N][N//2], dp1[N][N//2]))

Fixed submission:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])
Buggy python submission (verdict: Time Limit Exceeded):
h,w=map(int,input().split())
grid=[[1 if s=='#' else 0 for s in list(input())] for i in range(h)]
#print(grid)
black=0
maxi=1000
from collections import deque
visited=[[1000]*w for _ in range(h)]
def bfs(s):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=grid[s[0]][s[1]]
    D=[[1,0],[0,1]]
    while q:
        pre=q.pop()
        before=visited[pre[0]][pre[1]]
        for d in D:
            x=pre[0]+d[0]
            y=pre[1]+d[1]
            if 0<=x<h and 0<=y<w:
                q.append([x,y])
                visited[x][y]=min(visited[x][y],before+grid[x][y])

bfs([0,0])
print(visited[-1][-1])

Fixed submission:
h,w=map(int,input().split())
grid=[[1 if s=='#' else 0 for s in list(input())] for i in range(h)]
#print(grid)
maxi=10**5
from collections import deque
visited=[[maxi]*w for _ in range(h)]
def bfs(s):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=grid[s[0]][s[1]]
    for r in range(h):
        for c in range(w):
            if r>=1:
                visited[r][c]=min(visited[r][c],visited[r-1][c]+grid[r][c])
                if grid[r-1][c]==1:
                    visited[r][c]=min(visited[r][c],visited[r-1][c])
            if c>=1:
                visited[r][c]=min(visited[r][c],visited[r][c-1]+grid[r][c])
                if grid[r][c-1]==1:
                    visited[r][c]=min(visited[r][c],visited[r][c-1])
            

bfs([0,0])
print(visited[-1][-1])