Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

MAP=[["." for _ in range(w)] for _ in range(h)]
H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    MAP[i][j]="#"
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)

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

H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)

Buggy python submission (verdict: Time Limit Exceeded):
h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

MAP=[["." for _ in range(w)] for _ in range(h)]
H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    MAP[i][j]="#"
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
X,Y=[],[]
for i in range(h):
    if H[i]==max_h:
        X.append(i)
for i in range(w):
    if W[i]==max_w:
        Y.append(i)

flag=0
for i in X:
    for j in Y:
        if MAP[i][j]==".":
            flag=1
ans=max_w+max_h
print(ans if flag else ans-1)

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

H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)

Buggy python submission (verdict: Time Limit Exceeded):
h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

DP=[[[0,0] for _ in range(w)] for _ in range(h)]
MAP=[["." for _ in range(w)] for _ in range(h)]
for H,W in HW:
    DP[H-1][W-1]=[1,1]
    MAP[H-1][W-1]="#"

for i in range(h):
    for j in range(1,w):
        DP[i][j][0] +=DP[i][j-1][0]

for i in range(w):
    for j in range(1,h):
        DP[j][i][1] +=DP[j-1][i][1]

cnt=0
for i in range(h):
    for j in range(w):
        num=DP[i][w-1][0]+DP[h-1][j][1]
        if MAP[i][j]=="#":num -=1
        cnt=max(cnt,num)
print(cnt)

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

H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
if K==0:print(max(A));exit()

left,right=0,10**9+1
while right>left+1:
    cnt=K
    mid=(left+right)//2
    for i in range(N):
        cnt -=A[i]//mid
    if cnt>=0:right=mid
    elif cnt<0:left=mid

cnt=K
for i in range(N):
    cnt -=A[i]//left
print(left if cnt==0 else right)

Fixed submission:
from math import ceil
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
if K==0:print(max(A));exit()

left,right=0,10**9+1
while right>left+1:
    cnt=K
    mid=(left+right)//2
    for i in range(N):
        cnt -=ceil(A[i]/mid)-1
    if cnt>=0:right=mid
    elif cnt<0:left=mid

print(right)
Buggy python submission (verdict: Runtime Error):
mod=10**9+7
n,k=map(int,input().split())
A=list(map(int,input().split()))
count=k

B,C=[],[]
for i in A:
    if i>=0:B.append(i)
    else:C.append(i)

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        point=0
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                point=1
            else:ans *=C.pop()*C.pop()
        elif len(B)>=2:ans *=B.pop()*B.pop()
        elif len(C)>=2:ans *=C.pop()*C.pop()
        else:flag=0
        k -=2-point
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1
    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(reverse=True)
    for i in range(count):
        ans *=A[i]
        ans %=mod
    print(ans)

Fixed submission:
from collections import deque
import sys
input=sys.stdin.readline

mod=10**9+7
n,k=map(int,input().split())
A=list(map(int,input().split()))
cnt=k

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>=0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    num=0
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if plus>negative:
                ans *=B.popleft()
                num=1
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        else:
            ans *=B.popleft()*C.popleft()
            flag=0
        k -=2-num
    else:
        if 0<length_B:ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)


def DFS(point,left,right,cnt):
    global ans
    if point<=k:
        if cnt>ans:
            ans=cnt

    if left<n:
        if point+A[left]<=k:DFS(point+A[left],left+1,right,cnt+1)
    if right<m:
        if point+B[right]<=k:DFS(point+B[right],left,right+1,cnt+1)


n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
DFS(0,0,0,0)
print(ans)

Fixed submission:
n,m,k=map(int,input().split())
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))

for i in range(1,n+1):
    A[i]=A[i-1]+A[i]
for i in range(1,m+1):
    B[i]=B[i-1]+B[i]

ans,j=0,m
for i in range(n+1):
    if A[i]>k:break
    while B[j]>k-A[i]:
        j -=1
    ans=max(ans,i+j)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)


def DFS(point,left,right,cnt):
    global ans
    if point<=k:
        if cnt>ans:
            ans=cnt

    if left<n and point<=k:DFS(point+A[left],left+1,right,cnt+1)
    if right<m and point<=k:DFS(point+B[right],left,right+1,cnt+1)


n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
DFS(0,0,0,0)
print(ans)

Fixed submission:
n,m,k=map(int,input().split())
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))

for i in range(1,n+1):
    A[i]=A[i-1]+A[i]
for i in range(1,m+1):
    B[i]=B[i-1]+B[i]

ans,j=0,m
for i in range(n+1):
    if A[i]>k:break
    while B[j]>k-A[i]:
        j -=1
    ans=max(ans,i+j)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)


def DFS(point,left,right,cnt):
    global ans
    if point<=k:
        if cnt>ans:
            ans=cnt

    if left<n:DFS(point+A[left],left+1,right,cnt+1)
    if right<m:DFS(point+B[right],left,right+1,cnt+1)


n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
DFS(0,0,0,0)
print(ans)

Fixed submission:
n,m,k=map(int,input().split())
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))

for i in range(1,n+1):
    A[i]=A[i-1]+A[i]
for i in range(1,m+1):
    B[i]=B[i-1]+B[i]

ans,j=0,m
for i in range(n+1):
    if A[i]>k:break
    while B[j]>k-A[i]:
        j -=1
    ans=max(ans,i+j)
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n=int(input())
A=list(map(int,input().split()))
q=int(input())
BC=[list(map(int,input().split())) for _ in range(q)]

num=sum(A)
N={}
for i in A:
   if i not in N:N[i]=0
   N[i] +=1

for b,c in BC:
    dig=c-b
    num +=dig*N[b]
    print(num)
    if c not in N:N[c]=0
    N[c] +=N[b]
    N[b]=0

Fixed submission:
from collections import Counter
n=int(input())
A=list(map(int,input().split()))
q=int(input())
BC=[list(map(int,input().split())) for _ in range(q)]

num=sum(A)
N={}
for i in A:
   if i not in N:N[i]=0
   N[i] +=1

for b,c in BC:
    if b not in N:
        print(num)
        continue
    dig=c-b
    num +=dig*N[b]
    print(num)
    if c not in N:N[c]=0
    N[c] +=N[b]
    N[b]=0

Buggy python submission (verdict: Runtime Error):
from collections import Counter
n=int(input())
A=list(map(int,input().split()))
q=int(input())
BC=[list(map(int,input().split())) for _ in range(q)]

num=sum(A)
N={i+1:0 for i in range(9)}
for i in A:
    N[i] +=1

for b,c in BC:
    dig=c-b
    num +=dig*N[b]
    print(num)
    if c not in N:N[c]=0
    N[c] +=N[b]
    N[b]=0

Fixed submission:
from collections import Counter
n=int(input())
A=list(map(int,input().split()))
q=int(input())
BC=[list(map(int,input().split())) for _ in range(q)]

num=sum(A)
N={}
for i in A:
   if i not in N:N[i]=0
   N[i] +=1

for b,c in BC:
    if b not in N:
        print(num)
        continue
    dig=c-b
    num +=dig*N[b]
    print(num)
    if c not in N:N[c]=0
    N[c] +=N[b]
    N[b]=0
Buggy python submission (verdict: Runtime Error):
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())

if a+v*t>=b+w*t:
    if (b-a)%(v-w)==0:
        print("YES")
    else:print("NO")
else:print("NO")

Fixed submission:
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())

if v>w:
    if a-v*t<=b-w*t and a+v*t>=b+w*t:print("YES")
    else:print("NO")
else:print("NO")
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[n for _ range(n)]

while k!=0:
    B=[0 for _ in range(n+1)]
    for i,j in enumerate(A):
        B[max(0,i-j)] +=1
        B[min(n,i+j+1)] -=1
    for i in range(1,n):
        B[i] +=B[i-1]
    A=B[:n]
    k -=1
    if A==C:break
print(*A)

Fixed submission:
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[n for i in range(n)]

for m in range(k):
    B=[0 for _ in range(n)]
    for i in range(n):
        l,r=max(0,i-A[i]),min(n-1,i+A[i])
        B[l] +=1
        if r+1<n:B[r+1] -=1
    for i in range(n-1):
        B[i+1]=B[i]+B[i+1]
    A=B
    if A==C:break
print(*A)

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

B=[0 for _ in range(n)]

for K in range(k):
    for i in range(n):
        num=A[i]
        for j in range(max(0,i-num),min(n,i+num+1)):
            B[j] +=1
    A=B
    B=[0 for _ in range(n)]
print(*A)

Fixed submission:
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[n for i in range(n)]

for m in range(k):
    B=[0 for _ in range(n)]
    for i in range(n):
        l,r=max(0,i-A[i]),min(n-1,i+A[i])
        B[l] +=1
        if r+1<n:B[r+1] -=1
    for i in range(n-1):
        B[i+1]=B[i]+B[i+1]
    A=B
    if A==C:break
print(*A)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int,input().split()))

ans=1
for i in range(n):
    ans *=A[i]
if ans>10**18:print(-1);exit()
print(ans)

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

ans=1
if 0 in A:print(0);exit()
for i in range(n):
    ans *=A[i]
    if ans>10**18:print(-1);exit()
print(ans)
Buggy python submission (verdict: Runtime Error):
def DFS(num):
    global time
    if D[num]==0:
        D[num]=time
        time +=1
    for i in M[num]:
        if color[i]=="white":
            color[num]="gray"
            color[i]="gray"
            DFS(i)
        elif color[i]=="gray":
            color[num]="black"
            color[i]="black"
            DFS(i)
        elif color[i]=="black":
            return


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

B=[]
point,cnt=0,0
while cnt<n*2:
    point=A[point]
    B.append(point)
    point -=1
    cnt +=1

M=[set() for _ in range(n+1)]
for i in range(len(B)-1):
    a,b=B[i],B[i+1]
    M[a].add(b)

time=1
color=["white" for _ in range(n+1)]
D=[0 for _ in range(n+1)]
DFS(A[0])
route=[]
for i in range(n+1):
    if color[i]=="black":
        route.append([D[i],i])

C=[]
for i in sorted(route):
    C.append(i[1])

k=k-D[C[0]]
print(C[k%len(C)])

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

time=0
color=["white" for _ in range(n+1)]
D=[-1 for _ in range(n+1)]
C,s=[],A[0]
point=0
while 1:
    if color[s]=="white":
        color[s]="gray"
        C.append(s)
        D[s]=time
        time +=1
        s=A[s-1]
    else:
        point=D[s]
        break

loop=C[point:]
if k>len(C):
    k -=point+1
    print(loop[k%len(loop)])
else:print(C[k-1])

Buggy python submission (verdict: Runtime Error):
def DFS(num):
    global time
    if D[num]==0:
        D[num]=time
        time +=1
    for i in M[num]:
        if color[i]=="white":
            color[num]="gray"
            color[i]="gray"
            DFS(i)
        elif color[i]=="gray":
            color[num]="black"
            color[i]="black"
            DFS(i)
        elif color[i]=="black":
            return


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

B=[]
point,cnt=0,0
while cnt<n*2:
    point=A[point]
    B.append(point)
    point -=1
    cnt +=1

M=[set() for _ in range(n+1)]
for i in range(len(B)-1):
    a,b=B[i],B[i+1]
    M[a].add(b)

time=1
color=["white" for _ in range(n+1)]
D=[0 for _ in range(n+1)]
DFS(A[0])
route=[]
for i in range(n+1):
    if color[i]=="black":
        route.append([D[i],i])

C=[]
for i in sorted(route):
    C.append(i[1])

k=k-D[C[0]]+1
print(C[k%len(C)-1])

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

time=0
color=["white" for _ in range(n+1)]
D=[-1 for _ in range(n+1)]
C,s=[],A[0]
point=0
while 1:
    if color[s]=="white":
        color[s]="gray"
        C.append(s)
        D[s]=time
        time +=1
        s=A[s-1]
    else:
        point=D[s]
        break

loop=C[point:]
if k>len(C):
    k -=point+1
    print(loop[k%len(loop)])
else:print(C[k-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
s=input()[::-1]
m=len(s)
DP=[0]
word=""

for i in s:
    word=i+word
    DP.append(int(word)%2019)

DP=Counter(DP)
ans=0
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Fixed submission:
from collections import Counter
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=2019
    DP.append(num)
    point *=10
    point %=2019

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
s=input()[::-1]
m=len(s)
DP=[0]
word=""

for i in s:
    word +=i
    DP.append(int(word[::-1])%2019)

DP=Counter(DP)
ans=0
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Fixed submission:
from collections import Counter
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=2019
    DP.append(num)
    point *=10
    point %=2019

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
s=input()
m=len(s)
DP=[""]

for i in range(m):
    DP.append(DP[-1]+s[-(i+1)])

for i in range(1,len(DP)):
    DP[i]=int(DP[i][::-1])%2019
DP.append(0)
DP=Counter(DP)

ans=0
for v,m in DP.items():
    if m>=2:ans +=m*(m-1)//2
print(ans)

Fixed submission:
from collections import Counter
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=2019
    DP.append(num)
    point *=10
    point %=2019

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
s=input()
m=len(s)
DP=[0]

for i in range(m):
    DP.append(int(s[m-(i+1):]))

for i in range(len(DP)):
    DP[i]=DP[i]%2019
DP=Counter(DP)

ans=0
for v,m in DP.items():
    if m>=2:ans +=m*(m-1)//2
print(ans)

Fixed submission:
from collections import Counter
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=2019
    DP.append(num)
    point *=10
    point %=2019

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
m=len(s)

ans=0
for i in range(m+1):
    for j in range(i+4,m+1):
        num=int(s[i:j])
        if num%2019==0:ans +=1
print(ans)

Fixed submission:
from collections import Counter
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=2019
    DP.append(num)
    point *=10
    point %=2019

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()

cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k] and j-i!=k-j:
                cnt +=1

print(cnt)

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

ans=s.count("R")*s.count("B")*s.count("G")
for i in range(n):
    for j in range(i,n):
        k=2*j-i
        if k>=n:break
        if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
            ans -=1

print(ans)
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
D=[[0]*w for _ in range(h)]

S=[list(input()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        for x,y in ((1,0),(0,1)):
            X,Y=i+x,j+y
            if 0<=X<=h and 0<=Y<=w:
                if S[i][j]=="." and S[X][Y]=="#":
                    D[X][Y]=D[i][j]+1

ans=D[h-1][w-1]
print(ans if S[0][0]!="#" else ans+1)

Fixed submission:
inf=float("inf")
h,w=map(int,input().split())
D=[[inf]*w for _ in range(h)]
D[0][0]=0

S=[list(input()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        for x,y in ((1,0),(0,1)):
            X,Y=i+x,j+y
            if 0<=X<h and 0<=Y<w:
                if S[i][j]=="." and S[X][Y]=="#":D[X][Y]=min(D[i][j]+1,D[X][Y])
                else:D[X][Y]=min(D[i][j],D[X][Y])

#import numpy as np
#print(np.array(D))
ans=D[h-1][w-1]
print(ans if S[0][0]!="#" else ans+1)

Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
D=[[0]*w for _ in range(h)]

S=[list(input()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        for x,y in ((1,0),(0,1)):
            X,Y=i+x,j+y
            if 0<=X<=h and 0<=Y<=w:
                if S[i][j]=="." and S[X][Y]=="#":
                    D[X][Y]=D[i][j]+1
                    
ans=D[h-1][w-1]
print(ans if S[0][0]!="#" else ans+1)

Fixed submission:
inf=float("inf")
h,w=map(int,input().split())
D=[[inf]*w for _ in range(h)]
D[0][0]=0

S=[list(input()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        for x,y in ((1,0),(0,1)):
            X,Y=i+x,j+y
            if 0<=X<h and 0<=Y<w:
                if S[i][j]=="." and S[X][Y]=="#":D[X][Y]=min(D[i][j]+1,D[X][Y])
                else:D[X][Y]=min(D[i][j],D[X][Y])

#import numpy as np
#print(np.array(D))
ans=D[h-1][w-1]
print(ans if S[0][0]!="#" else ans+1)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
DP=[0]

if p==2 or p==5:
    if s[0]%p==0:print(n*(n+1)//2)
    else:print(0)
else:
    num,point=0,1
    for i in s:
        num +=int(i)*point
        num %=p
        DP.append(num)
        point *=10
        point %=p
    
    ans=0
    DP=Counter(DP)
    for v,m in DP.items():
        if m>=2:ans +=m*(m-1)//2
    print(ans)

Fixed submission:
from collections import Counter
n,p=map(int,input().split())
s=input()
DP=[0]
ans=0

if p==2 or p==5:
    for i,j in enumerate(s):
        if int(j)%p==0:
            ans +=i+1
else:
    num,point=0,1
    for i in s[::-1]:
        num +=int(i)*point
        num %=p
        DP.append(num)
        point *=10
        point %=p

    DP=Counter(DP)
    for v,m in DP.items():
        if m>=2:ans +=m*(m-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
"""n<10**7の場合に使える。
https://drken1215.hatenablog.com/entry/2018/06/08/210000"""


def cmb(n,r,mod):
    if r<0 or r>n:return 0
    return g1[r]*g2[r]%mod


mod=10**9+7
n,a,b=map(int,input().split())
k=max(a,b)
g1=[1,n]
g2=[1,1]
inverse=[0,1]

for i,j in enumerate(range(n-1,n-k+1,-1)):
    i=i+2
    g1.append((g1[-1]*j)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1]%mod))

N=pow(2,n,mod)-1
print((N-cmb(n,b,mod)-cmb(n,a,mod))%mod)

Fixed submission:
def cmb(n,r,mod):
    if r<0 or r>n:return 0
    return g1[r]*g2[r]%mod


mod=10**9+7
n,a,b=map(int,input().split())
k=max(a,b)
g1=[1,n]
g2=[1,1]
inverse=[0,1]

for i,j in enumerate(range(n-1,((n-k+1)-1),-1)):
    i=i+2
    g1.append((g1[-1]*j)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1]%mod))

N=pow(2,n,mod)-1
print((N-cmb(n,b,mod)-cmb(n,a,mod))%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
P=list(map(int,input().split()))
K=[]

DP=[0]*1001
for i in P:
    if DP[i]==0:
        DP[i]=(i*(i+1)//2)/i
    K.append(DP[i])

ans=0
for i in range(n-k+1):
    ans=max(ans,sum(K[i:i+k]))
print(ans)

Fixed submission:
n,k=map(int,input().split())
P=list(map(int,input().split()))
K=[]

DP=[0]*1001
for i in P:
    if DP[i]==0:
        DP[i]=(i*(i+1)//2)/i
    K.append(DP[i])

K.append(0)
ans=sum(K[:k])
score=sum(K[:k])
for i in range(n-k+1):
    score -=K[i]
    score +=K[i+k]
    ans=max(ans,score)
print(ans)

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

DP=[float("inf")]*1001
for i in P:
    if DP[i]==float("inf"):
        DP[i]=(i*(i+1)//2)/i
    K.append(DP[i])

ans=0
for i in range(n-k+1):
    ans=max(ans,sum(K[i:i+k]))
print(ans)

Fixed submission:
n,k=map(int,input().split())
P=list(map(int,input().split()))
K=[]

DP=[0]*1001
for i in P:
    if DP[i]==0:
        DP[i]=(i*(i+1)//2)/i
    K.append(DP[i])

K.append(0)
ans=sum(K[:k])
score=sum(K[:k])
for i in range(n-k+1):
    score -=K[i]
    score +=K[i+k]
    ans=max(ans,score)
print(ans)
Buggy python submission (verdict: Runtime Error):
n=input()
k=int(input())
m=len(n)

DP=[[[0]*(k+1) for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(k+1):
            for k in range(num+1):
                if k!=0:
                    DP[i][flag or k<=num][j] +=DP[i-1][flag][j-1]
                else:
                    DP[i][flag or k<=num][j] +=DP[i-1][flag][j]
print(DP[-1][0][k]+DP[-1][1][k])

Fixed submission:
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i - 1][0][k]
        else:
            dp[i][0][k] += dp[i - 1][0][k]
        if k - 1 >= 0:
            dp[i][1][k] += 9 * dp[i - 1][1][k - 1]
            if l != 0:
                dp[i][0][k] += dp[i - 1][0][k - 1]
                dp[i][1][k] += (l - 1) * dp[i - 1][0][k - 1]

print(dp[m][0][K] + dp[m][1][K])