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


def knapsack(capacity, item_weights, item_values):
    no_current_item_values = [0] * (capacity + 1)
    for i, val in enumerate(item_values):
        with_current_item_values = [0] * (capacity + 1)
        for current_capacity in range(1, capacity + 1):
            if current_capacity < item_weights[i]:
                with_current_item_values[current_capacity] = no_current_item_values[current_capacity]
            else:
                with_current_item_values[current_capacity] = max(
                    no_current_item_values[current_capacity],
                    no_current_item_values[current_capacity - item_weights[i]] + val
                )
        no_current_item_values = with_current_item_values

    return no_current_item_values[-1]


inp = fileinput.input()

first_line_split = inp.readline().split(" ")

item_count = int(first_line_split[0])
capacity = int(first_line_split[1])

item_weights = []
item_values = []
for _ in range(item_count):
    split = inp.readline().split(" ")
    item_weights.append(int(split[0]))
    item_values.append(int(split[1]))

print(knapsack(capacity, item_weights, item_values))


Fixed submission:
import fileinput


def knapsack(capacity, item_weights, item_values):
    no_current_item_values = [0] * (capacity + 1)
    for i, val in enumerate(item_values):
        with_current_item_values = [0] * (capacity + 1)
        for current_capacity in range(1, capacity + 1):
            if current_capacity < item_weights[i]:
                with_current_item_values[current_capacity] = no_current_item_values[current_capacity]
            else:
                with_current_item_values[current_capacity] = max(
                    no_current_item_values[current_capacity],
                    no_current_item_values[current_capacity - item_weights[i]] + val
                )
        no_current_item_values = with_current_item_values

    return no_current_item_values[-1]


inp = fileinput.input()

first_line_split = inp.readline().split(" ")

item_count = int(first_line_split[0])
capacity = int(first_line_split[1])

item_weights = []
item_values = []
for _ in range(item_count):
    split = inp.readline().split(" ")
    item_weights.append(int(split[0]))
    item_values.append(int(split[1]))

print(knapsack(capacity, item_weights, item_values))
Buggy python submission (verdict: Runtime Error):
import fileinput


def solve_slimes(slimes):
    slime_union_table = [0] * len(slimes) * len(slimes)
    slime_cost_table = [0] * len(slimes) * len(slimes)

    for i in range(len(slimes)):
        slime_union_table[i] = slimes[i]

    for gap in range(1, len(slimes)):
        for li in range(len(slimes) - gap):
            split_size = slime_union_table[li] + slime_union_table[li + 1 + (gap - 1) * len(slimes)]
            slime_union_table[li + gap * len(slimes)] = split_size

            for split in range(0, gap):
                split_cost = slime_cost_table[li + split * len(slimes)] + slime_cost_table[li + split + 1 + (gap - split - 1) * len(slimes)] + split_size

                if slime_cost_table[li + gap * len(slimes)] == 0:
                    slime_cost_table[li + gap * len(slimes)] = split_cost

                else:
                    slime_cost_table[li + gap * len(slimes)] = min(
                        split_cost,
                        slime_cost_table[li + gap * len(slimes)]
                    )
    return slime_cost_table[len(slimes) * (len(slimes) - 1)]


inp = fileinput.FileInput()

inp.readline()
slimes = [int(v) for v in inp.readline().split()]

print(solve_slimes(slimes)

Fixed submission:
import fileinput


def solve_slimes(slimes):
    slime_union_table = [0] * len(slimes) * len(slimes)
    slime_cost_table = [0] * len(slimes) * len(slimes)

    for i in range(len(slimes)):
        slime_union_table[i] = slimes[i]

    for gap in range(1, len(slimes)):
        for li in range(len(slimes) - gap):
            split_size = slime_union_table[li] + slime_union_table[li + 1 + (gap - 1) * len(slimes)]
            slime_union_table[li + gap * len(slimes)] = split_size

            for split in range(0, gap):
                split_cost = slime_cost_table[li + split * len(slimes)] + slime_cost_table[li + split + 1 + (gap - split - 1) * len(slimes)] + split_size

                if slime_cost_table[li + gap * len(slimes)] == 0:
                    slime_cost_table[li + gap * len(slimes)] = split_cost

                else:
                    slime_cost_table[li + gap * len(slimes)] = min(
                        split_cost,
                        slime_cost_table[li + gap * len(slimes)]
                    )
    return slime_cost_table[len(slimes) * (len(slimes) - 1)]


inp = fileinput.FileInput()

inp.readline()
slimes = [int(v) for v in inp.readline().split()]

print(solve_slimes(slimes))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import fileinput


def solve_match(match_matrix):
    size = len(match_matrix)
    combo_dict = {}

    r = tuple(range(size))

    for col in range(size):
        for combo in itertools.combinations(r, col + 1):
            if col == 0:
                combo_dict[combo] = match_matrix[combo[0]][col]
            else:
                s = 0
                for i, row_num in enumerate(combo):
                    if match_matrix[row_num][col] == 1:
                        s += combo_dict[combo[:i] + combo[i + 1:]]
                combo_dict[combo] = s
    return combo_dict[r]


inp = fileinput.FileInput()
n = int(inp.readline())

arr = []
for _ in range(n):
    arr.append([int(v) for v in inp.readline().split(" ")])

print(solve_match(arr))


Fixed submission:
import itertools
import fileinput
 
 
def solve_match(match_matrix):
    size = len(match_matrix)

    combo_list = [0] * (2**size)

    combo_indexes = [[] for _ in range(size + 1)]
    for i in range(2**size):
        count = 0
        n = i
        while (n): 
            count += n & 1
            n >>= 1
        combo_indexes[count].append(i)

    for col in range(size):
        for combo in combo_indexes[col + 1]:
            if col == 0:
                for i in range(size):
                    if (combo & (1 << i)):
                        combo_list[combo] = match_matrix[i][col]
                        break
            else:
                s = 0
                cnt = 0
                for i in range(size):
                    flag = 1 << i
                    if (combo & flag) and match_matrix[i][col] == 1:
                        s += combo_list[combo & (~flag)]
                        cnt += 1
                        if cnt == col + 1:
                            break
                
                combo_list[combo] = s % (10**9 + 7)
    return combo_list[-1]
 
 
inp = fileinput.FileInput()
n = int(inp.readline())
 
arr = []
for _ in range(n):
    arr.append([int(v) for v in inp.readline().split(" ")])
 
print(solve_match(arr))
Buggy python submission (verdict: Time Limit Exceeded):
import array

class Solver:

  def solve(self):
    n, k = map(int, raw_input().split())
    x = map(int, raw_input().split())
    y = [0] * (100100 - len(x))
    dp = array.array('i', [1<<30] * 100100)
    dp[0] = 0
    h = array.array('i', x + y)

    for i in xrange(n):
      for kk in xrange(k):
        j = kk + 1
        v = dp[i] + abs(h[i] - h[i+j])
        if dp[i+j] > v:
          dp[i+j] = v

    print dp[n-1]

Solver().solve()

Fixed submission:
import array

class Solver:

  def solve(self):
    n, k = map(int, raw_input().split())
    x = map(int, raw_input().split())
    y = [0] * (100100 - len(x))
    dp = array.array('i', [1<<30] * 100100)
    dp[0] = 0
    h = array.array('i', x + y)

    for i in xrange(n):
      dpi = dp[i]
      hi = h[i]
      for kk in xrange(k):
        j = kk + 1
        v = dpi + abs(hi - h[i+j])
        if dp[i+j] > v:
          dp[i+j] = v

    print dp[n-1]

Solver().solve()

Buggy python submission (verdict: Time Limit Exceeded):
import array

class Solver:

  def solve(self):
    n, k = map(int, raw_input().split())
    x = map(int, raw_input().split())
    dp = array.array('i', [1<<30] * 100100)
    dp[0] = 0
    h = array.array('i', [0] * 100100)
    for i in xrange(n):
      h[i] = x[i]

    for i in xrange(n):
      for kk in xrange(k):
        j = kk + 1
        v = dp[i] + abs(h[i] - h[i+j])
        if dp[i+j] > v:
          dp[i+j] = v

    print dp[n-1]

Solver().solve()

Fixed submission:
import array

class Solver:

  def solve(self):
    n, k = map(int, raw_input().split())
    x = map(int, raw_input().split())
    y = [0] * (100100 - len(x))
    dp = array.array('i', [1<<30] * 100100)
    dp[0] = 0
    h = array.array('i', x + y)

    for i in xrange(n):
      dpi = dp[i]
      hi = h[i]
      for kk in xrange(k):
        j = kk + 1
        v = dpi + abs(hi - h[i+j])
        if dp[i+j] > v:
          dp[i+j] = v

    print dp[n-1]

Solver().solve()
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
arr = set()
arr.add(s)
for i in range(len(s)-1):
    for j in range(0, len(s)):
        arr.add(s[j:j+i+1])
arr = list(arr)
arr.sort()
print(arr[k-1])


Fixed submission:
s = input()
k = int(input())
arr = set()
arr.add(s)
for i in range(len(s)-1):
    if i > 5:
        break
    for j in range(0, len(s)):
        arr.add(s[j:j+i+1])

arr = list(arr)
arr.sort()
print(arr[k-1])

Buggy python submission (verdict: Runtime Error):
s = input()
k = int(input())
arr = set()
arr.add(s)
for i in range(len(s)-1):
    for j in range(1, len(s)):
        arr.add(s[j:j+i+1])
arr = list(arr)
arr.sort()
print(arr[k-1])


Fixed submission:
s = input()
k = int(input())
arr = set()
arr.add(s)
for i in range(len(s)-1):
    if i > 5:
        break
    for j in range(0, len(s)):
        arr.add(s[j:j+i+1])

arr = list(arr)
arr.sort()
print(arr[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
arr = set()
arr.add(s)
for i in range(len(s)-1):
    for j in range(0, len(s)):
        arr.add(s[j:j+i+1])
arr = list(arr)
arr.sort()
print(arr[k-1])


Fixed submission:
s = input()
k = int(input())
arr = set()
arr.add(s)
for i in range(len(s)-1):
    if i > 5:
        break
    for j in range(0, len(s)):
        arr.add(s[j:j+i+1])

arr = list(arr)
arr.sort()
print(arr[k-1])
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
r = "Yes"
for i in range(1, h-1):
    for j in range(1, w-1):
        if a[i][j] == "#" and a[i - 1][j] == "." and a[i + 1][j] == "." and a[i][j - 1] == "." and a[i][j + 1] == ".":
          r = "No"
print(r)


Fixed submission:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
r = "Yes"
for i in range(1, h-1):
    for j in range(1, w-1):
        if s[i][j] == "#" and s[i - 1][j] == "." and s[i + 1][j] == "." and s[i][j - 1] == "." and s[i][j + 1] == ".":
          r = "No"
print(r)
Buggy python submission (verdict: Runtime Error):
d = dict(a=input(), b=input(), c=input())
op = 'a'
while True:
    if not d[op]:
        print(op.upper())
        break
    op = d[op].pop(0)


Fixed submission:
d = dict(a=list(input()), b=list(input()), c=list(input()))
op = 'a'
while True:
    if not d[op]:
        print(op.upper())
        break
    op = d[op].pop(0)
Buggy python submission (verdict: Runtime Error):
n = int(input())
def c(x,y):
    if 0 <= x < n and 0 <= y < 2:
        if cache[y][x] != " ":
            return cache[y][x]

        if x == 0 and y == 0:
            total = matrice[0][0]
        else:
            if x > 0:
                tt1 = c(x-1,y)
            else:
                tt1 = 0
            if y > 0:
                tt2 = c(x,y-1)
            else:
                tt2 = 0
            total = max(tt1,tt2) + matrice[y][x]
        cache[y][x] = total
        return total

    
matrice = []
cache = [ [" " for i in range(n)] for a in range(2) ] 
for i in range(2):
    matrice.append( [ int(i) for i in input().split() ] )

print( c(n-1,1) )


Fixed submission:
argent = int(input())
gateau = int(input())
donut = int(input())

argent -= gateau
argent %= donut
print(argent)
Buggy python submission (verdict: Runtime Error):
def main()
    a = int(input())
    b = int(input())
    c = int(input())
    tt = int(input())
    total = 0

    for yen500 in range(a+1):
        for yen100 in range(b+1):
            for yen50 in range(c+1):
                if yen500 * 500 + yen100 * 100 + yen50 * 50 == tt:
                    total += 1

    print(total)

main()

Fixed submission:
def main():
    a = int(input())
    b = int(input())
    c = int(input())
    tt = int(input())
    total = 0

    for yen500 in range(a+1):
        for yen100 in range(b+1):
            for yen50 in range(c+1):
                if yen500 * 500 + yen100 * 100 + yen50 * 50 == tt:
                    total += 1

    print(total)

main()
Buggy python submission (verdict: Runtime Error):
    n = int(input())
    def c(x,y):
        if 0 <= x < n and 0 <= y < 2:
            if cache[y][x] != " ":
                return cache[y][x]
     
            if x == 0 and y == 0:
                total = matrice[0][0]
            else:
                if x > 0:
                    tt1 = c(x-1,y)
                else:
                    tt1 = 0
                if y > 0:
                    tt2 = c(x,y-1)
                else:
                    tt2 = 0
                total = max(tt1,tt2) + matrice[y][x]
            cache[y][x] = total
            return total
     
        
    matrice = []
    cache = [ [" " for i in range(n)] for a in range(2) ] 
    for i in range(2):
        matrice.append( [ int(i) for i in input().split() ] )
     
    print( c(n-1,1) )

Fixed submission:
n = int(input())
def c(x,y):
    if 0 <= x < n and 0 <= y < 2:
        if cache[y][x] != " ":
            return cache[y][x]

        if x == 0 and y == 0:
            total = matrice[0][0]
        else:
            if x > 0:
                tt1 = c(x-1,y)
            else:
                tt1 = 0
            if y > 0:
                tt2 = c(x,y-1)
            else:
                tt2 = 0
            total = max(tt1,tt2) + matrice[y][x]
        cache[y][x] = total
        return total

    
matrice = []
cache = [ [" " for i in range(n)] for a in range(2) ] 
for i in range(2):
    matrice.append( [ int(i) for i in input().split() ] )

print( c(n-1,1) )
Buggy python submission (verdict: Time Limit Exceeded):
import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# sum_vの取りうる上限値
MAX_V = (10**3+1) * N

# 最小値を求めるので無限大の値
f_inf = float('inf')

def chmin(a, b):
    if a <= b:
        return a
    else:
        return b

def knapsack(n, w):
    # dpの初期化　dp[i][sum_v]は重さの総和の最小値
    dp = [[f_inf for i in range(MAX_V)] for j in range(N+1)]
    # 初期条件
    dp[0][0] = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        w, v = map(int, input().split())
        for sum_v in range(MAX_V):
            # i番目の品物を選ぶ場合
            if (sum_v -v >= 0):
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v - v] + w)
            # i番目の品物を選ばない場合
            dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v])
    #dp[N][sum_v]の値が、W以下であるsum_vの値の最大値
    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)

knapsack(N, W)




Fixed submission:
import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# sum_vの取りうる上限値
MAX_V = (10**3) * N +1
# 最小値を求めるので無限大の値
f_inf = float('inf')

def knapsack(n, w):
    # dpの初期化　dp[sum_v]は重さの総和の最小値
    dp = [f_inf] * MAX_V
    # 初期条件
    dp[0] = 0
    sum_v = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(MAX_V, v-1, -1):
            new_weight = dp[j - v] + w
            if new_weight > W:
                continue
            if dp[j] > new_weight:
                dp[j] = new_weight

    ans = 0
    for sum_v in range(MAX_V):
        if dp[sum_v] <= W:
            ans = sum_v
    print(ans)

knapsack(N, W)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
# input処理を高速化する
input = sys.stdin.readline

def chmax(a, b):
    if a >= b:
        return a
    return b

def chmin(a, b):
    if a <= b:
        return a
    return b

def main():
    N = int(input())
    a = list(map(int, input().split()))

    # aiからajのX−Yの最大値
    # [左端,右端)=[l,r)からの遷移    
    # 左をとる[l+1,r)、右をとる[l,r−1)の2通り
    dp = [[0] * (N+2)  for _ in range(N+2)]
    dp[N+1][N+1] = 4999999995

    for len in range(1, N + 1):
        for i in range(N + 1 - len):
            j = i + len

            if (N - len) % 2 == 0:
                dp[i][j] = chmax(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = chmin(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])

    print(dp[0][N])
 


main()

Fixed submission:
import sys
# input処理を高速化する
input = sys.stdin.readline

def chmax(a, b):
    if a >= b:
        return a
    return b

def chmin(a, b):
    if a <= b:
        return a
    return b

def main():
    N = int(input())
    a = list(map(int, input().split()))

    # aiからajのX−Yの最大値
    # [左端,右端)=[l,r)からの遷移    
    # 左をとる[l+1,r)、右をとる[l,r−1)の2通り
    dp = [[0] * (N+2)  for _ in range(N+2)]

    for len in range(1, N + 1):
        for i in range(N + 1 - len):
            j = i + len

            if (N - len) % 2 == 0:
                dp[i][j] = chmax(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = chmin(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])

    print(dp[0][N])

main()
Buggy python submission (verdict: Time Limit Exceeded):
n,k=input().split()
n=int(n)
k=int(k)
a=[int(x) for x in input().split()]


dp=[1e18]*n
dp[0]=0


dp[1]=abs(a[1]-a[0])

m=pow(10,10)

for i in range(2,n):
    m=pow(10,10)
    for j in range(1,k+1):
        if i-j>=0:
            m=min(m,dp[i-j]+abs(a[i]-a[i-j]))
    dp[i]=m
    
    
        

print(dp[n-1])    
        

    
    


Fixed submission:
n,k=input().split()
n=int(n)
k=int(k)
a=[int(x) for x in input().split()]


dp=[1e18]*n
dp[0]=0


dp[1]=abs(a[1]-a[0])

m=pow(10,10)

for i in range(2,n):
    m=pow(10,10)
    for j in range(1,k+1):
        if i-j>=0:
            m=min(m,dp[i-j]+abs(a[i]-a[i-j]))
    dp[i]=m
    
    
        

print(dp[n-1])
Buggy python submission (verdict: Runtime Error):
N=int(input())
inputs=[]
dp=[]
for _ in range(N):
    inputs.append([int(x) for x in input().split()])
    dp.append([0]*3)

for j in range(3):
    dp[0][j]=inputs[0][j]

for i in range(1,N):

    for j in range(3):
        
        for k in range(3):
            if(j!=k):
                dp[i][j]=max(dp[i-1][k],dp[i][j])
        
        dp[i][j]+=inputs[i][j]


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


Fixed submission:
N=int(input())
inputs=[]
dp=[]
for _ in range(N):
    inputs.append([int(x) for x in input().split()])
    dp.append([0]*3)

for j in range(3):
    dp[0][j]=inputs[0][j]

for i in range(1,N):

    for j in range(3):
        
        for k in range(3):
            if(j!=k):
                dp[i][j]=max(dp[i-1][k],dp[i][j])
        
        dp[i][j]+=inputs[i][j]



print(max(dp[N-1]))
Buggy python submission (verdict: Runtime Error):
n,k = map(int, input().split())
a = list(map(int, input().split()))
 
ind = a.index(1)
 
left = ind
right = n-1-ind
import math
if left<k-1 or right<k-1:
	print (n//(k-1))
else:
	if k>=n:
		print (1)
	else:
		print(int(math.ceil(left/(k-1))+math.ceil(right/(k-1))))


Fixed submission:
s = list(input())
print (s.count('+')-s.count('-'))
Buggy python submission (verdict: Time Limit Exceeded):

n, k = map(int, raw_input().split())
hs = map(int, raw_input().split())
oo = max(hs) * n + 1


dp = [oo] * n
dp[n - 1] = 0
for i in range(n - 2, -1, -1):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i] = min(dp[i], dp[i + j] + abs(hs[i] - hs[i + j]))
print(dp[0])


Fixed submission:
n, k = map(int, raw_input().split())
hs = map(int, raw_input().split())
oo = max(hs) * n + 1


dp = [oo] * n
dp[n - 1] = 0
for i in range(n - 2, -1, -1):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i] = min(dp[i], dp[i + j] + abs(hs[i] - hs[i + j]))
print(dp[0])
Buggy python submission (verdict: Time Limit Exceeded):


n, w = map(int, raw_input().split())
items = []
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))

dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    wi, vi = items[i - 1]
    for j in range(1, w + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if j >= wi:
            dp[i][j] = max(dp[i][j], vi + dp[i - 1][j - wi])
print(dp[n][w])


Fixed submission:

n, w = map(int, raw_input().split())
items = []
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))

dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    wi, vi = items[i - 1]
    for j in range(1, w + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if j >= wi:
            dp[i][j] = max(dp[i][j], vi + dp[i - 1][j - wi])
print(dp[n][w])
Buggy python submission (verdict: Time Limit Exceeded):


s = raw_input()
t = raw_input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if s[i - 1] == t[j - 1]:
            dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1])
        else:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1])

l = dp[len(s)][len(t)]
resp = []
inds = len(s)
indt = len(t)
while len(resp) < l:
    if s[inds - 1] == t[indt - 1] and dp[inds][indt] == 1 + dp[inds - 1][indt - 1]:
        resp.append(s[inds - 1])
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt - 1]:
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt]:
        inds -= 1
        continue
    if dp[inds][indt] == dp[inds][indt - 1]:
        indt -= 1
        continue
resp.reverse()
print(''.join(resp))


Fixed submission:

s = raw_input()
t = raw_input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if s[i - 1] == t[j - 1]:
            dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1])
        else:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1])

l = dp[len(s)][len(t)]
resp = []
inds = len(s)
indt = len(t)
while len(resp) < l:
    if s[inds - 1] == t[indt - 1] and dp[inds][indt] == 1 + dp[inds - 1][indt - 1]:
        resp.append(s[inds - 1])
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt - 1]:
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt]:
        inds -= 1
        continue
    if dp[inds][indt] == dp[inds][indt - 1]:
        indt -= 1
        continue
resp.reverse()
print(''.join(resp))
Buggy python submission (verdict: Time Limit Exceeded):


n = input()
p = map(float, raw_input().split())

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    pi = p[i - 1]
    for j in range(i + 1):
        dp[i][j] = pi * dp[i - 1][j - 1] + (1 - pi) * dp[i - 1][j]
resp = 0
for i in range(n / 2 + 1, n + 1):
    resp += dp[n][i]
print(resp)


Fixed submission:

n = input()
p = map(float, raw_input().split())

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    pi = p[i - 1]
    for j in range(i + 1):
        dp[i][j] = pi * dp[i - 1][j - 1] + (1 - pi) * dp[i - 1][j]
resp = 0
for i in range(n / 2 + 1, n + 1):
    resp += dp[n][i]
print(resp)