Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)

Fixed submission:
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return

num[0] = -heappop(h)
dfs(0)
print(sum(c) - max(c))
print(*num)

Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x, par):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v, x)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)

Fixed submission:
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return

num[0] = -heappop(h)
dfs(0)
print(sum(c) - max(c))
print(*num)

Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x, par):
	global h
	for v in adj[x]:
		if v == par:
			continue
		num[v] = -heappop(h)
		dfs(v, x)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)

Fixed submission:
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return

num[0] = -heappop(h)
dfs(0)
print(sum(c) - max(c))
print(*num)
Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, inpuit().split())
print((c//a)*b)

Fixed submission:
a, b, c = map(int, input().split())
print((c//a)*b)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
	return sys.stdin.readline()[:-1]
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
	for j in range(s+1):
		dp[i+1][j] += dp[i][j] * 2
		dp[i+1][j] %= MOD
		if j+a[i] <= s:
			dp[i+1][j+a[i]] += dp[i][j]
			dp[i+1][j+a[i]] %= MOD
#print(*dp, sep="\n")
res = 0
for j in range(s+1):
	if j*2 >= s:
		res += dp[n][j] * 3
		res %= MOD

if s%2 == 0:
	dpp = [0 for _ in range(s+1)]
	dpp[0] = 1
	for i in range(n):
		for j in range(s-a[i], -1, -1):
			dpp[j+a[i]] += dpp[j]
			dpp[j+a[i]] %= MOD
	res -= dpp[s//2] * 3

print((pow(3, n, MOD) - res) % MOD)

Fixed submission:
import sys
def input():
	return sys.stdin.readline()[:-1]
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
	for j in range(s+1):
		dp[i+1][j] += dp[i][j] * 2
		dp[i+1][j] %= MOD
		if j+a[i] <= s:
			dp[i+1][j+a[i]] += dp[i][j]
			dp[i+1][j+a[i]] %= MOD
#print(*dp, sep="\n")
res = 0
for j in range(s+1):
	if j*2 >= s:
		res += dp[n][j] * 3
		res %= MOD

if s%2 == 0:
	dpp = [0 for _ in range(s+1)]
	dpp[0] = 1
	for i in range(n):
		for j in range(s-a[i], -1, -1):
			dpp[j+a[i]] += dpp[j]
			dpp[j+a[i]] %= MOD
	res -= dpp[s//2] * 3

print((pow(3, n, MOD) - res) % MOD)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
print(gcd(a))

Fixed submission:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
b=a[0]
for x in a[1:]:
  b=gcd(b,x)
print(b)

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
n=int(input())
a=list(map,input().split())
print(gcd(a))

Fixed submission:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
b=a[0]
for x in a[1:]:
  b=gcd(b,x)
print(b)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353
s = input()
n = len(s)
R = s.count("0") * 2 + s.count("1")
B = 2*n - R
rb = [[R, B] for _ in range(2*n)]
if s[0] == "0":
	rb[0] = [2, 0]
elif s[0] == "1":
	rb[0] = [1, 1]
else:
	rb[0] = [0, 2]
for i in range(1, n):
	if s[i] == "0":
		rb[i] = [rb[i-1][0] + 2, rb[i-1][1] + 0]
	elif s[i] == "1":
		rb[i] = [rb[i-1][0] + 1, rb[i-1][1] + 1]
	else:
		rb[i] = [rb[i-1][0] + 0, rb[i-1][1] + 2]

dp = [[0 for _ in range(R+1)] for _ in range(2*n)]
if rb[0][0] >= 1:
	dp[0][1] = 1
if rb[0][1] >= 1:
	dp[0][0] = 1
for i in range(1, 2*n):
	for j in range(R+1):
		if j > 0 and rb[i][0] >= j:
			dp[i][j] += dp[i-1][j-1]
			dp[i][j] %= MOD
		if j != i+1 and rb[i][1] >= i+1 - j:
			dp[i][j] += dp[i-1][j]
			dp[i][j] %= MOD

print(dp[2*n-1][R])

Fixed submission:
MOD = 998244353
s = input()
n = len(s)
R = s.count("0") * 2 + s.count("1")
B = 2*n - R
rb = [[R, B] for _ in range(2*n)]
if s[0] == "0":
	rb[0] = [2, 0]
elif s[0] == "1":
	rb[0] = [1, 1]
else:
	rb[0] = [0, 2]
for i in range(1, n):
	if s[i] == "0":
		rb[i] = [rb[i-1][0] + 2, rb[i-1][1] + 0]
	elif s[i] == "1":
		rb[i] = [rb[i-1][0] + 1, rb[i-1][1] + 1]
	else:
		rb[i] = [rb[i-1][0] + 0, rb[i-1][1] + 2]

dp = [[0 for _ in range(R+1)] for _ in range(2*n)]
if rb[0][0] >= 1:
	dp[0][1] = 1
if rb[0][1] >= 1:
	dp[0][0] = 1
for i in range(1, 2*n):
	for j in range(R+1):
		if j > 0 and rb[i][0] >= j:
			dp[i][j] += dp[i-1][j-1]
			dp[i][j] %= MOD
		if j != i+1 and rb[i][1] >= i+1 - j:
			dp[i][j] += dp[i-1][j]
			dp[i][j] %= MOD

print(dp[2*n-1][R])

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353
s = input()
n = len(s)
R = s.count("0") * 2 + s.count("1")
B = 2*n - R
rb = [[R, B] for _ in range(2*n)]
if s[0] == "0":
	rb[0] = [2, 0]
elif s[0] == "1":
	rb[0] = [1, 1]
else:
	rb[0] = [0, 2]
for i in range(1, n):
	if s[i] == "0":
		rb[i] = [rb[i-1][0] + 2, rb[i-1][1] + 0]
	elif s[i] == "1":
		rb[i] = [rb[i-1][0] + 1, rb[i-1][1] + 1]
	else:
		rb[i] = [rb[i-1][0] + 0, rb[i-1][1] + 2]

dp = [[0 for _ in range(R+1)] for _ in range(2*n)]
if rb[0][0] >= 1:
	dp[0][1] = 1
if rb[0][1] >= 1:
	dp[0][0] = 1
for i in range(1, 2*n):
	for j in range(R+1):
		if j > 0 and rb[i][0] >= j:
			dp[i][j] += dp[i-1][j-1]
			dp[i][j] %= MOD
		if j != i+1 and rb[i][1] >= i+1 - j:
			dp[i][j] += dp[i-1][j]
			dp[i][j] %= MOD

print(dp[2*n-1][R])

Fixed submission:
MOD = 998244353
s = input()
n = len(s)
R = s.count("0") * 2 + s.count("1")
B = 2*n - R
rb = [[R, B] for _ in range(2*n)]
if s[0] == "0":
	rb[0] = [2, 0]
elif s[0] == "1":
	rb[0] = [1, 1]
else:
	rb[0] = [0, 2]
for i in range(1, n):
	if s[i] == "0":
		rb[i] = [rb[i-1][0] + 2, rb[i-1][1] + 0]
	elif s[i] == "1":
		rb[i] = [rb[i-1][0] + 1, rb[i-1][1] + 1]
	else:
		rb[i] = [rb[i-1][0] + 0, rb[i-1][1] + 2]

dp = [[0 for _ in range(R+1)] for _ in range(2*n)]
if rb[0][0] >= 1:
	dp[0][1] = 1
if rb[0][1] >= 1:
	dp[0][0] = 1
for i in range(1, 2*n):
	for j in range(R+1):
		if j > 0 and rb[i][0] >= j:
			dp[i][j] += dp[i-1][j-1]
			dp[i][j] %= MOD
		if j != i+1 and rb[i][1] >= i+1 - j:
			dp[i][j] += dp[i-1][j]
			dp[i][j] %= MOD

print(dp[2*n-1][R])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
sys.setrecursionlimit(10 ** 6)

class UnionFind():
	def __init__(self, lis):
		self.table = [-1 for _ in range(len(lis))]
		self.size = [x for x in lis]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
		return

n, m = map(int, input().split())
x = list(map(int, input().split()))
adj = [[] for _ in range(n)]
e = []
for i in range(m):
	a, b, y = map(int, input().split())
	a, b = a-1, b-1
	e.append((y, a, b))

used = [False for _ in range(m)]
candidate = [False for _ in range(m)]
e.sort()
uf = UnionFind(x)
for i in range(m):
	y, a, b = e[i]
	adj[a].append((b, y, i))
	adj[b].append((a, y, i))
	uf.unite(a, b)
	if uf.size[uf.find(a)] >= y:
		candidate[i] = True

ans = 0
for i in range(m-1, -1, -1):
	if used[i]:
		continue
	if not candidate[i]:
		ans += 1
	else:
		used[i] = True
		y, a, b = e[i]
		stack = [a, b]
		while stack:
			l = stack.pop()
			for v, z, j in adj[l]:
				if used[j]:
					continue
				if z <= y:
					stack.append(v)
					used[j] = True

print(ans)

Fixed submission:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
sys.setrecursionlimit(10 ** 6)

class UnionFind():
	def __init__(self, lis):
		self.table = [-1 for _ in range(len(lis))]
		self.size = [x for x in lis]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
		return

n, m = map(int, input().split())
x = list(map(int, input().split()))
adj = [[] for _ in range(n)]
e = []
for i in range(m):
	a, b, y = map(int, input().split())
	a, b = a-1, b-1
	e.append((y, a, b))

used = [False for _ in range(m)]
candidate = [False for _ in range(m)]
e.sort()
uf = UnionFind(x)
for i in range(m):
	y, a, b = e[i]
	adj[a].append((b, y, i))
	adj[b].append((a, y, i))
	uf.unite(a, b)
	if uf.size[uf.find(a)] >= y:
		candidate[i] = True

ans = 0
for i in range(m-1, -1, -1):
	if used[i]:
		continue
	if not candidate[i]:
		ans += 1
	else:
		used[i] = True
		y, a, b = e[i]
		stack = [a, b]
		while stack:
			l = stack.pop()
			for v, z, j in adj[l]:
				if used[j]:
					continue
				if z <= y:
					stack.append(v)
					used[j] = True

print(ans)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
#print(sushi)
num = 0
kind = set()
changable = []
for i in range(k):
	num += sushi[i][1]
	if sushi[i][0] in kind:
		changable.append(sushi[i][1])
	else:
		kind.add(sushi[i][0])

num += len(kind)**2
changable.reverse()
#print(changable)
ans = num

for i in range(k, n):
	if sushi[i][0] not in kind:
		num += sushi[i][1] + 2*len(kind)+1 - changable.pop()
		#print(num, kind)
		kind.add(sushi[i][0])
		ans = max(ans, num)

	if not changable:
		break

print(ans)

Fixed submission:
n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
#print(sushi)
num = 0
kind = set()
changable = []
for i in range(k):
	num += sushi[i][1]
	if sushi[i][0] in kind:
		changable.append(sushi[i][1])
	else:
		kind.add(sushi[i][0])

num += len(kind)**2
#changable.reverse()
#print(changable)
ans = num

for i in range(k, n):
	if not changable:
		break

	if sushi[i][0] not in kind:
		num += sushi[i][1] + 2*len(kind)+1 - changable.pop()
		#print(num, kind)
		kind.add(sushi[i][0])
		ans = max(ans, num)


print(ans)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
#print(sushi)
num = 0
kind = set()
changable = []
for i in range(k):
	num += sushi[i][1]
	if sushi[i][0] in kind:
		changable.append(sushi[i][1])
	else:
		kind.add(sushi[i][0])

num += len(kind)**2
changable.reverse()
#print(changable)
ans = num

for i in range(k, n):
	if sushi[i][0] not in kind:
		num += sushi[i][1] + 2*len(kind)+1 - changable.pop()
		#print(num, kind)
		kind.add(sushi[i][0])
		ans = max(ans, num)

print(ans)

Fixed submission:
n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
#print(sushi)
num = 0
kind = set()
changable = []
for i in range(k):
	num += sushi[i][1]
	if sushi[i][0] in kind:
		changable.append(sushi[i][1])
	else:
		kind.add(sushi[i][0])

num += len(kind)**2
#changable.reverse()
#print(changable)
ans = num

for i in range(k, n):
	if not changable:
		break

	if sushi[i][0] not in kind:
		num += sushi[i][1] + 2*len(kind)+1 - changable.pop()
		#print(num, kind)
		kind.add(sushi[i][0])
		ans = max(ans, num)


print(ans)
Buggy python submission (verdict: Runtime Error):
MOD = 10**9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % MOD

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % MOD

h, w, k = map(int, input().split())
ans = k * f_list[h+w] * f_r_list[h+w-k]
ans += (h+w) * k * (k+1) * f_list[h+w-1] * f_r_list[2] * f_r_list[h+w-k]
ans %= MOD
ans += h * w * f_list[h+w-2] * (k-1) * k * (k+1) * pow(3, MOD-2, MOD) * f_r_list[h+w-k]
ans %= MOD
print(ans)

Fixed submission:
MOD = 10**9 + 7
list_size = 20000001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % MOD

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % MOD

h, w, k = map(int, input().split())
ans = k * f_list[h+w] * f_r_list[h+w-k]
ans += (h+w) * k * (k+1) * f_list[h+w-1] * f_r_list[2] * f_r_list[h+w-k]
ans %= MOD
ans += h * w * f_list[h+w-2] * (k-1) * k * (k+1) * pow(3, MOD-2, MOD) * f_r_list[h+w-k]
ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
	dp[i] = dp[i-1] + abs(h[i] - h[i-1])
	for j in range(1, min(i, k)+1):
		dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

print(dp[-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
	dp[i] = dp[i-1] + abs(h[i] - h[i-1])
	for j in range(1, min(i, k)+1):
		dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, W = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(1, n+1):
	for w in range(W+1):
		if t[i-1][0] > w:
			dp[i][w] = dp[i-1][w]
		else:
			dp[i][w] = max(dp[i-1][w], dp[i-1][max(0, w - t[i-1][0])] + t[i-1][1])
print(dp[-1][-1])

Fixed submission:
n, W = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(1, n+1):
	for w in range(W+1):
		if t[i-1][0] > w:
			dp[i][w] = dp[i-1][w]
		else:
			dp[i][w] = max(dp[i-1][w], dp[i-1][max(0, w - t[i-1][0])] + t[i-1][1])
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(float, input().split()))
dp = [[0 for _ in range(n+1)] for _ in range(n)]
#dp[i][j]: iまで投げてj枚表の確率
dp[0][0] = 1 - p[0]
dp[0][1] = p[0]

for i in range(1, n):
	for j in range(i+2):
		if j == 0:
			dp[i][j] = dp[i-1][j] * (1 - p[i])
		else:
			dp[i][j] = dp[i-1][j] * (1 - p[i]) + dp[i-1][j-1] * p[i]

#print(dp)
ans = 0
for i in range(n//2 + 1, n+1):
	ans += dp[-1][i]
print(ans)

Fixed submission:
n = int(input())
p = list(map(float, input().split()))
dp = [[0 for _ in range(n+1)] for _ in range(n)]
#dp[i][j]: iまで投げてj枚表の確率
dp[0][0] = 1 - p[0]
dp[0][1] = p[0]

for i in range(1, n):
	for j in range(i+2):
		if j == 0:
			dp[i][j] = dp[i-1][j] * (1 - p[i])
		else:
			dp[i][j] = dp[i-1][j] * (1 - p[i]) + dp[i-1][j-1] * p[i]

#print(dp)
ans = 0
for i in range(n//2 + 1, n+1):
	ans += dp[-1][i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
#dp[l][r]: 左l個右r個取ったところからの前-後max
for i in range(n):
	dp[i][n-1-i] = a[i]
for x in range(n-2, -1, -1):
	for y in range(x+1):
		l, r = y, x-y
		dp[l][r] = max(-dp[l+1][r] + a[l], -dp[l][r+1] + a[-(r+1)])

print(dp[0][0])

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

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
#dp[l][r]: 左l個右r個取ったところからの前-後max
for i in range(n):
	dp[i][n-1-i] = a[i]
for x in range(n-2, -1, -1):
	for y in range(x+1):
		l, r = y, x-y
		dp[l][r] = max(-dp[l+1][r] + a[l], -dp[l][r+1] + a[-(r+1)])

print(dp[0][0])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9+7
dp = [[0 for _ in [0]*(k+1)] for _ in [0]*n]
sum_list = [[0] for _ in [0]*n]

def make_sum(i):
	for j in range(k+1):
		sum_list[i].append(sum_list[i][-1] + dp[i][j])
	return

for j in range(a[0]+1):
	dp[0][j] = 1

for i in range(1, n):
	make_sum(i-1)
	for j in range(k+1):
		dp[i][j] = sum_list[i-1][j+1] - sum_list[i-1][max(0, j-a[i])]

print(dp[n-1][k] % MOD)

Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9+7
dp = [[0 for _ in [0]*(k+1)] for _ in [0]*n]
sum_list = [[0] for _ in [0]*n]

def make_sum(i):
	for j in range(k+1):
		sum_list[i].append((sum_list[i][-1] + dp[i][j]) % MOD)
	return

for j in range(a[0]+1):
	dp[0][j] = 1

for i in range(1, n):
	make_sum(i-1)
	for j in range(k+1):
		dp[i][j] = (sum_list[i-1][j+1] - sum_list[i-1][max(0, j-a[i])]) % MOD

print(dp[n-1][k])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
cost = [0]
for p in a:
	cost.append(cost[-1] + p)
def get_cost(l, r):
	return cost[r+1] - cost[l]

dp = [[float("inf") for _ in range(n)] for _ in range(n)]
for i, p in enumerate(a):
	dp[i][i] = 0

for g in range(1, n):
	for l in range(n-g):
		r = l + g
		for m in range(l, r):
			dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + get_cost(l, r))

print(dp[0][n-1])

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
cost = [0]
for p in a:
	cost.append(cost[-1] + p)
def get_cost(l, r):
	return cost[r+1] - cost[l]

dp = [[float("inf") for _ in range(n)] for _ in range(n)]
for i, p in enumerate(a):
	dp[i][i] = 0

for g in range(1, n):
	for l in range(n-g):
		r = l + g
		for m in range(l, r):
			dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + get_cost(l, r))

#print(dp)
print(dp[0][n-1])
Buggy python submission (verdict: Time Limit Exceeded):
class Rmax():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0 for _ in range(2*self.n-1)]

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
		return

	#[a, b)
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return 0
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return max(vl, vr)

n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Rmax(n)
for h, a in zip(H, A):
	h -= 1
	opt = dp.Get(0, h) + a
	if opt > dp.Access(h):
		dp.Update(h, opt)

#print(dp.node)
print(dp.Get(0, n))

Fixed submission:
INF = 10**30

class Rmax():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0 for _ in range(2*self.n-1)]

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
		return

	#[a, b)
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return 0
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return max(vl, vr)

n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Rmax(n)
for h, a in zip(H, A):
	h -= 1
	opt = dp.Get(0, h) + a
	if opt > dp.Access(h):
		dp.Update(h, opt)

#print(dp.node)
print(dp.Get(0, n))
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7

def mat_dot(one, two, mod):
	return [[sum([(one[i][k]*two[k][j])%mod for k in range(max(len(two), len(one[0])))])%mod for j in range(len(two[0]))] for i in range(len(one))]

def mat_pow(mat, exp, mod):
	size = len(mat)
	res = [[0 for _ in range(size)] for _ in range(size)]
	for i in range(size):
		res[i][i] = 1
	cnt = 0
	while (1<<cnt) <= exp:
		if (exp>>cnt)&1:
			res = mat_dot(res, mat, mod)
		mat = mat_dot(mat, mat, mod)
		cnt += 1
	return res

n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = mat_pow(a, k, MOD)
print(sum([sum(x) for x in b]) % MOD)

Fixed submission:
MOD = 10**9+7

def mat_dot(one, two, mod):
	return [[sum([(one[i][k]*two[k][j])%mod for k in range(max(len(two), len(one[0])))])%mod for j in range(len(two[0]))] for i in range(len(one))]

def mat_pow(mat, exp, mod):
	size = len(mat)
	res = [[0 for _ in range(size)] for _ in range(size)]
	for i in range(size):
		res[i][i] = 1
	cnt = 0
	while (1<<cnt) <= exp:
		if (exp>>cnt)&1:
			res = mat_dot(res, mat, mod)
		mat = mat_dot(mat, mat, mod)
		cnt += 1
	return res

n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = mat_pow(a, k, MOD)
print(sum([sum(x) for x in b]) % MOD)