Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

A_sum=[0,A[0]]
B_sum=[0,B[0]]
for i in range(1,N):
    A_sum.append(A_sum[i]+A[i])
for i in range(1,M):
    B_sum.append(B_sum[i]+B[i])

b_read=0
ans=0
for i in range(N,-1,-1):
    for j in range(b_read,M+1):
        if A_sum[i]+B_sum[j]<=K:
            ans=max(ans,i+j)
            b_read=j
print(ans)


Fixed submission:
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

used=0
a_read=0
for i in range(N):
    if used+A[i]>K:
        break
    else:
        used+=A[i]
        a_read+=1

b_read=0
for i in range(M):
    if used+B[i]>K:
        break
    else:
        used+=B[i]
        b_read+=1
ans=a_read+b_read
tmp=ans

for i in range(a_read):
    if b_read==M:
        break
    used-=A[a_read-1]
    a_read-=1
    tmp-=1
    while True:
        if b_read>=M:
            break
        if used+B[b_read]<=K:
            b_read+=1
            used+=B[b_read-1]
            tmp+=1
        else:
            break
    ans=max(ans,tmp)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K=int(input())
S=input()
N=len(S)
mod=10**9+7

fact=[0]*(K+N)
fact[0]=fact[1]=1
for i in range(2,K+N):
    fact[i]=fact[i-1]*i%mod

def comb(n,r):
    ret=fact[n]*pow(fact[r],-1,mod)*pow(fact[n-r],-1,mod)%mod
    return ret

ans=0
for i in range(K+1):
    ans+=pow(26,i,mod)*pow(25,K-i,mod)*comb(K+N-1-i,N-1)
    ans%=mod

print(ans)

Fixed submission:
K=int(input())
S=input()
N=len(S)
mod=10**9+7

fact=[0]*(K+N)
fact[0]=fact[1]=1
for i in range(2,K+N):
    fact[i]=fact[i-1]*i%mod

def comb(n,r):
    ret=fact[n]*pow(fact[r],mod-2,mod)*pow(fact[n-r],mod-2,mod)%mod
    return ret

ans=0
for i in range(K+1):
    ans+=pow(26,i,mod)*pow(25,K-i,mod)*comb(K+N-1-i,N-1)
    ans%=mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
A,B,C,D=map(int,input().split())
mod=998244353

dp=[[0]*D for _ in range(C)]

dp[A-1][B-1]=1

for i in range(A-1,C):
    for j in range(B-1,D):
        if i==A-1 and j==B-1:
            continue
        if i>A-1:
            dp[i][j]+=dp[i-1][j]*(j+1)
        if j>B-1:
            dp[i][j]+=dp[i][j-1]*(i+1)
        if i>A-1 and j>B-1:
            dp[i][j]-=dp[i-1][j-1]*(j)*(i)
        dp[i][j]%=mod

print(dp[C-1][D-1]%mod)


Fixed submission:
A,B,C,D=map(int,input().split())
mod=998244353

dp=[[0]*D for _ in range(C)]

dp[A-1][B-1]=1

for i in range(A-1,C):
    for j in range(B-1,D):
        if i==A-1 and j==B-1:
            continue
        if i>A-1:
            dp[i][j]+=dp[i-1][j]*(j+1)
        if j>B-1:
            dp[i][j]+=dp[i][j-1]*(i+1)
        if i>A-1 and j>B-1:
            dp[i][j]-=dp[i-1][j-1]*(j)*(i)
        dp[i][j]%=mod

print(dp[C-1][D-1]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))

dic={}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]]=1
    else:
        dic[A[i]]+=1

if N==1:
    print(1)
    exit()

if 1 in dic:
    if dic[1]>1:
        print(0)
        exit()
    else:
        print(1)
        exit()

def make_divisors(n):
    divisors=[]
    for j in range(2, int(n**0.5)+1):
        if n%j==0:
            divisors.append(j)
            if j!=n//j:
                divisors.append(n//j)
 
    return divisors

ans=0
for i in range(N):
    if dic[A[i]]>1:
        continue
    f=False
    for j in range(2, int(A[i]**0.5)+1):
        if A[i]%j==0:
            if j in dic or A[i]//j in dic:
                f=True
                break
    if f:
        continue
    ans+=1

print(ans)

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

M=max(A)
check=[0]*(M+1)
for i in range(N):
    a=A[i]
    while a<=M:
        check[a]+=1
        a+=A[i]
ans=0
for i in range(N):
    if check[A[i]]==1:
        ans+=1

print(ans)

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

dic={}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]]=1
    else:
        dic[A[i]]+=1

if N==1:
    print(1)
    exit()

if 1 in dic:
    if dic[1]>1:
        print(0)
        exit()
    else:
        print(1)
        exit()

def make_divisors(n):
    divisors=[]
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n//i:
                divisors.append(n//i)
 
    return divisors

ans=0
for i in range(N):
    if dic[A[i]]>1:
        continue
    f=False
    div=make_divisors(A[i])
    for d in div:
        if d in dic:
            f=True
            break
    if f:
        continue
    ans+=1

print(ans)

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

M=max(A)
check=[0]*(M+1)
for i in range(N):
    a=A[i]
    while a<=M:
        check[a]+=1
        a+=A[i]
ans=0
for i in range(N):
    if check[A[i]]==1:
        ans+=1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())

pond=[]
for _ in range(H):
    pond.append(list(input()))

inf=10**7
cost=[[inf]*W for _ in range(H)]
cost[x1][y1]=0
from heapq import heapify,heappop,heappush
hq=[(0,x1,y1)]

while hq:
    t,x,y=heappop(hq)
    #北へ
    for i in range(1,K+1):
        if x-i<0 or pond[x-i][y]=="@":
            break
        if cost[x-i][y]>t+1:
            cost[x-i][y]=t+1
            heappush(hq,(t+1,x-i,y))
    #東へ
    for i in range(1,K+1):
        if y+i>W-1 or pond[x][y+i]=="@":
            break
        if cost[x][y+i]>t+1:
            cost[x][y+i]=t+1
            heappush(hq,(t+1,x,y+i))
    #南へ
    for i in range(1,K+1):
        if x+i>H-1 or pond[x+i][y]=="@":
            break
        if cost[x+i][y]>t+1:
            cost[x+i][y]=t+1
            heappush(hq,(t+1,x+i,y))
    #西へ
    for i in range(1,K+1):
        if y-i<0 or pond[x][y-i]=="@":
            break
        if cost[x][y-i]>t+1:
            cost[x][y-i]=t+1
            heappush(hq,(t+1,x,y-i))

if cost[x2][y2]==inf:
    print(-1)
    exit()  
print(cost[x2][y2])

Fixed submission:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())

pond=[]
for _ in range(H):
    pond.append(list(input()))

inf=10**7
cost=[[inf]*W for _ in range(H)]
cost[x1][y1]=0
from heapq import heapify,heappop,heappush
hq=[(0,x1,y1)]

while hq:
    t,x,y=heappop(hq)
    #北へ
    for i in range(1,K+1):
        if x-i<0 or pond[x-i][y]=="@" or cost[x-i][y]<t+1:
            break
        if cost[x-i][y]>t+1:
            cost[x-i][y]=t+1
            heappush(hq,(t+1,x-i,y))
    #東へ
    for i in range(1,K+1):
        if y+i>W-1 or pond[x][y+i]=="@" or cost[x][y+i]<t+1:
            break
        if cost[x][y+i]>t+1:
            cost[x][y+i]=t+1
            heappush(hq,(t+1,x,y+i))
    #南へ
    for i in range(1,K+1):
        if x+i>H-1 or pond[x+i][y]=="@" or cost[x+i][y]<t+1:
            break
        if cost[x+i][y]>t+1:
            cost[x+i][y]=t+1
            heappush(hq,(t+1,x+i,y))
    #西へ
    for i in range(1,K+1):
        if y-i<0 or pond[x][y-i]=="@" or cost[x][y-i]<t+1:
            break
        if cost[x][y-i]>t+1:
            cost[x][y-i]=t+1
            heappush(hq,(t+1,x,y-i))

if cost[x2][y2]==inf:
    print(-1)
    exit()  
print(cost[x2][y2])
Buggy python submission (verdict: Runtime Error):
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353

dp=[[0]*(S+1) for _ in range(N)]

dp[0][0]=2
dp[0][A[0]]=1
for i in range(N-1):
    for j in range(S+1):
        dp[i+1][j]+=dp[i][j]*2
        dp[i+1][j]%=mod
        if j+A[i+1]<=S:
            dp[i+1][j+A[i+1]]+=dp[i][j]
            dp[i+1][j+A[i+1]]%=mod

print(dp[N-1][S]%mod)

Fixed submission:
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353

dp=[[0]*(S+1) for _ in range(N)]

dp[0][0]=2
if A[0]<=S:
  dp[0][A[0]]=1
for i in range(N-1):
    for j in range(S+1):
        dp[i+1][j]+=dp[i][j]*2
        dp[i+1][j]%=mod
        if j+A[i+1]<=S:
            dp[i+1][j+A[i+1]]+=dp[i][j]
            dp[i+1][j+A[i+1]]%=mod

print(dp[N-1][S]%mod)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)
import functools
@functools.lru_cache(maxsize=None)  
def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    return tmp

for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    print(solve(N))


Fixed submission:
import sys
sys.setrecursionlimit(10**8)
T=int(input())

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    dic[N]=tmp
    return tmp

for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    dic={}
    print(solve(N))

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)
T=int(input())

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D)
    b=N%3 
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        tmp=min(tmp,solve((N+(3-b))//3)+B+D,solve((N-b)//3)+B+2*D)
    c=N%5
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        tmp=min(tmp,solve((N-c)//5)+C+D*c,,solve((N+(5-c))//5)+C+D*(5-c))
    dic[N]=tmp
    return tmp

for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    dic={}
    print(solve(N))


Fixed submission:
import sys
sys.setrecursionlimit(10**8)
T=int(input())

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    dic[N]=tmp
    return tmp

for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    dic={}
    print(solve(N))
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
from heapq import heappop,heappush 

graph=[[] for _ in range(M)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    graph[A].append(B)
    graph[B].append(A)

mark=[-1]*(N-1)

inf=float("inf")

di=[inf]*N
di[0]=0
hq=[(0,0)]

while hq:
    t,r=heappop(hq) #time room
    if t>di[r]:
        continue
    for x in graph[r]:
        t_new=t+1
        r_new=x
        if t_new<di[r_new]:
            di[r_new]=t_new
            heappush(hq,(t_new,r_new))
            if mark[r_new-1]==-1:
                mark[r_new-1]=r
            else:
                print("No")
                exit()
    
print("Yes")
for i in mark:
    print(i+1)

Fixed submission:
N,M=map(int,input().split())
from heapq import heappop,heappush 

graph=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    graph[A].append(B)
    graph[B].append(A)

mark=[-1]*(N-1)

inf=float("inf")

di=[inf]*N
di[0]=0
hq=[(0,0)]

while hq:
    t,r=heappop(hq) #time room
    if t>di[r]:
        continue
    for x in graph[r]:
        t_new=t+1
        r_new=x
        if t_new<di[r_new]:
            di[r_new]=t_new
            heappush(hq,(t_new,r_new))
            if mark[r_new-1]==-1:
                mark[r_new-1]=r
            else:
                print("No")
                exit()
    
print("Yes")
for i in mark:
    print(i+1)

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
from heapq import heappop,heappush 

graph=[[] for _ in range(M)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    graph[A].append(B)
    graph[B].append(A)

mark=[-1]*(N-1)

inf=float("inf")

di=[inf]*N
di[0]=0
hq=[(0,0)]

while hq:
    t,r=heappop(hq) #time room
    if t>di[r]:
        continue
    for x in graph[r]:
        t_new=t+1
        r_new=x
        if t_new<di[r_new]:
            di[r_new]=t_new
            heappush(hq,(t_new,r_new))
            if mark[r_new-1]==-1:
                mark[r_new-1]=r
            else:
                print("No")
    
print("Yes")
for i in mark:
    print(i+1)

Fixed submission:
N,M=map(int,input().split())
from heapq import heappop,heappush 

graph=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    graph[A].append(B)
    graph[B].append(A)

mark=[-1]*(N-1)

inf=float("inf")

di=[inf]*N
di[0]=0
hq=[(0,0)]

while hq:
    t,r=heappop(hq) #time room
    if t>di[r]:
        continue
    for x in graph[r]:
        t_new=t+1
        r_new=x
        if t_new<di[r_new]:
            di[r_new]=t_new
            heappush(hq,(t_new,r_new))
            if mark[r_new-1]==-1:
                mark[r_new-1]=r
            else:
                print("No")
                exit()
    
print("Yes")
for i in mark:
    print(i+1)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
plus=[]
minus=[]
for _ in range(N):
    S=input()
    tmp=0
    min_tmp=0 #)))の
    for i in range(len(S)):
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp<0:
            min_tmp=min(min_tmp,tmp)
    tmp=0
    max_tmp=0 #(((の
    for i in range(len(S)):
        i=len(S)-i-1
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp>0:
            max_tmp=max(max_tmp,tmp)
    if tmp>=0:
        plus.append((tmp,max_tmp,-min_tmp))
    else:
        minus.append((tmp,max_tmp,-min_tmp))

plus.sort(key=lambda x:x[2])
minus.sort(reverse=True,key=lambda x:x[1])
ans=0
for i,j,k in plus:
    if ans<k:
        print("No")
        exit()
    ans+=i
for i,j,k in minus:
    if ans<k:
        print("No")
        exit()
    ans+=i
if ans==0:
    print("Yes")
else:
    print("No")


Fixed submission:
N=int(input())
plus=[]
minus=[]
for _ in range(N):
    S=input()
    tmp=0
    min_tmp=0 #)))の
    for i in range(len(S)):
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp<0:
            min_tmp=min(min_tmp,tmp)
    tmp=0
    max_tmp=0 #(((の
    for i in range(len(S)):
        i=len(S)-i-1
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp>0:
            max_tmp=max(max_tmp,tmp)
    if tmp>=0:
        plus.append((tmp,max_tmp,-min_tmp))
    else:
        minus.append((tmp,max_tmp,-min_tmp))

plus.sort(key=lambda x:x[2])
minus.sort(reverse=True,key=lambda x:x[1])
ans=0
for i,j,k in plus:
    if ans<k:
        print("No")
        exit()
    ans+=i
for i,j,k in minus:
    if ans<k:
        print("No")
        exit()
    ans+=i
if ans==0:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
S=input()

from collections import defaultdict
d=defaultdict(int)

for i in range(len(S)):
    a=S[i:]
    b=int(a)
    d[b%2019]+=1

ans=0

for k,v in d.items():
    if k==0:
        ans+=v
    else:
        ans+=v*(v-1)//2

print(ans)

Fixed submission:
S=input()

from collections import defaultdict
d=defaultdict(int)

n=len(S)
b=0
for i in range(n):
    a=int(S[n-i-1])
    b+=a*pow(10,i,2019)
    b%=2019
    d[b]+=1

ans=0

for k,v in d.items():
    if k==0:
        ans+=v
    ans+=v*(v-1)//2

print(ans)
Buggy python submission (verdict: Runtime Error):
N,M,S=map(int,input().split())

inf = float('inf')
cost=[[]*N for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

used=[False]*2451*N
di=[inf]*2451*N
di[S]=0

while True:
    v=-1
    for i in range(2451*N):
        if not used[i] and v==-1:
            v=i
        elif not used[i] and di[i]<di[v]:
            v=i
    if v==-1:
        break
    used[v]=True
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            di[x*2451+s-a]=min((di[x*2451+s-a],di[v]+b))
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    di[v+c]=min(di[v+c],di[v]+d)

for i in range(1,N):
    m=inf
    for j in range(2451):
        m=min(m,di[i*2451+j])
    print(m)

Fixed submission:
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))

B=[(j,i) for i,j in enumerate(A)]
B.sort(reverse=True)

dp=[[0]*(N+1) for _ in range(N+1)]

c=0
for v,k in B:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

ans=0
for i in range(N):
    ans=max(ans,dp[i][N-i])

print(ans)

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

d={}

for i,j in enumerate(A):
    d[i]=j

d=sorted(d.items(),key=lambda x:x[1],reverse=True)

dp=[[0]*(N+1) for _ in range(N+1)]

c=0
for k,v in d:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

ans=0
for i in range(N):
    ans=max(ans,dp[i][N-i])

print(ans)

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

d={}

for i,j in enumerate(A):
    d[i]=j

d=sorted(d.items(),key=lambda x:x[1],reverse=True)

dp=[[0]*(N+1) for _ in range(N+1)]

c=0
for k,v in d:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

ans=0
for i in range(N):
    ans=max(ans,dp[i][N-i])

print(ans)

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

d={}

for i,j in enumerate(A):
    d[i]=j

d=sorted(d.items(),key=lambda x:x[1],reverse=True)

dp=[[0]*(N+1) for _ in range(N+1)]

c=0
for k,v in d:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

ans=0
for i in range(N):
    ans=max(ans,dp[i][N-i])

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
S=input()
Q=int(input())

X=deque(list(S))
f=1
for _ in range(Q):
    t,ff,c=input().split()
    if t=="1":
        f*=-1
    else:
        if ff=="1":
            if f==1:
                X.appendleft(c)
            else:
                X.append(c)
        else:
            if f==-1:
                X.appendleft(c)
            else:
                X.append(c)

if f==-1:
    X.reverse()

print("".join(X))

Fixed submission:
S=input()
Q=int(input())

X=[]
Y=[]
f=1
for _ in range(Q):
    A=list(input().split())
    if A[0]=="1":
        f*=-1
    if A[0]=="2":
        if A[1]=="1":
            if f==1:
                X.append(A[2])
            if f==-1:
                Y.append(A[2])
        if A[1]=="2":
            if f==-1:
                X.append(A[2])
            if f==1:
                Y.append(A[2])

x="".join(X)
x="".join(list(reversed(x)))
y="".join(Y)

a=[x,S,y]
b="".join(a)

if f==-1:
    b="".join(list(reversed(b)))

print(b)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())

f=1
for _ in range(Q):
    A=[]
    A.clear()
    A=list(input().split())
    if A[0]=="1":
        f*=-1
    if A[0]=="2":
        if A[1]=="1":
            if f==1:
                S=A[2]+S
            if f==-1:
                S=S+A[2]
        if A[1]=="2":
            if f==-1:
                S=A[2]+S
            if f==1:
                S=S+A[2]

if f==-1:
    S="".join(list(reversed(S)))

print(S)


Fixed submission:
S=input()
Q=int(input())

X=[]
Y=[]
f=1
for _ in range(Q):
    A=list(input().split())
    if A[0]=="1":
        f*=-1
    if A[0]=="2":
        if A[1]=="1":
            if f==1:
                X.append(A[2])
            if f==-1:
                Y.append(A[2])
        if A[1]=="2":
            if f==-1:
                X.append(A[2])
            if f==1:
                Y.append(A[2])

x="".join(X)
x="".join(list(reversed(x)))
y="".join(Y)

a=[x,S,y]
b="".join(a)

if f==-1:
    b="".join(list(reversed(b)))

print(b)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
N,P=map(int,input().split())
S=input()

if P==2 or P==5:
    ans=0
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)

else:
    d=defaultdict(int)
    a=0
    for i in range(N):
        a+=int(S[N-i-1])*10**i
        a%=P
        d[a]+=1
    ans=d[0]
    for v in d.values():
        ans+=v*(v-1)//2
    print(ans)
    


Fixed submission:
from collections import defaultdict
N,P=map(int,input().split())
S=input()

if P==2 or P==5:
    ans=0
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)

else:
    d=defaultdict(int)
    a=0
    for i in range(N):
        a+=int(S[N-i-1])*pow(10,i,P)
        a%=P
        d[a]+=1
    ans=d[0]
    for v in d.values():
        ans+=v*(v-1)//2
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
N,P=map(int,input().split())
S=input()

if P==2 or P==5:
    ans=0
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)

else:
    d=defaultdict(int)
    for i in range(N):
        a=int(S[N-i-1:N])%P
        d[a]+=1
    ans=d[0]
    for v in d.values():
        ans+=v*(v-1)//2
    print(ans)
    


Fixed submission:
from collections import defaultdict
N,P=map(int,input().split())
S=input()

if P==2 or P==5:
    ans=0
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)

else:
    d=defaultdict(int)
    a=0
    for i in range(N):
        a+=int(S[N-i-1])*pow(10,i,P)
        a%=P
        d[a]+=1
    ans=d[0]
    for v in d.values():
        ans+=v*(v-1)//2
    print(ans)