Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
ans=[]
for i in range(q):
	x,y=map(int,input().split())
	ans.append(s[x-1:y].count('AC'))
for i in ans:
	print(i)

Fixed submission:
n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
	t[i+1]=t[i]+(1 if s[i:i+2]=='AC' else 0)
for i in range(q):
	l,r=map(int,input().split())
	print(t[r-1]-t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
ans=[]
for i in range(q):
	x,y=map(int,input().split())
	ans.append(s[x-1:y].count('AC'))
print('\n'.join(list(map(str,ans))))
	

Fixed submission:
n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
	t[i+1]=t[i]+(1 if s[i:i+2]=='AC' else 0)
for i in range(q):
	l,r=map(int,input().split())
	print(t[r-1]-t[l-1])
Buggy python submission (verdict: Runtime Error):
s = input();
l = len(s)
zero=0,one=0
for i in s:
	if i=='0': zero+=1
	else one+=1
print(min(zero, one))

Fixed submission:
s=input();
l=len(s)
zero,one=0,0
for i in s:
	if i=='0': zero+=1
	else: one+=1
print(min(zero, one)*2)

Buggy python submission (verdict: Time Limit Exceeded):
s = input();
l = len(s)
while ('01' in s) or ('10' in s): 
	s=s.replace('01', '').replace('10', '')
print(l - len(s))

Fixed submission:
s=input();
l=len(s)
zero,one=0,0
for i in s:
	if i=='0': zero+=1
	else: one+=1
print(min(zero, one)*2)
Buggy python submission (verdict: Runtime Error):
import random

n = int(input())
m = [int(i) for i in input().split()]

while True:
	a = m.pop(random.randrange(n)); n -= 1
	b = m.pop(random.randrange(n)); n -= 1
	a -= b
	m.extend([a, b]); n += 2
	print(m)
	for i in m:
		if i <= 0:
			m.remove(i); n -= 1
	if len(m) == 1: print(m[0]); exit()

Fixed submission:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
	ans = gcd(ans, a[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
N, X = map(int, input().split())
l = list(map(int, input().split()))
g = X - l[0]
for i in l[1:N]:
	if i == X: continue
	g = gcd(g, abs(X-i))

print(abs(g))

Fixed submission:
N, X = map(int, input().split())
l = list(map(int, input().split()))
g = X - l[0]
from fractions import gcd
for i in l[1:N]:
	if i == X: continue
	g = gcd(g, abs(X-i))

print(abs(g))

Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
l = list(map(int, input().split()))
g = X - l[0]
from math import gcd
for i in l[1:N]:
	if i == X: continue
	g = gcd(g, abs(X-i))

print(abs(g))

Fixed submission:
N, X = map(int, input().split())
l = list(map(int, input().split()))
g = X - l[0]
from fractions import gcd
for i in l[1:N]:
	if i == X: continue
	g = gcd(g, abs(X-i))

print(abs(g))

Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
l = list(map(int, input().split()))
g = X - l[0]
from math import gcd
for i in l[1:N]:
	if i == X: continue
	g = gcd(g, abs(X-i))

print(abs(g))

Fixed submission:
N, X = map(int, input().split())
l = list(map(int, input().split()))
g = X - l[0]
from fractions import gcd
for i in l[1:N]:
	if i == X: continue
	g = gcd(g, abs(X-i))

print(abs(g))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input();ew=[]
ans=[]
for i in s:
	if i=='W': ew.append(0)
	else: ew.append(1)

for i in range(n):
	t=[]
	t.extend([1]*i)
	t.append(ew[i])
	t.extend([0]*(n-i-1))
	a=list(map(lambda x,y: abs(x-y), ew,t))
	ans.append(sum(a))
print(min(ans))

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

num_w=0
num_e=s[1:].count('E')
ans=num_e
for i in range(n):
	if i == 0:
		continue
	if s[i]=='E':
		num_e-=1
	if s[i-1]=='W':
		num_w+=1
	ans=min(ans, num_w+num_e)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()
ans=[0]*n
for i in range(n):
	for j in range(i):
		if s[j]=='W': ans[i]+=1
	for k in range(i,n):
		if s[k]=='E': ans[i]+=1
print(min(ans))

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

num_w=0
num_e=s[1:].count('E')
ans=num_e
for i in range(n):
	if i == 0:
		continue
	if s[i]=='E':
		num_e-=1
	if s[i-1]=='W':
		num_w+=1
	ans=min(ans, num_w+num_e)
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
t_now = 0
x_now = 0
y_now = 0
flag = True
for _ in range(n):
    t, x, y = map(int, input().split())
    if t < abs(x - x_now) or t < abs(y - y_now) or (y == y_now and x == x_now):
        print('No')
        flag = False
        break
    t_now = t
    x_now = x
    y_now = y
if flag:
    print('Yes')


Fixed submission:
a,b = map(int, input().split())
if (a*b) % 2 == 0:
	print('Even')
else:
	print('Odd')
Buggy python submission (verdict: Time Limit Exceeded):
n = input()
A = list(map(int, input().split()))
i = 0
while True:
    odd = [a for a in A if a % 2]
    if len(odd) > 0:
        break
    A = map(lambda x: x/2, A)
    i+=1
print(i)


Fixed submission:
from time import sleep
n = input()
A = list(map(int, input().split()))
i = 0
while True:
    if len([a for a in A if a % 2]) > 0:
        break
    A = list(map(lambda x: x/2, A))
    i+=1
print(i)

Buggy python submission (verdict: Runtime Error):
n = input()
a = list(map(int, input().split())
while True:
	sum(a)
	if sum % 2:
		break
	for num in a:
		num = num / 2
	i += 1
print(i)

Fixed submission:
from time import sleep
n = input()
A = list(map(int, input().split()))
i = 0
while True:
    if len([a for a in A if a % 2]) > 0:
        break
    A = list(map(lambda x: x/2, A))
    i+=1
print(i)

Buggy python submission (verdict: Runtime Error):
n = input()
a = list(map(int, input().split())
while True:
	sum += [num for num in a]
	if sum % 2:
		break
	for num in a:
		num /= 2
	i += 1
print(i)

Fixed submission:
from time import sleep
n = input()
A = list(map(int, input().split()))
i = 0
while True:
    if len([a for a in A if a % 2]) > 0:
        break
    A = list(map(lambda x: x/2, A))
    i+=1
print(i)

Buggy python submission (verdict: Runtime Error):
n = input()
a = list(map(int, input().split())
while True:
	sum += a[num for num in len(a)]
	if sum % 2:
		break
	for num in a:
		num /= 2
	i += 1
print(i)

Fixed submission:
from time import sleep
n = input()
A = list(map(int, input().split()))
i = 0
while True:
    if len([a for a in A if a % 2]) > 0:
        break
    A = list(map(lambda x: x/2, A))
    i+=1
print(i)
Buggy python submission (verdict: Time Limit Exceeded):
k,s = map(int,input().split());a=0
for x in range(k+1):
	for y in range(k+1):
		for z in range(k+1):
			if x+y+z == s: a+=1
print(a)

Fixed submission:
k,s = map(int,input().split())
c=0
for i in range(k+1):
	for j in range(k+1):
		if 0 <= s-i-j <= k:
			c+=1
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
n = input()
t_list = ['dream', 'dreamer', 'erase', 'eraser']
i = 0
while len(n) != 0:
    for t in t_list:
        if n[-len(t):] == t:
            n = n[:-len(t)]
            break
if not n:
    print('YES')
else:
    print('NO')


Fixed submission:
s = input().replace("eraser","").replace("erase","").replace("dreamer","").replace("dream","")
if s:
    print("NO")
else:
    print("YES")
Buggy python submission (verdict: Runtime Error):
s=[input().replace('a','0').replace('b','1').replace('c','2') for _ in '111'];
while True:
	t=int(s[t][0])
	s[t]=s[t][1:]
	if len(s[t])==0:
		print('ABC'[t])
		exit()

Fixed submission:
s=[input().replace('a','0').replace('b','1').replace('c','2') for _ in '111'];t=0
while True:
	if len(s[t])==0:
		print('ABC'[t])
		exit()
	a=int(s[t][0])
	s[t]=s[t][1:]
	t=a
Buggy python submission (verdict: Runtime Error):
n, x = map(int, input().split())
l = list(map(int, input().split()))

d = 0
cnt = 0
if l[0] == 0:
    print(0)
else:
    cnt += 1
    for i in range(1,n):
        d += l[i - 1]
        if d <= x:
            cnt += 1
    print(cnt)


Fixed submission:
x, a = map(int, input().split())
 
if x < a:
  print(0)
else:
  print(10)

Buggy python submission (verdict: Runtime Error):
x, a = map(int, input())
 
if x < a:
  print(0)
else:
  print(10)

Fixed submission:
x, a = map(int, input().split())
 
if x < a:
  print(0)
else:
  print(10)

Buggy python submission (verdict: Runtime Error):
x a = map(int, input())

if x < a:
  print(0)
else:
  print(10)

Fixed submission:
x, a = map(int, input().split())
 
if x < a:
  print(0)
else:
  print(10)
Buggy python submission (verdict: Runtime Error):
N = int(input())

n1 = int(N / 100 % 100)
n2 = N % 100

if n1 > 12 and n2 > 0:
    print("YYMM")
elif n2 > 12 and n1 > 0:
    print("MMYY")
elif n1 < 13 and n2 < 13:
    print("AMBIGUOUS")
else:
    print("NA")


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

for i in range(len(S)):
    if i == k - 1:
        print(S[i].swapcase(), end="")
    else:
        print(S[i], end="")
print()

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

n1 = int(N / 100 % 100)
n2 = N % 100

if n1 == 0 or n2 == 0:
    print("NA")
elif n1 > 12:
    print("YYMM")
elif n2 > 12:
    print("MMYY")
elif n1 < 12:
    print("AMBIGUOUS")


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

for i in range(len(S)):
    if i == k - 1:
        print(S[i].swapcase(), end="")
    else:
        print(S[i], end="")
print()
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = lisr(input())
cnt = 0
for i in range(1, N-1):
    if S[i-1] == "#" and S[i] == ".":
        s[i] = "."
         cnt += 1
print(cnt)

Fixed submission:
A, B, C = map(int, input().split())
if A > B:
    tmp = A
    A =  B
    B = tmp 

if C >= A and C <= B:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = lisr(input())
cnt = 0
for i in range(1, N-1):
    if S[i-1] == "#":
        for j in range(i, N-1):
             if S[j] ==  ".":
                 cnt += 1
print(cnt)

Fixed submission:
A, B, C = map(int, input().split())
if A > B:
    tmp = A
    A =  B
    B = tmp 

if C >= A and C <= B:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = lisr(input())
cnt = 0
for i in range(1, N):
    if S[i-1] == "#" and S[i] == ".":
        s[i] = "#"
         cnt += 1
print(cnt)

Fixed submission:
A, B, C = map(int, input().split())
if A > B:
    tmp = A
    A =  B
    B = tmp 

if C >= A and C <= B:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = lisr(input())
cnt = 0
for i in range(1, N):
    if S[i-1] == "#" and S[i] == ".":
        s[i-1] = "."
         cnt += 1
print(cnt)

Fixed submission:
A, B, C = map(int, input().split())
if A > B:
    tmp = A
    A =  B
    B = tmp 

if C >= A and C <= B:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = lisr(input())
cnt = 0
for i in range(1, N):
    if S[i-1] == "#" :
        s[i] = "."
         cnt += 1
print(cnt)

Fixed submission:
A, B, C = map(int, input().split())
if A > B:
    tmp = A
    A =  B
    B = tmp 

if C >= A and C <= B:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = lisr(input())
cnt = 0
for i in range(1, N):
     if S[i-1] == "#":
         if S[i] == ".":
             S[i] = "#"
             cnt += 1
print(cnt)

Fixed submission:
A, B, C = map(int, input().split())
if A > B:
    tmp = A
    A =  B
    B = tmp 

if C >= A and C <= B:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = lisr(input())
cnt = 0
for i in range(1, N):
    if S[i-1] == "#" and S[i] == ".":
        cnt += 1
print(cnt)

Fixed submission:
A, B, C = map(int, input().split())
if A > B:
    tmp = A
    A =  B
    B = tmp 

if C >= A and C <= B:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = list(input())
K = int(input())

for i in S:
    if S[K] == i:
        print(i, end="")
    else:
        print("*", end="")
print()

Fixed submission:
N = int(input())
S = list(input())
K = int(input())
 
for i in S:
    if S[K-1] == i:
        print(i, end="")
    else:
        print("*", end="")
print()
Buggy python submission (verdict: Runtime Error):
a, b = input().split('')

if a == "9" or b == "9":
    print("Yes")
else:
    print("No")


Fixed submission:
l = list(input())
for i in l:
    if i == "9":
        print("Yes")
        break
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split(''))

if a == 9 or b == 9:
    print("Yes")
else:
    print("No")


Fixed submission:
l = list(input())
for i in l:
    if i == "9":
        print("Yes")
        break
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
x, a, b = map(int, input().split())

if abs(x - a) < abs(x - b):
    print(A)
else:
    print(B)


Fixed submission:
x, a, b = map(int, input().split())

if abs(x - a) < abs(x - b):
    print("A")
else:
    print("B")
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())
        print("No")

if A % 3 == 0 or B % 3 == 0 or (A + B) % 3 == 0:
    print("Possible")
else:
    print("Impossible")


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

if A % 3 == 0 or B % 3 == 0 or (A + B) % 3 == 0:
    print("Possible")
else:
    print("Impossible")

Buggy python submission (verdict: Runtime Error):
A, B = maP(int, input().split())

if A % 3 == 0 or B % 3 == 0 or (A + B) % 3 == 0:
    print("Possible")
else:
    print("Impossible")


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

if A % 3 == 0 or B % 3 == 0 or (A + B) % 3 == 0:
    print("Possible")
else:
    print("Impossible")
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

print(["error", A + B] [A + B < 10])


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

if (r * 100 + g * 10 + b) % 4 == 0:
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

print(["error", A + B] A + B < 10)


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

print(["error", A + B] [A + B < 10])
Buggy python submission (verdict: Runtime Error):
L = [0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0]

x, y = map(int, input().split())

if L(x) == L(y):
    print("Yes")
else:
    print("No")


Fixed submission:
L = [0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0]

x, y = map(int, input().split())

print(["No", "Yes"] [L[x] == L[y]])

Buggy python submission (verdict: Runtime Error):
L = [0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0]

x, y = map(int, intput().split())

print(["Yes", "No"] [L(x) == l(y)])


Fixed submission:
L = [0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0]

x, y = map(int, input().split())

print(["No", "Yes"] [L[x] == L[y]])

Buggy python submission (verdict: Runtime Error):
L = [0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0]

x, y = map(int, intput().split())

print(["Yes", "No"] [if L(x) == l(y)]


Fixed submission:
L = [0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0]

x, y = map(int, input().split())

print(["No", "Yes"] [L[x] == L[y]])
Buggy python submission (verdict: Runtime Error):
print(eval(input())


Fixed submission:
ans = eval(input())
print(ans)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
tmp = map(int, input().split())
if tmp[0] < tmp[1]:
  print(0)
else:
  print(10)

Fixed submission:
# -*- coding: utf-8 -*-
tmp = list(map(int, input().split()))
if tmp[0] < tmp[1]:
  print(0)
else:
  print(10)

Buggy python submission (verdict: Runtime Error):
tmp = map(int, input().split(' '))
if tmp[0] < tmp[1]:
  print(0)
else:
  print(10)

Fixed submission:
# -*- coding: utf-8 -*-
tmp = list(map(int, input().split()))
if tmp[0] < tmp[1]:
  print(0)
else:
  print(10)
Buggy python submission (verdict: Runtime Error):
info = map(int, input().split(' '))
N, X = info[0], info[1]
info = map(int, input().split(' '))
len = 0

count = 1

for for1 in info:
  len += for1
  if len <= X:
    count += 1
  else:
    break

print(count)

Fixed submission:
# -*- coding: utf-8 -*-
info = list(map(int, input().split(' ')))
N, X = info[0], info[1]
info = list(map(int, input().split(' ')))
len = 0

count = 1

for for1 in info:
  len += for1
  if len <= X:
    count += 1
  else:
    break

print(count)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

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


Fixed submission:
# coding: utf-8

n = int(input())    # 2 <= n <= 10^5
h = list(map(int, input().rstrip().split()))
dp = [0]
for i in range(1, n):
    dp.append(min( \
        dp[i - 1] + abs(h[i - 1] - h[i]), \
        float('inf') if i < 2 else dp[i - 2] + abs(h[i - 2] - h[i])))
print(dp[- 1])

Buggy python submission (verdict: Runtime Error):
# coding: utf-8

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

dp = [0] * 100010
for i in range(1, n):
    c = float('inf')
    for j, d in enumerate(dp[:i]):
        c_ = d + abs(h[i - j] - h[i])
        if c_ < c:
            c = c_
    dp[i] = c
print(dp[i])


Fixed submission:
# coding: utf-8

n = int(input())    # 2 <= n <= 10^5
h = list(map(int, input().rstrip().split()))
dp = [0]
for i in range(1, n):
    dp.append(min( \
        dp[i - 1] + abs(h[i - 1] - h[i]), \
        float('inf') if i < 2 else dp[i - 2] + abs(h[i - 2] - h[i])))
print(dp[- 1])

Buggy python submission (verdict: Runtime Error):
# coding: utf-8

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

dp = [0] * 100010
for i in range(1, n):
    c = float('inf')
    for j in range(1, k + 1):
        if j > i:
            break
        else:
            c_ = dp[i - j] + abs(h[i - j] - h[i])
            if c_ < c:
                c = c_
    dp[i] = c
print(dp[i])


Fixed submission:
# coding: utf-8

n = int(input())    # 2 <= n <= 10^5
h = list(map(int, input().rstrip().split()))
dp = [0]
for i in range(1, n):
    dp.append(min( \
        dp[i - 1] + abs(h[i - 1] - h[i]), \
        float('inf') if i < 2 else dp[i - 2] + abs(h[i - 2] - h[i])))
print(dp[- 1])

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

n = int(input())    # 2 <= n <= 10^5
h = list(map(int, input().rstrip().split()))
cost = lambda f, t: abs(h[t] - h[f])
# dp[j][i]
#   j 回目のジャンプでiにいるために必要な最低コストを格納
dp = [[float('inf')] * n for _ in range(n)]
for i in dp:
    i[0] = 0
for j in range(1, n):
    for i in range(1, n):
        dp[j][i] = min( \
            dp[j - 1][i], \
            float('inf') if i < 1 else \
                dp[j - 1][i - 1] + abs(h[i - 1] - h[i]), \
            float('inf') if i < 2 else \
                dp[j - 1][i - 2] + abs(h[i - 2] - h[i]))
print(dp[n - 1][n - 1])


Fixed submission:
# coding: utf-8

n = int(input())    # 2 <= n <= 10^5
h = list(map(int, input().rstrip().split()))
dp = [0]
for i in range(1, n):
    dp.append(min( \
        dp[i - 1] + abs(h[i - 1] - h[i]), \
        float('inf') if i < 2 else dp[i - 2] + abs(h[i - 2] - h[i])))
print(dp[- 1])
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, p):
    dp = [[ 0.0 ] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1.0
    for i in range(n):
        for j in range(n + 1):
            dp[i + 1][j] = dp[i][j - 1] * p[i] + \
                dp[i][j] * (1 - p[i])
    return(sum(dp[n][n // 2 + 1:]))

n = int(input()) # n: odd, 1 <= n <= 2999
p = list(map(float, input().split())) # 0 < pi[i] < 1
print(f(n, p))


Fixed submission:
# coding: utf-8
import sys
input = sys.stdin.readline

def f2(n, p):
    dp = [ 0.0 ] * (n + 1)
    dp[0] = 1.0
    # pprint.pprint(dp, width = 50)
    for i in range(n):
        dp_ = list(dp)
        pi_ = 1 - p[i]
        for j in range(n + 1):
            dp[j] = dp_[j - 1] * p[i] + dp_[j] * pi_
        # pprint.pprint(dp, width = 50)
    return(sum(dp[n // 2 + 1:]))

n = int(input()) # n: odd, 1 <= n <= 2999
p = list(map(float, input().split())) # 0 < pi[i] < 1
print(f2(n, p))
Buggy python submission (verdict: Runtime Error):
# coding: utf-8

import sys
input = sys.stdin.readline

def f(N, A, K):
    dp = [0] * (K + 1)
    mina = min(A)
    minmax = mina + max(A)
    for i in range(mina, minmax):
        for x in A:
            i_ = i - x
            dp[i] = 1 if i_ < mina else dp[i_] ^ 1
            if dp[i]:
                break
    for i in range(minmax, K + 1):
        for x in A:
            dp[i] = dp[i - x] ^ 1
            if dp[i]:
                break
    return(dp[K])

ans = [ "Second", "First" ]
n, k = map(int, input().split()) # 1 <= n <= 100, 1 <= k <= 10^5
a = list(map(int, input().split()))
print(ans[f(n, a, k)])


Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

def f(N, A, K):
    dp = [0] * (K + 1)
    for i in range(K + 1):
        for x in A:
            if i < x:
                break
            if not dp[i - x]:
                dp[i] = 1
                break
    return(dp[K])

ans = [ "Second", "First" ]
n, k = map(int, input().split()) # 1 <= n <= 100, 1 <= k <= 10^5
a = list(map(int, input().split()))
print(ans[f(n, a, k)])
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from functools import lru_cache
from itertools import accumulate as accum
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

@lru_cache(maxsize = None)
def f(l, r):
    if l == r:
        return(0)
    cost = float('inf')
    for x in range(l, r):
        cost_ = f(l, x) + f(x + 1, r)
        if cost_ < cost:
            cost = cost_
    return(cost + acsum[r] - acsum[l - 1])

n = int(input()) # 2 <= n <= 400
acsum = list(accum(map(int, input().split()))) + [0]
print(f(0, n - 1))


Fixed submission:
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f2(n, a):
    acsum = list(accum(a)) + [0]
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
        if i + 1 != n:
            dp[i][i + 1] = a[i] + a[i + 1]
    for i in range(n - 3, -1, -1):
        for j in range(i + 2, n):
            c = float('inf')
            dpi = dp[i]
            for x in range(i, j):
                c_ = dpi[x] + dp[x + 1][j]
                if c_ < c:
                    c = c_
            dpi[j] = c + acsum[j] - acsum[i - 1]
    return(dp[0][n - 1])

n = int(input()) # 2 <= n <= 400
a = list(map(int, input().split()))
print(f2(n, a))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

from functools import lru_cache
from itertools import accumulate as accum
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

@lru_cache(maxsize = None)
def f(l, r):
    if l == r:
        return(0)
    return(min(f(l, x) + f(x + 1, r) for x in range(l, r)) \
        + acsum[r] - acsum[l - 1])

n = int(input()) # 2 <= n <= 400
acsum = list(accum(map(int, input().split()))) + [0]
print(f(0, n - 1))


Fixed submission:
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f2(n, a):
    acsum = list(accum(a)) + [0]
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
        if i + 1 != n:
            dp[i][i + 1] = a[i] + a[i + 1]
    for i in range(n - 3, -1, -1):
        for j in range(i + 2, n):
            c = float('inf')
            dpi = dp[i]
            for x in range(i, j):
                c_ = dpi[x] + dp[x + 1][j]
                if c_ < c:
                    c = c_
            dpi[j] = c + acsum[j] - acsum[i - 1]
    return(dp[0][n - 1])

n = int(input()) # 2 <= n <= 400
a = list(map(int, input().split()))
print(f2(n, a))