Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

def resolve():
    # 達成スコアを決める
    # 修行回数がK以下を達成できるスコアを二分探索
    def check(X):
        cnt = 0
        for i in range(N):
            a = X // F[i]
            if a < A[i]:  # 修行をしてスコアを最小化する
                cnt += A[i] - a
        return cnt <= K

    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()), reverse=True)

    ok = 10 ** 12 # 最大スコア a: 10**6 * x:10**6
    ng = -1
    while ok - ng > 1:
        X = (ok + ng) // 2
        if check(X):
            ok = X
        else:
            ng = X

    print(ok)


if __name__ == "__main__":
    resolve()


Fixed submission:

def resolve():
    # 達成スコアを決める
    # 修行回数がK以下を達成できるスコアを二分探索
    def check(X):
        cnt = 0
        for i in range(N):
            a = X // F[i]
            if a < A[i]:  # 修行をしてスコアを最小化する
                cnt += A[i] - a
        return cnt <= K

    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()), reverse=True)

    ok = 10 ** 12 # 最大スコア a: 10**6 * x:10**6
    ng = -1
    while ok - ng > 1:
        X = (ok + ng) // 2
        if check(X):
            ok = X
        else:
            ng = X

    print(ok)


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

def resolve():
    # 達成スコアを決める
    # 修行回数がK以下を達成できるスコアを二分探索
    def check(X):
        cnt = 0
        for i in range(N):
            a = X // F[i]
            if a < A[i]:  # 修行をしてスコアを最小化する
                cnt += A[i] - a
        return cnt <= K

    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()), reverse=True)

    ok = 10 ** 18
    ng = -1
    while ok - ng > 1:
        X = (ok + ng) // 2
        if check(X):
            ok = X
        else:
            ng = X

    print(ok)


if __name__ == "__main__":
    resolve()

Fixed submission:

def resolve():
    # 達成スコアを決める
    # 修行回数がK以下を達成できるスコアを二分探索
    def check(X):
        cnt = 0
        for i in range(N):
            a = X // F[i]
            if a < A[i]:  # 修行をしてスコアを最小化する
                cnt += A[i] - a
        return cnt <= K

    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()), reverse=True)

    ok = 10 ** 12 # 最大スコア a: 10**6 * x:10**6
    ng = -1
    while ok - ng > 1:
        X = (ok + ng) // 2
        if check(X):
            ok = X
        else:
            ng = X

    print(ok)


if __name__ == "__main__":
    resolve()
Buggy python submission (verdict: Runtime Error):
import fractions, math

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

    # divisors.sort()
    return divisors
  
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1
import random

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in xrange(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
  
A, B = map(int, input().split()) 
ans = set(make_divisors(A)) &  set(make_divisors(B))
print(sum([is_prime3(i) for i in ans])+1)



Fixed submission:
import fractions, math

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

    # divisors.sort()
    return divisors
  
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1
import random

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
  
A, B = map(int, input().split()) 
ans = set(make_divisors(A)) &  set(make_divisors(B))
print(sum([is_prime3(i) for i in ans])+1)
Buggy python submission (verdict: Time Limit Exceeded):

def resolve():
    INF = 10 ** 18
    N, M = map(int, input().split())

    Cost = [0] * M
    Box_key = [0] * M
    for i in range(M):
        a, b = map(int, input().split())
        Cost[i] = a
        C = list(map(int, input().split()))
        Box_key[i] = sum(1 << (c - 1) for c in C)

    # dp[ i ][ S ] := 最初の i 個の鍵からいくつか選んで、
    # 開いた宝箱の集合が S で表されるような場合についての、最小コスト
    dp = [[INF] * (1 << N) for _ in range(M + 1)]
    dp[0][0] = 0

    for i in range(M):
        for j in range(1 << N):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i + 1][j | Box_key[i]] = min(dp[i + 1][j | Box_key[i]], dp[i][j] + Cost[i])

    if dp[M][(1 << N) - 1] == INF:
        print(-1)
    else:
        print(dp[M][(1 << N) - 1])


if __name__ == "__main__":
    resolve()

Fixed submission:
N, M = map(int, input().split())
N2 = 2**N
INF = float("inf")
X = [INF]*N2
X[0] = 0

for i in range(M):
  a, b = map(int, input().split())
  C = list(map(int, input().split()))
  
  k = sum(1<<(c-1) for c in C)
    
  for j in range(N2):
    if X[j|k] > X[j] + a:
      X[j|k] = X[j] + a

ans = X[-1]      
if ans >= INF:
  ans = -1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np 

N, K, Q = map(int, input().split())
A = np.array([K]*N)

for i in range(Q):
  a = int(input())-1
  correct = A[a]
  A = A-1
  A[a] = correct
for ans in A:
  if ans < 1:
    print("No")
  else:
    print("Yes")
  



Fixed submission:
import numpy as np 
from collections import Counter

N, K, Q = map(int, input().split())
A = np.array([K]*N)-Q

correct = Counter([int(input())-1 for _ in range(Q)])
#correct = sorted(correct.;items(), key:lambda x: x[0])

for i in range(N):
  if i in correct.keys():
    A[i] += correct[i]
  print("No" if A[i] < 1 else "Yes")
Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())
H = np.array(input().split(), dtype=np.int32)

"""
A = [10,4,8,7,3]
left_idx = [0,0,2,2,2]
というものを作る
"""
left_idx = np.arrange(N)
left_idx[1:][A[:-1] >= A[1:]] = 0
np.maximum.accumulate(left_idx, out=left_idx)

ans = (np.arrange(N) - left_idx).max()
print(ans)

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

cnt = 0
ans = 0
for i in range(N-1):
  if H[i+1] <= H[i]:
    cnt += 1
  else:
    ans = max(ans, cnt)
    cnt = 0
ans = max(ans, cnt)    
print(ans)
Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop

N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]
for _ in range(N):
  a, b = map(int, input().split())
  AB[a].append(b) # 消化日数に対しての価値
  
#heapq.heapify(a)  # listを優先度付きキューに

q = []
ans = 0
for B in AB:
  for b in B: # 日数：価値
    heappush(q, -b) # 最大値のため、マイナスをかける
  if q:
    ans -= heappop(q) # マイナスの値を戻す
print(ans)    
    


Fixed submission:
from heapq import heappush, heappushpop

N, M = map(int, input().split())
tasks = [[] for _ in range(M+1)]
for _ in range(N):
  a, b = map(int, input().split())
  if a <= M:
    tasks[M-a].append(b)

q = []
for day in range(M+1):
  for v in tasks[day]:
    if len(q) < day+1:
      heappush(q, v)
    else:
      heappushpop(q,v)
print(sum(q))
Buggy python submission (verdict: Time Limit Exceeded):
L, R = map(int, input().split())
R = min(R, L+4038)
ans = 2018
for i in range(L, R):
  for j in range(i+1, R+1):
    x = i*j%2019
    ans = min(ans, x)
print(ans)    

Fixed submission:
L, R = map(int, input().split())

if R-L > 2020:
  print(0)
  exit()

R = min(R, L+4038)
ans = 2018
for i in range(L, R):
  for j in range(i+1, R+1):
    x = i*j%2019
    ans = min(ans, x)
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(1, n-1):
  pA = sorted(A[i-1:i+2])  
  print(pb)
  if pA[1] == A[i]:
    count += 1
print(count)    

Fixed submission:
n = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(1, n-1):
  pA = sorted(A[i-1:i+2])  
  if pA[1] == A[i]:
    count += 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
S = input().replace("BC", "D")
in_ABC = S.count("AD")
count = 0
while in_ABC != 0:
  S = S.replace("AD", "DA", 1)
  count += 1
  in_ABC = S.count("AD")
print(count)  

Fixed submission:
S = input().replace("BC", "D")
acc = 0
ans = 0
for s in S:
  if s == "B" or s == "C":
    acc = 0
    continue
  if s == "A":
    acc += 1
  if s == "D":
    ans += acc
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
in_ABC = S.count("ABC")
count = 0
while in_ABC != 0:
  S = S.replace("ABC", "BCA", 1)
  count += 1
  in_ABC = S.count("ABC")
print(count)  

Fixed submission:
S = input().replace("BC", "D")
acc = 0
ans = 0
for s in S:
  if s == "B" or s == "C":
    acc = 0
    continue
  if s == "A":
    acc += 1
  if s == "D":
    ans += acc
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
count = 0
while "ABC" in S:
  S = S.replace("ABC", "BCA", 1)
  count += 1
print(count)  

Fixed submission:
S = input().replace("BC", "D")
acc = 0
ans = 0
for s in S:
  if s == "B" or s == "C":
    acc = 0
    continue
  if s == "A":
    acc += 1
  if s == "D":
    ans += acc
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, play = map(int, input().split())
card = list(map(int, input().split()))
card.sort()
for i in range(play):
  n, c = map(int, input().split())
  for i in range(n):
    step = 0
    if card[step] < c:
      card[step] = c
      card.sort()
    else:
      step += 1
print(sum(card))
        

Fixed submission:
n, play = map(int, input().split())
card = list(map(int, input().split()))
card.sort()
# カードのリスト化を全操作済み
bc = [list(map(int, input().split())) for _ in range(play)]
bc.sort(key=lambda x:x[1], reverse=True)

arr = []
sum_b = 0
for b, c in bc:
  arr += [c]*b
  sum_b += b
  if sum_b >= n:
    break
# 最初のカードを連結
arr += card    
arr.sort(reverse=True)
# カード枚数分合計
print(sum(arr[:n]))
Buggy python submission (verdict: Runtime Error):
S = int(input())
yymm = S//100
mmyy = S%100
yymm = (1<=y<=12)
mmyy = (1<=x<=12)

ans = "NA"
if yymm and mmyy:
    answer = 'AMBIGUOUS'
elif yymm and not(mmyy):
    answer = 'YYMM'
elif mmyy and not(yymm):
    answer = 'MMYY'

print(ans)  

Fixed submission:
import sys
input = sys.stdin.readline

S = input().rstrip()
l = [0]*2
y = S[:2]
m = S[2:]
l[0] = 0 if "01" <= y <= "12" else 1
l[1] = 1 if "01" <= m <= "12" else 0

if l[0] == 0 and l[1] == 1:
  print("AMBIGUOUS")
elif l[0] == 1 and l[1] == 1:
  print("YYMM")
elif l[0] == 0 and l[1] == 0:
  print("MMYY")  
else:
  print("NA")
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
 
n, k = map(int, input().split())
prob = 0
for i in range(1, n+1):
  count = 0
  total = i
  while total < k:
    total *= 2
    count += 1
  prob += 1/2**p
print(prob/n)


Fixed submission:
import sys
input = sys.stdin.readline
 
n, k = map(int, input().split())
prob = 0
for i in range(1, n+1):
  count = 0
  total = i
  while total < k:
    total *= 2
    count += 1
  prob += 1/2**count
print(prob/n)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

s_len, n = map(int, input().split())
s = input().rstrip()
for i in range(n):
  count = 0
  a, b = map(int, input().split())
  s_slice = s[a-1:b]  
  for i in range(len(s_slice)-1):
    if s_slice[i:2+i]=="AC":
      count += 1
  print(count)
  


Fixed submission:
import sys
input = sys.stdin.readline

import bisect
left = bisect.bisect_left
right = bisect.bisect_right 

n, q = list(map(int, input().split()))
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
a = [i for i in range(n-1) if s[i:i+2]=="AC"]

for i in range(q):
  left_index = left(a, lr[i][0]-1)      
  right_index = right(a, lr[i][1]-2)  
  print(right_index - left_index)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

s_len, n = map(int, input().split())
s = input().rstrip()
for i in range(n):
  a, b = map(int, input().split())
  s_slice = s[a-1:b]  
  print(sum([s_slice[i:2+i]=="AC" for i in range(len(s_slice)-1)]))
  


Fixed submission:
import sys
input = sys.stdin.readline

import bisect
left = bisect.bisect_left
right = bisect.bisect_right 

n, q = list(map(int, input().split()))
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
a = [i for i in range(n-1) if s[i:i+2]=="AC"]

for i in range(q):
  left_index = left(a, lr[i][0]-1)      
  right_index = right(a, lr[i][1]-2)  
  print(right_index - left_index)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

s_len, n = map(int, input().split())
s = input().rstrip()
for i in range(n):
  a, b = map(int, input().split())
  s_slice = s[a-1:b]  
  count = sum([s_slice[i:2+i]=="AC" for i in range(len(s_slice)-1)])
  print(count)
  


Fixed submission:
import sys
input = sys.stdin.readline

import bisect
left = bisect.bisect_left
right = bisect.bisect_right 

n, q = list(map(int, input().split()))
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
a = [i for i in range(n-1) if s[i:i+2]=="AC"]

for i in range(q):
  left_index = left(a, lr[i][0]-1)      
  right_index = right(a, lr[i][1]-2)  
  print(right_index - left_index)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()

ans = 0
while S.count("01") or S.count("10"):
  if S.count("01"):
    ans += S.count("01")
    S = S.replace("01", "")
  if S.count("10"):
    ans += S.count("10")
    S = S.replace("10", "")
    
print(ans*2)    

Fixed submission:
import sys
input = sys.stdin.readline

S = input().rstrip()
stack = []
count = 0
for s in S:
  if not stack:
    stack.append(s)
  elif s != stack[-1]:
    stack.pop()
    count += 2
  else:
    stack.append(s)
print(count)
Buggy python submission (verdict: Runtime Error):
N, food = map(int, input().split())
S = set(range(1,food+1))
for i in range(N):
  k, *a = ma(int,input().split())
  S &= set(a)
print(len(S))

Fixed submission:
n,m=map(int,input().split())
S=set(range(1,m+1))
for i in range(n):
    K,*A=map(int,input().split())
    S&=set(A)
print(len(S))

Buggy python submission (verdict: Runtime Error):
N, food = input().split()
S = set(range(1,food+1))
for i in range(N):
  k, *a = input().split()
  S &= set(a)
print(len(S))

Fixed submission:
n,m=map(int,input().split())
S=set(range(1,m+1))
for i in range(n):
    K,*A=map(int,input().split())
    S&=set(A)
print(len(S))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

import numpy as np

N = int(input())

dp = np.zeros((N+1, 3), dtype=int)
arr = np.zeros((N, 3), dtype=int)
for i in range(N):
  arr[i] = list(map(int, input().split()))

# dp roop
for i in range(N):
  for j in range(3):
    for k in range(3):
      if j==k:
        continue
      dp[i+1, k] = np.maximum(dp[i+1, k], dp[i, j] + arr[i, k])
print(max(dp[N]))

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
dp = [[0]*3 for i in range(N+1)]
arr = [list(map(int, input().split())) for i in range(N)]

# dp roop
for i in range(N):
  for j in range(3):
    for k in range(3):
      if j==k:
        continue
      dp[i+1][k] = max(dp[i+1][k], dp[i][j] + arr[i][k])
print(max(dp[N]))

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

import numpy as np

N = int(input())

dp = np.zeros((N+1, 3), dtype=int)
arr = np.zeros((N, 3), dtype=int)
for i in range(N):
  arr[i] = list(map(int, input().split()))

# dp roop
for i in range(N):
  for j in range(3):
    for k in range(3):
      if j==k:
        continue
      dp[i+1, k] = np.maximum(dp[i+1, k], dp[i, j] + arr[i, k])
print(max(dp[N]))import sys
input = sys.stdin.readline

import numpy as np

N = int(input())

dp = np.zeros((N+1, 3), dtype=int)
arr = np.zeros((N, 3), dtype=int)
for i in range(N):
  arr[i] = list(map(int, input().split()))

# dp roop
for i in range(N):
  for j in range(3):
    for k in range(3):
      if j==k:
        continue
      dp[i+1, k] = np.maximum(dp[i+1, k], dp[i, j] + arr[i, k])
print(max(dp[N]))

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
dp = [[0]*3 for i in range(N+1)]
arr = [list(map(int, input().split())) for i in range(N)]

# dp roop
for i in range(N):
  for j in range(3):
    for k in range(3):
      if j==k:
        continue
      dp[i+1][k] = max(dp[i+1][k], dp[i][j] + arr[i][k])
print(max(dp[N]))
Buggy python submission (verdict: Time Limit Exceeded):

def resolve():
    S = input()
    T = input()

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

    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])

    ans = ""

    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            ans = S[i - 1] + ans
            i -= 1
            j -= 1
    print(ans)


if __name__ == "__main__":
    resolve()


Fixed submission:

def resolve():
    S = input()
    T = input()

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

    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])

    ans = ""

    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            ans = S[i - 1] + ans
            i -= 1
            j -= 1
    print(ans)


if __name__ == "__main__":
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):

def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    dp = [[0] * (N+1) for _ in range(N+1)]
    # 左側をとる: 区間 [i+1,j)[i+1,j) に遷移
    # 右側をとる: 区間 [i,j−1)[i,j−1) に遷移
    for L in range(1, N + 1):
        i = 0
        while i + L <= N:
            j = i + L
            # 先手番
            if (N - L) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
            # 後手番
            else:
                dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])
            i += 1

    print(dp[0][N])


if __name__ == "__main__":
    resolve()

Fixed submission:

def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    dp = [[0] * (N+1) for _ in range(N+1)]
    # 左側をとる: 区間 [i+1,j)[i+1,j) に遷移
    # 右側をとる: 区間 [i,j−1)[i,j−1) に遷移
    for L in range(1, N + 1):
        i = 0
        while i + L <= N:
            j = i + L
            # 先手番
            if (N - L) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
            # 後手番
            else:
                dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])
            i += 1

    print(dp[0][N])


if __name__ == "__main__":
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    cum_A = [0]*(N+1)
    for i in range(N):
        cum_A[i+1] = cum_A[i] + A[i]

    dp = [[1<<60]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0

    for l in range(2, N+1):
        # right = left + len - 1でrightが[0, N - 1]のように
        for left in range(N-l+1):
            right = left + l-1
            #if right>= N: continue
            cost = cum_A[right+1] - cum_A[left]
            for k in range(left, right):
                tmp = dp[left][k] + dp[k+1][right] + cost
                dp[left][right] = min(dp[left][right], tmp)

    return print(dp[0][N-1])


if __name__ == "__main__":
    resolve()

Fixed submission:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    cum_A = [0]*(N+1)
    for i in range(N):
        cum_A[i+1] = cum_A[i] + A[i]

    dp = [[1<<60]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0

    for l in range(2, N+1):
        # right = left + len - 1でrightが[0, N - 1]のように
        for left in range(N-l+1):
            right = left + l-1
            #if right>= N: continue
            cost = cum_A[right+1] - cum_A[left]
            for k in range(left, right):
                tmp = dp[left][k] + dp[k+1][right] + cost
                dp[left][right] = min(dp[left][right], tmp)

    return print(dp[0][N-1])

if __name__ == "__main__":
    resolve()
Buggy python submission (verdict: Runtime Error):

def resolve():
    from functools import cmp_to_key
    # aをbの上に配置するとき、W≤sa と W+wa≤sbを満たす必要: W≤min(sa,sb−wa)
    # bをaの上に配置するとき、同様に: W≤min(sb,sa−wb)
    def cmp(a, b):
        va = min(a[1], b[1] - a[0])
        vb = min(b[1], a[1] - b[0])
        if (va == vb): return 0
        return -1 if (va > vb) else 1

    N = int(input())
    # Block[w][s][v]
    Block = [list(map(int, input().split())) for _ in range(N)]
    Block.sort(key=cmp_to_key(cmp))

    max_W = 10**4+1
    dp = [[0]*(max_W+5) for _ in range(N+1)]
    # dp[i][tot] := i番目までを使って、重さの総和がtotである場合の価値の総和の最大値
    for i in range(N):
        for tot in range(max_W+1):
            dp[i+1][tot] = max(dp[i+1][tot], dp[i][tot])
            if tot <= Block[i][1]:
                dp[i + 1][tot+Block[i][0]] = max(dp[i + 1][tot+Block[i][0]], dp[i][tot] + Block[i][2])

    print(max(dp[N]))

if __name__ == "__main__":
    resolve()

Fixed submission:

def resolve():
    from functools import cmp_to_key
    # aをbの上に配置するとき、W≤sa と W+wa≤sbを満たす必要: W≤min(sa,sb−wa)
    # bをaの上に配置するとき、同様に: W≤min(sb,sa−wb)
    def cmp(a, b):
        va = min(a[1], b[1] - a[0])
        vb = min(b[1], a[1] - b[0])
        if (va == vb): return 0
        return -1 if (va > vb) else 1

    N = int(input())
    # Block[w][s][v]
    Block = [list(map(int, input().split())) for _ in range(N)]
    Block.sort(key=cmp_to_key(cmp))

    max_W = 2*(10**4+1)
    dp = [[0]*(max_W+5) for _ in range(N+1)]
    # dp[i][tot] := i番目までを使って、重さの総和がtotである場合の価値の総和の最大値
    for i in range(N):
        w, s, v = Block[i]
        for tot in range(max_W):
            dp[i+1][tot] = max(dp[i+1][tot], dp[i][tot])
            if tot <= s:
                dp[i + 1][tot+w] = max(dp[i + 1][tot+w], dp[i][tot] + v)

    print(max(dp[N]))


if __name__ == "__main__":
    resolve()