Problem:


Score : 600 points

Problem Statement

Given is an integer sequence of length N+1: A_0, A_1, A_2, \ldots, A_N. Is there a binary tree of depth N such that, for each d = 0, 1, \ldots, N, there are exactly A_d leaves at depth d? If such a tree exists, print the maximum possible number of vertices in such a tree; otherwise, print -1.

Notes

A binary tree is a rooted tree such that each vertex has at most two direct children.

A leaf in a binary tree is a vertex with zero children.

The depth of a vertex v in a binary tree is the distance from the tree's root to v. (The root has the depth of 0.)

The depth of a binary tree is the maximum depth of a vertex in the tree.

Constraints

0 \leq N \leq 10^5

0 \leq A_i \leq 10^{8} (0 \leq i \leq N)

A_N \geq 1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 A_2 \cdots A_N

Output

Print the answer as an integer.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

Below is the tree with the maximum possible number of vertices. It has seven vertices, so we should print 7.

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

10
0 0 1 1 2 3 5 8 13 21 34

Sample Output 5

264



Sample input:
3
0 1 1 2


Sample output:
7

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    N = int(input().strip())
    A = list(map(int, input().strip().split(" ")))



    if A[0] != 1 and len(A) == 1:
        print(-1)

    tree = [0] * (sum([2 ** i for i in range(N + 1)]))
    for i, a in enumerate(A[::-1]):
        depth = len(A) - 1 - i
        depth_hierarchy_start_index = sum([2 ** i for i in range(depth)]) if depth != 0 else 0
        depth_hierarchy_end_index = sum([2 ** i for i in range(depth + 1)]) if depth != 0 else 1

        # keisho
        if depth != N:
            for i in range(depth_hierarchy_start_index, depth_hierarchy_end_index):
                if tree[2 * i + 1] != 0 or tree[2 * i + 2] != 0:
                    tree[i] = 2

        # 1 ume
        count = 0
        part = 2
        while True:
            for i in range(0, 2 ** depth, int(2 ** depth / part) if int(2 ** depth / part) >= 1 else 1):
                if tree[depth_hierarchy_start_index + i] == 0:
                    tree[depth_hierarchy_start_index + i] = 1
                    count += 1
                if count == a:
                    break
            part *= 2
            if count == a:
                break
            if int(2 ** depth / part) < 1 and count < a:
                print(-1)
                break


    if not int(2 ** depth / part) < 1 and not  count < a:
        print(sum([1 if i != 0 else 0 for i in tree]))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


class Solver:
    def __init__(self, depth_list):
        self.ans = -1
        self.depth_list = depth_list

    @lru_cache(None)
    def helper(self, d, current_sum, min_nodes, max_nodes):
        if d == 0:
            if min_nodes == 1:
                self.ans = max(self.ans, current_sum+1)
                return
            else:
                return
        else:
            max_size = 2 ** d
            # if number of leaf is grater than the size of max nodes for the layer
            if min_nodes > max_size:
                return
            for c in range(min_nodes, max_nodes):
                if c > max_size:
                    continue
                min_nodes = (c // 2) + (c % 2) + self.depth_list[d - 1]
                max_nodes = c + self.depth_list[d - 1]+1
                self.helper(d-1, current_sum+c, min_nodes, max_nodes)


def main():
    N = int(input().strip())
    depth_list = [int(i) for i in input().strip().split()]
    solver = Solver(depth_list)
    solver.helper(N, 0, depth_list[-1], depth_list[-1]+1)

    return solver.ans

if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

Solution code:
n = int(input)
al = list(map(int, input().split()))
print(-1)

Submission status: Runtime Error

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
asc = [0] * (n + 1)
desc = [0] * (n + 1)
asc[0] = 1
desc[-1] = a_list[-1]
sum = 0

for i in range(n):
    asc[i + 1] = (asc[i] -a_list[i]) * 2
    desc[n - 1 - i] = desc[n - i] + a_list[n - 1 - i]

    if asc[i + 1] <= a_list[i + 1]
        print(-1)
        exit()

for i in range(n + 1):
    sum += min(asc[i], desc[i])

print(sum)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))

f = 0
if a[0] != 0:
    f = 1
else:
    l = [1]
    for  i in range(n-1):
        v = 2*l[i]-a[i+1]
        if v<=0:
            f = 1
            break
        l.append(v)
    w = a
    for i in range(n-1):
        if w[-(i+1)]+a[-(i+2)]<=l[-(i+1)]:
            w[-(i+2)] = w[-(i+1)]+a[-(i+2)]
        else:
            w[-(i + 2)] = l[-(i+1)]+a[-(i+2)]
if f == 1:
    print(-1)
else:
    ans = 0
    for i in w:
        ans += i
    print(ans+1)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    N = int(input().strip())
    A = list(map(int, input().strip().split(" ")))

    # N =10
    # A = list(map(int, "0 0 1 1 2 3 5 8 13 21 34".strip().split(" ")))


    if A[0] != 1 and len(A) == 1:
        print(-1)

    tree = [0] * (sum([2 ** i for i in range(N + 1)]))
    for i, a in enumerate(A[::-1]):
        depth = len(A) - 1 - i
        depth_hierarchy_start_index = sum([2 ** i for i in range(depth)]) if depth != 0 else 0
        depth_hierarchy_end_index = sum([2 ** i for i in range(depth + 1)]) if depth != 0 else 1

        # keisho
        if depth != N:
            for i in range(depth_hierarchy_start_index, depth_hierarchy_end_index):
                if tree[2 * i + 1] != 0 or tree[2 * i + 2] != 0:
                    tree[i] = 2

        # 1 ume
        count = 0
        part = 2
        while True:
            for i in range(0, 2 ** depth, int(2 ** depth / part) if int(2 ** depth / part) >= 1 else 1):
                if tree[depth_hierarchy_start_index + i] == 0:
                    tree[depth_hierarchy_start_index + i] = 1
                    count += 1
                if count == a:
                    break
            part *= 2
            if count == a:
                break
            if int(2 ** depth / part) < 1 and count < a:
                print(-1)
                exit()


    print(sum([1 if i != 0 else 0 for i in tree]))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
cir = 0
sum = 0
hantei=0

lis = [1]
for i in range(n):
    cc = lis[-1] - a[i]
    cc *=2
    if cc<=0:
        hantei=1
    lis.append(cc)

p#rint(lis)



for i in range(n+1):
    tmp = a[-1-i]+cir
    sum += tmp
    #print(tmp,cir)
    if i==n:
        break
    if tmp <= lis[-1-i] and tmp+a[-2-i]>lis[-2-i]:
        if tmp%2==0:
            cir = tmp//2
        else:
            cir = tmp//2+1
    else:
        cir = tmp
if hantei==1:
    print(-1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1
    if N == 0:
        if A == [0]:
            print('-1')
        elif A == [1]:
            print('1')
        else:
            print('-1')
        return
    if N == 1:
        if A == [0, 1]:
            print('2')
        elif A == [0, 2]:
            print('3')
        else:
            print('-1')
        return

    for d in range(1, N):
        f[d] = 2 * min(f[d - 1], count) - A[d] + min(max(f[d - 1] - count, 0), f[d - 1])
        count -= min(f[d - 1], count)
        if f[d] <= 0:
            print('-1')
            return
    print(sum(f) + sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
import numpy as np
from heapq import heapify, heappop, heappush
import copy
from math import gcd, ceil
from collections import deque
# queueとして使う場合 push, popleftを使う
from bisect import bisect_left, bisect_right
# bisect_left: 配列の順序関係が崩れない条件で挿入することができる一番左の点
# bisect_right: 配列の順序関係が崩れない条件で挿入することができる一番右の点
# A = [1, 1, 1, 2, 2, 2, 4]
# print(bisect_left(A, 2))  # 3
# print(bisect_right(A, 2))  # 6
# print(bisect_left(A, 3))  # 6
# print(bisect_right(A, 3))  # 6


def main():
    N = int(input())
    A = [int(c) for c in input().split()]

    if N == 0:
        if A[0] == 1:
            print(1)
        else:
            print(-1)
    elif A[0] == 1:
        print(-1)
        sys.exit()
    now = 0
    p = 1
    num = 1
    while(N > now):
        max_ = sum(A[now+2:])
        c = A[now + 1]
        p = min(max_, p * 2 - c)
        if p < 0:
            print(-1)
            sys.exit()
        num += p + c
        now += 1
    if c != A[-1]:
        # 最後の子
        print(-1)
        sys.exit()
    print(num - p)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==1:
  if a==[0,1]:
    print(2)
  elif a==[0,2]:
    print(3)
  else:
    print(-1)
  exit()
subt=[0]*(n)
if a[0] == 0:
  subt[0]=2
elif a[0]== 1:
  subt[0]=1
else:
  print(-1)
  exit()

for i in range(n-1):
  if a[i+1] > subt[i]-1:
    if i<n-1:
      print(-1)
      exit()
    elif a[i+1] > subt[i]:
      print(-1)
      exit()
  else:  
    subt[i+1]=(subt[i]-a[i+1])*2
if a[n]> subt[-1]:
  print(-1)
  exit()
if a[n] > subt[-2]:
  subt[-1]=a[n]
else:
  subt[-1]=a[n]
  for j in range(2,n):
    if (subt[-j]-a[-j])*2 < subt[1-j]:
      print(-1)
      exit()
    if (subt[-j]-a[-j]) <= subt[1-j]:
      pass
    else:
      subt[-j]=subt[1-j]+a[-j]
print(sum(subt)+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()

max_a = [0] * (N+1)

max_a[0] = 1 - A[0]

for i in range(1, N+1):
    max_a[i] = max_a[i-1] * 2 - A[i]
    if max_a[i] < 0:
        print(-1)
        exit()

num = [0]*(N)
cnt = 0
tmp = A[-1]
for i in reversed(range(N)):

    if tmp <= max_a[i]:
        cnt += tmp
    else:
        cnt += max_a[i]
        tmp = max_a[i]

cnt += sum(A)

print(cnt+A[-2])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1
    if N == 0:
        if not A == [0]:
            print('-1')
            return
        else:
            print('1')
            return
    if N == 1:
        if A == [0, 1]:
            print('2')
        elif A == [0, 2]:
            print('3')
        else:
            print('-1')

    for d in range(1, N):
        f[d] = 2 * min(f[d - 1], count) - A[d] + min(max(f[d - 1] - count, 0), f[d - 1])
        count -= min(f[d - 1], count)
        if f[d] <= 0:
            print('-1')
            return
    print(sum(f) + sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# C

N = int(input())
A_N = list(map(int, input().split()))
reversed_A_N = list(reversed(A_N))

print(A_N[1])

for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]
 
r_reversed_A_N = list(reversed(reversed_A_N))
 
 
r_reversed_A_N[0] = 1
for i in range(N):
    max_next_nodes = (r_reversed_A_N[i] - A_N[i]) * 2 - A_N[i+1]
    if max_next_nodes < 0:
      print(-1)
      exit()
    elif max_next_nodes >= r_reversed_A_N[i+1]:
        break
    else:
        r_reversed_A_N[i+1] = max_next_nodes + A_N[i+1]
 
r_reversed_A_N[-1] = A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Runtime Error

Solution code:
cur = 1
ans = 1
n = int(input())
b = input()
b = b.split(" ")
a = []
for i in b:
	a.append(int(i))
flag = 1
for i in range(n):
	if cur <= a[i]:
		flag = 0
		print(-1)
		break
	cur = cur - a[i]
	temp = cur
	cur = cur * 2
	ans = ans + cur
if flag:
	ans = ans - cur + a[n]
	if a[n] < temp:
		extra = temp - a[n]
		while i >= 0:
			ans = ans - extra
			extra = extra - a[i] - a[i + 1];
			if extra < 0:
				break
			extra = extra // 2
			i = i - 1
	print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(50000)

depth = int(input()) 
leaves = list(map(int, input().split(" ")))
limited = []

def find( i, depth, cur) :
    if i == depth :
        limited.append(leaves[i])
        return ( leaves[i], (leaves[i]+1)//2 )
    _max, _min = find(i+1, depth, (cur-leaves[i])*2 )
    _max = min(cur, _max+leaves[i])
    _min += leaves[i]
    if _max < _min :
        return (-float('inf'), float('inf') )
    limited.append(_max)
    return ( _max, (_min+1)//2 )

find(0, depth, 1) 
if len(limited) != depth+1 :
    print(-1)
else :
    print(sum(limited))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1
    if N == 0:
        if not A == [1]:
            print('-1')
            return
        else:
            print('1')
            return
    if N == 1:
        if not A == [0, 1]:
            print('-1')
            return
        else:
            print(2)
            return


    for d in range(1, N):
        f[d] = 2 * min(f[d-1], count) - A[d] + min(max(f[d-1]-count, 0), f[d-1])
        count -= min(f[d-1], count)
        if f[d] <= 0:
            print('-1')
            return
    print(sum(f)+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(12000)

depth = int(input()) 
leaves = list(map(int, input().split(" ")))
limited = []

def find( i, depth, cur) :
    if i == depth :
        limited.append(leaves[i])
        return ( leaves[i], (leaves[i]+1)//2 )
    _max, _min = find(i+1, depth, (cur-leaves[i])*2 )
    _max = min(cur, _max+leaves[i])
    _min += leaves[i]
    if _max < _min :
        return (-float('inf'), float('inf') )
    limited.append(_max)
    return ( _max, (_min+1)//2 )

find(0, depth, 1) 
if len(limited) != depth+1 :
    print(-1)
else :
    print(sum(limited))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1

    if sum(A) == 1:
        print(N+1)

    if N == 1:
        if not A == [0, 1]:
            print('-1')
            return
        else:
            print(2)
            return


    for d in range(1, N):
        f[d] = 2 * min(f[d-1], count) - A[d] + min(max(f[d-1]-count, 0), f[d-1])
        count -= min(f[d-1], count)
        if f[d] <= 0:
            print('-1')
            return
    print(sum(f)+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def power(n,p,m):
    if p == 0:
        return 1
    elif p%2:
        return (power(n,p-1,m)*n)%m
    else:
        return ((power(n,p//2,m))**2)%m
 
n,m,p = map(int,input().split())
print(power(n,p,m))

Submission status: Runtime Error

Solution code:
depth = int(input()) 
leaves = list(map(int, input().split(" ")))
limited = []
def find( i, depth, cur) :
    if i == depth :
        limited.append(leaves[i])
        return ( leaves[i], (leaves[i]+1)//2 )
    _max, _min = find(i+1, depth, (cur-leaves[i])*2 )
    _max = min(cur, _max+leaves[i])
    _min += leaves[i]
    if _max < _min :
        return (-float('inf'), float('inf') )
    limited.append(_max)
    return ( _max, (_min+1)//2 )

find(0, depth, 1) 
if len(limited) != depth+1 :
    print(-1)
else :
    print(sum(limited))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
P = [2**i for i in range(len(A))]

# A = A[::-1]
# P = P[::-1]

# ans = 0
# node = 0
# for i in range(len(A)-1):
#     node = node + A[i]
#     node = min(node,2 * (P[i+1] - A[i+1]))
#     ans += node
#     if node <= 0:
#         print (-1)
#         exit()
#     print (node)
    
# ans += 1
# print (ans)

if A[0] > 0:
    print(-1)
    exit()
if A[-1] >= 2**N:
    print (-1)
    exit()

ans = [0]
node = [0]
def rec(i):
    if i==0:
        ans[0]+=1
        return 1
    node[0] = node[0] + A[i]
    node[0] = min(node[0], 2*rec(i-1))
    ans[0] += node[0]
    #print (node[0],node[0]-A[i])
    if i!=N and node[0] - A[i] <= 0:
        print(-1)
        exit()
    return node[0] - A[i]
rec(N)
print (ans[0])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1

    if N == 1:
        if not A == [0, 1]:
            print('-1')
            return
        else:
            print(2)
            return


    for d in range(1, N):
        f[d] = 2 * min(f[d-1], count) - A[d] + min(max(f[d-1]-count, 0), f[d-1])
        count -= min(f[d-1], count)
        if f[d] <= 0:
            print('-1')
            return
    print(sum(f)+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a_li = list(map(int, input().split()))
muri = False
cnt = 0
for i in range(n, -1, -1):
    cnt = np.ceil(cnt/2) + a_li[i]
    if cnt > 2**i:
        muri = True
        break
if muri:
    print(-1)
else:
    cnt = 1
    node = 1
    las = a_li[-1]
    if n==0:
        print(1)
    else:
        for i in range(1, n):
            node = min(node*2-a_li[i], sum(a_li[i+1:]))
            cnt += node + a_li[i]
        print(cnt+las)

Submission status: Runtime Error

Solution code:
import math

def find_max_verticies(A, i, verticies, prev_verticies):
	#print(i, verticies, prev_verticies)
	max_leaves = 2**i
	a = A[i]
	if a > max_leaves:
		return -1
	if i == 0:
		if a != 0:
			return -1
		return verticies + 1
	if i == N:
		return find_max_verticies(A, i-1, a, a)
	else:
		if prev_verticies <= 0:
			return -1
		min_nonleaf = math.ceil(prev_verticies/2)
		max_nonleaf = min(prev_verticies, max_leaves - a)
		if min_nonleaf + a > max_leaves:
			return -1
		for j in reversed(range(min_nonleaf, max_nonleaf+1)):
			v = find_max_verticies(A, i-1, verticies + j + a, j + a)			
			if v > 0:
				return v
		return -1


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

print(find_max_verticies(A, N, 0, 0))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
saidaiA =[]
oya = 1/2
flag = True
for i in range(len(A)):
    ko = oya *2
    oya = ko - A[i]
    saidaiA.append(int(ko))
    # print("i=",i)
    # print("ko =",ko)
    # print("oya =",oya)
    if oya < 0:
        flag = False
ans = 0
# print(saidaiA)
motikosi = 0
for i in range(len(A)):
    if A[-i] + motikosi >= saidaiA[-i]:
        ans += saidaiA[-i]
        motikosi = saidaiA[-i]
    else:
        ans += A[-i] + motikosi
        motikosi = A[-i] + motikosi
if flag == True:
    print(int(ans)+1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
a=1
k=0
f=0
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if a<=0:
    f+=1
    break
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
if f==0 and n!=0 and n!=1:
  print(sum(g))
elif n==0 or n==1:
  print(len[l])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1

    if N == 1:
        if not A == [0, 1]:
            print('-1')
            return
        else:
            print(2)
            return


    for d in range(1, N):
        f[d] = 2 * min(f[d-1], count) - A[d] + min(max(f[d-1]-count, 0), f[d-1])
        count -= min(f[d-1], count)
        if f[d] < 0:
            print('-1')
            return
    print(sum(f)+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
a=1
k=0
f=0
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if a<=0:
    f+=1
    break
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  print(len[l])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
# C

N = int(input())
A_N = list(map(int, input().split()))
reversed_A_N = list(reversed(A_N))

for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]

r_reversed_A_N = list(reversed(reversed_A_N))

r_reversed_A_N[0] = 1
for i in range(N):
    max_next_nodes = (r_reversed_A_N[i] - A_N[i]) * 2 - A_N[i+1]
    if max_next_nodes < 0:
      print(-1)
      exit()
    elif max_next_nodes >= r_reversed_A_N[i+1]:
        break
    else:
        r_reversed_A_N[i+1] = max_next_nodes + A_N[i+1]

r_reversed_A_N[i] = list(reversed(reversed_A_N))[i]# A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1

    if N == 1:
        if not A == [0, 1]:
            print('-1')
            return
        else:
            print(2)


    for d in range(1, N):
        f[d] = 2 * min(f[d-1], count) - A[d] + min(max(f[d-1]-count, 0), f[d-1])
        count -= min(f[d-1], count)
        if f[d] < 0:
            print('-1')
            return
    print(sum(f)+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    N = int(input().strip())
    A = list(map(int, input().strip().split(" ")))


    if A[0] != 1 and len(A) == 1:
        print(-1)

    tree = [0] * (sum([2 ** i for i in range(N + 1)]))
    for i, a in enumerate(A[::-1]):
        depth = len(A) - 1 - i
        depth_hierarchy_start_index = sum([2 ** i for i in range(depth)]) if depth != 0 else 0
        depth_hierarchy_end_index = sum([2 ** i for i in range(depth + 1)]) if depth != 0 else 1

        # keisho
        if depth != N:
            for i in range(depth_hierarchy_start_index, depth_hierarchy_end_index):
                if tree[2 * i + 1] != 0 or tree[2 * i + 2] != 0:
                    tree[i] = 2

        # 1 ume
        count = 0
        part = 2
        while True:
            try:
                for i in range(0, 2 ** depth, int(2 ** depth / part) if int(2 ** depth / part) != 0 else 1):
                    if tree[depth_hierarchy_start_index + i] == 0:
                        tree[depth_hierarchy_start_index + i] = 1
                        count += 1
                    if count == a:
                        break
                    part *= 2
                if count == a:
                    break
            except:
                print(-1)

    print(sum([1 if i != 0 else 0 for i in tree]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1

    if N == 1:
        if not A == [0, 1]:
            print('-1')
            return

    for d in range(1, N):
        f[d] = 2 * min(f[d-1], count) - A[d] + min(max(f[d-1]-count, 0), f[d-1])
        count -= min(f[d-1], count)
        if f[d] < 0:
            print('-1')
            return
    print(sum(f)+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

def find_max_verticies(A, i, verticies, prev_verticies):
	#print(i, verticies, prev_verticies)
	max_leaves = 2**i
	a = A[i]
	if a > max_leaves:
		return -1
	if i == 0:
		if a != 0:
			return -1
		return verticies + 1
	if i == N:
		return find_max_verticies(A, i-1, a, a)
	else:
		min_nonleaf = math.ceil(prev_verticies/2)
		max_nonleaf = min(prev_verticies, max_leaves - a)
		if min_nonleaf + a > max_leaves:
			return -1
		for j in reversed(range(min_nonleaf, max_nonleaf+1)):
			v = find_max_verticies(A, i-1, verticies + j + a, j + a)			
			if v > 0:
				return v
		return -1


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

print(find_max_verticies(A, N, 0, 0))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0:
	if a[0]==1:
		print(2/0)
		exit()
	else:
		while True:
			print(98236874184)
M=[1]
now=2
for i in range(n):
	M.append(now)
	now-=a[i+1]
	if now<=10**29:
		now*=2
now=a[-1]
for i in range(n):
	M[-i-1]=min(now,M[-i-1])
	now=min(now,M[-i-1])
	now+=a[-i-2]
if a[0]!=0:
	print(-1)
	exit()
for i in range(n+1):
	if M[i]<=0:
		print(-1)
		exit()
print(sum(M))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1
    upper = sum([2 ** i for i in range(N)])

    if N == 1:
        if not A == [0, 1]:
            print('-1')
            return

    for d in range(1, N):
        f[d] = 2 * min(f[d-1], count) - A[d] + min(max(f[d-1]-count, 0), f[d-1])
        count -= min(f[d-1], count)
        if f[d] < 0:
            print('-1')
            return
    print(sum(f)+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin

"""def main(N,ls):
    d = []
    d.append([1,1])
    for i in range(1,N+1):#iでふかさiの求められる最小の個数と最大の個数を出してく
        a = ls[i]
        fco = d[i-1]
        mx = fco[1]*2 - a
        mn = fco[0] -a
        d.append([mn,mx])"""
result = []
def dfs(r,tn,fc):
    if r == N:
        if fc == ls[N]:
            result.append(tn)
    else:
        a = ls[r]
        mx = fc*2 - a*2
        mn = max(1,fc -a)
        for j in range(mn,mx+1):
            dfs(r+1,tn+j,j)#


N = int(input())
ls = list(map(int, stdin.readline().split()))

dfs(0,1,1)
if len(result) == 0:
    print(-1)
else:
    print(max(result))

Submission status: Runtime Error

Solution code:
input())
a=list(map(int,input().split()))
ok=True

v=[0 for i in range(n+2)]
import time

#start=time.time()
nextv=0

nec=2**n

for i in range(n,-1,-1):

    if nec>=v[i+1]+a[i]:
        v[i]=v[i+1]+a[i]
    else:
        v[i]=nec

    nec=nec >>1



#print(time.time()-start)

for i in range(1,n+1):
    if v[i-1]-a[i-1]<0:
        ok=False
        break
    if (v[i-1]-a[i-1])*2<v[i]:
        v[i]=(v[i-1]-a[i-1])*2

if a[0]!=0:ok=False

ans=sum(v)

if ans==0:ok=False

if ok:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
p=[0]
a=1
k=0
f=0
if n==0:
  print(p(0))
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if a<=0:
    f+=1
    break
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  print(l[0])
else:
  print(-1)