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:
n = int(input())
A = list(map(int,input().split()))

b = 1
B=[0]*(n+1)
count = 0
for i in range(n):
    B[i] = b
    if 2*(b - A[i]) < A[i+1]:
        count += 1
    b = 2*(b - A[i])

B[n] = b

j = 0
while A[n] > B[j]:
    j+=1

total = 0
for i in range(j):
    total += B[i]

s = A[n]
for i in range(n-1,j-1,-1):
    total += min(B[i],s+A[i])
    s+=A[i]

if count==0:
    print(total+A[n])
else:
    print('-1')

Submission status: Runtime Error

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

b = 1
B=[0]*(n+1)
count = 0
for i in range(n):
    B[i] = b
    if 2*(b - A[i]) < A[i+1]:
        count += 1
    b = 2*(b - A[i])

B[n] = b

j = 0
while A[n] > B[j]:
    j+=1
    print(j,A[n],B[j])

total = 0
for i in range(j):
    total += B[i]

print(total)
s = A[n]
for i in range(n-1,j-1,-1):
    total += min(B[i],s+A[i])
    print(B[i],s+A[i])
    s+=A[i]

if count==0:
    print(total+A[n])
else:
    print('-1')

Submission status: Runtime Error

Solution code:
N = int(input())
    A = list(map(int, input().split()))
    s = [0] * (N + 2)
    for i in range(N + 1):
        s[i + 1] = s[i] + A[i]
    node, leaf = 1, 1
    for d in range(1, N + 1):
        if leaf < A[d]:
            print(-1)
            break
        leaf = min((leaf - A[d - 1]) * 2, s[N + 1] - s[d])
        if leaf < A[d]:
            print(-1)
            break
        node += leaf
    else:
        print(node)

Submission status: Runtime Error

Solution code:
import math

N = int(input())
A = list(map(int,input().split()))
rangelist = [[]]*(N+1)
rangelist[N] = [A[N],A[N]]
for n in range(N-1,-1,-1):
    rangelist[n] = [math.ceil(rangelist[n+1][0]/2) + A[n], rangelist[n+1][1] + A[n]]
total = 0
noderayor = 1
for n in range(N+1):
    num = 2**n
    if num < rangelist[n][0]:
        print(-1)
        exit()
    noderayor = min(rangelist[n][1], min(num,upper*2))
    total += noderayor
    upper = noderayor - A[n]
print(total)

Submission status: Runtime Error

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

B = []

if N == 0:
    if A[0] != 1:
        print(-1)
        exit()
    else:
        print(1)
        exit()

else:
    if A[0] != 0:
        print(-1)
        exit()
    else:
        B.append(1)
        for i in range(1, N + 1):
            B.append((B[i - 1] - A[i - 1]) * 2)
            if (A[i] > B[i] or (A[i] == B[i] and i != N)):
                print(-1)
                exit()

        ans = 0
        ans += A[N]
        B[N] = A[N]
        for i in range(N, -1, -1):
            ans += min(B[i], B[i + 1] + A[i])
            B[i] = min(B[i], B[i + 1] + A[i])

        print(ans)
        exit()

Submission status: Runtime Error

Solution code:
n = int(input())
a = map(int, input().split())
s = sum(a)
k = 1 - a[0]
ans = 1

for i in range(1,n+1):
  if k*2 <= s:
    k *= 2
  else:
    k = s
  ans += k
  k -= a[i]
  s -= a[i]

if k == 0 and s == 0:
  print(ans)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[int], nb: int) -> int:
    possible = dfs(values, nb, values[-1], values[-1])
    if possible is None:
        return -1
    return possible


def dfs(
    values: List[int], depth: int, cur_nodes: int, cur_leaves: int
) -> Optional[int]:
    if pow(2, depth) < values[depth] or cur_leaves != values[depth]:
        return None
    if depth == 0:
        return 1
    min_parents = math.ceil(cur_nodes / 2)
    max_parents = cur_nodes
    for next_nodes in range(
        min(pow(2, depth - 1), cur_nodes + values[depth - 1]), min_parents - 1, -1,
    ):
        for parents in range(min_parents, max_parents + 1):
            possible = dfs(values, depth - 1, next_nodes, next_nodes - parents)
            if possible is not None:
                return cur_nodes + possible
    return None


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(stdin.readline().strip())
    values = list(map(int, stdin.readline().split()))
    # values = []
    # for _ in range(N):
    #     values.append(stdin.readline().split())
    result = solve(values, N)
    print(result, file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    # pylint: disable=super-init-not-called
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Submission status: Runtime Error

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [1] * (N)
    B.append(0)
    sumA = sum(A)
    ans = 0

    if N == 0 and A[0] != 1:
        print(-1)
        return
    
    for i in range(1,N):
        sumA -= A[i]
        B[i] = min(2 * B[i-1] - A[i], sumA)
        if B[i] < 0:
            print(-1)
            return

    print(sum(A,B))

if __name__ == "__main__":
    main()

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)
        l = [1]+l
    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:
            if l[-(i+2)]<=l[-(i+1)]+a[-(i+2)]<= l[-(i+2)]*2 :
                w[-(i + 2)] = l[-(i + 1)] + a[-(i + 2)]
            else:

                flag = 1
                break
if f == 1:
    print(-1)
else:
    ans = 0
    for i in w:
        ans += i
    print(ans+1)

Submission status: Runtime Error

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



f = 0
if a[0] != 0:
    f = 1
else:
    l = [1,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:
            if l[-(i+2)]<=l[-(i+1)]+a[-(i+2)]<= l[-(i+2)]*2 :
                w[-(i + 2)] = l[-(i + 1)] + a[-(i + 2)]
            else:

                flag = 1
                break
if f == 1:
    print(-1)
else:
    ans = 0
    for i in w:
        ans += i
    print(ans+1)

Submission status: Runtime Error

Solution code:
l

Submission status: Runtime Error

Solution code:
N = int(input())
arr = list(map(int, input().split()))
for i in range(min(N,30)):
    if arr[i] > 2**i:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    if (ans[i-1]-arr[i-1])*2 <= sum_arr[i-1]:
        tmp = (ans[i-1]-arr[i-1])*2
    else:
        tmp = sum_arr[i-1]
    ans[i] = tmp
print(sum(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
arr = list(map(int, input().split()))
for i in range(min(N,25)):
    if arr[i] > 2**i:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    if (ans[i-1]-arr[i-1])*2 <= sum_arr[i-1]:
        tmp = (ans[i-1]-arr[i-1])*2
    else:
        tmp = sum_arr[i-1]
    ans[i] = tmp
print(sum(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
arr = list(map(int, input().split()))
for i in range(min(N,25)):
    if arr[i] > 2**i:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    if (ans[i-1]-arr[i-1])*2 <= sum_arr[i-1]:
        tmp = (ans[i-1]-arr[i-1])*2
    else:
        tmp = sum_arr[i-1]
    ans[i] = tmp
print(ans)

Submission status: Runtime Error

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [1] * N
    sumA = sum(A)

    if N == 0 and a[0] != 1:
        print(-1)
        return
    
    for i in range(1,N):
        sumA = sumA - A[i]
        B[i] = min(2 * B[i-1] - A[i], sumA)
    
    print(sum(A + B))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def dfs(i,pre,n,a,ans):
    if (pre*2 < a[i]): return -1
    ans[i] += a[i]
    if (i == n):
        return a[i]

    pre = pre*2 - a[i]
    u = dfs(i+1,pre,n,a,ans);
    if (u<0 or pre*2 < u): return -1;
    ans[i] += min(pre, u)
    return min(pre, u) + a[i]



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

if (n == 0):
    if (a[0] == 0):
        print(-1)
    else:
        print(1)
    exit()

ans = [1] + [0]*n
u = dfs(1,1,n,a,ans)
if (n!=0 and a[0] != 0): u = -1

if (u >= 0):
    print(sum(ans))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
# read = sys.stdin.buffer.read
# readline = sys.stdin.buffer.readline
# readlines = sys.stdin.buffer.readlines
input = sys.stdin.readline


def culcedge(edge, depth):
    newedge = edge.copy()
    can = newedge[depth-1]-leaf[depth-1]
    ans = -1
    for i in range(can+1):
        newedge[depth] = can+i
        if depth == N:
            if newedge[N] == leaf[N]:
                return sum(newedge)
            return -1
        ans = max(ans, culcedge(newedge, depth+1))
    return ans


N = int(input())
leaf = list(map(int, input().split(" ")))
edge = [0]*(N+1)
edge[0] = 1
ans = -1

ans = culcedge(edge, 1)
print(ans)

Submission status: Runtime Error

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

ans = 0
if A[0] >= 1:
    ans = -1
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
else:
    node_num = {N: A[N]}
    max_parent_num = {0: 1}
    for i in range(1, N+1):
        max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]

    for i in range(N, 0, -1):
        if node_num[i] > min(2**i, A[i] + max_parent_num[i]):
            ans = -1
            break
        #i-1 no parent wo tukuru
        if node_num[i] <= max_parent_num[i-1]:
            i_1_parent_num = node_num[i]
        else:
            i_1_parent_num = max_parent_num[i-1]
        node_num[i-1] = i_1_parent_num + A[i-1]
    if node_num[0] > min(1, A[0] + max_parent_num[0]):
        ans = -1

if ans == -1 or ans == 1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
li=list(map(int,input().split()))
tree=[0]*(n+1)
tree[n]=li[n]
for i in range(n-1,-1,-1):
    tree[i]=min(2**i,tree[i+1]+li[i])

s=tree[1]
for i in range(0,n):
    if (tree[i] - li[i]) * 2 <=0:
        print(-1)
        exit()
    elif (tree[i]-li[i])*2<tree[i+1]:
        tree[i+1]=(tree[i]-li[i])*2
print(sum(tree))

Submission status: Runtime Error

Solution code:
N = int(input())
a_list = [int(a) for a in input().split()]

if a[0] > 1:
    print(-1)
    exit()

ans = a_list[-1] + 1
temp1 = [""]*(N+1)
temp1[-1] = a_list[-1]
for n in range(N-1, 0, -1):
    temp1[n] = temp1[n+1]+a_list[n]
    
temp2 = 1
for n in range(1, N):
    temp2 = (temp2-a_list[n-1])*2
    ans_temp = min(temp2, temp1[n])
    
    if ans_temp < a_list[n]:
        print(-1)
        exit()
    
    ans += ans_temp
    
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
a_list = [int(a) for a in input().split()]

if a[0] > 1:
    print(-1)
    exit()

ans = a_list[-1] + 1
temp1 = [""]*(N+1)
temp1[-1] = a_list[-1]
for n in range(N-1, 0, -1):
    temp1[n] = temp1[n+1]+a_list[n]
    
temp2 = 1
print(temp1)
for n in range(1, N):
    temp2 = (temp2-a_list[n-1])*2
    ans_temp = min(temp2, temp1[n])
    
    if ans_temp < a_list[n]:
        print(-1)
        exit()
    
    ans += ans_temp
    
print(ans)

Submission status: Runtime Error

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

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


#!  方針
#!    1．葉の枚数が可能であるかチェック
#!    2．節の最大数、上から降りて、下から上がる



Fushi=[1]
for i in range(N+1):
  if i==0: continue
  f = Fushi[i-1] * 2
  h = Ha[i]

  a = f-h
  if (a<0) or (a=0 and i==N):
    print(-1)
    exit(0)

  Fushi.append( a )


Fushi[N]=0

#p("H, ",Ha)
#p("F, ", Fushi)


for i in reversed(range(N)):
  #print(i)

  h = Ha[i+1]
  f = Fushi[i+1]

  a = min(Fushi[i], h+f)
  if a<=0:
    print(-1)
    exit(0)

  Fushi[i] = a



#p("F, ", Fushi)
#p("sumH" , sum(Ha))
#p("sumF", sum(Fushi))


ans = sum(Ha) + sum(Fushi)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)

if A[0] >= 1 and N <> 1:
  print(-1)
  exit()

ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Runtime Error

Solution code:
import math, numpy

n = int(input())

a = list(map(int,input().split()))

l = [0] * (n + 1)
l[0] = 1

cumsum_a = numpy.cumsum(a[::-1])[::-1]

if (n > 0) and (a[0] > 0):
    print(-1)
else:
    for i in range(1, n):
        b_max1 = 2 * (l[i - 1] - a[i - 1])
        b_max2 = cumsum_a[i]

        if a[i] > 2 ** i - math.ceil(l[i-1]/2):
            l = -1
            break

        l[i] = min(b_max1, b_max2)

    if l != -1:
        l[-1] = a[-1]
        print(sum(l))
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import math, numpy

n = int(input())

a = list(map(int,input().split()))

l = [0] * n
l[0] = 1

cumsum_a = numpy.cumsum(a[::-1])[::-1]

if (n > 0) and (a[0] > 0):
    print(-1)
else:
    for i in range(1, n):
        b_max1 = 2 * (l[i - 1] - a[i - 1])
        b_max2 = cumsum_a[i]

        if a[i] > 2 ** i - math.ceil(l[i-1]/2):
            l = -1
            break

        l[i] = min(b_max1, b_max2)

    if l != -1:
        l[-1] = a[-1]
        print(sum(l))
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
32.txt

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

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

ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Runtime Error

Solution code:
import math, numpy

n = int(input())

a = list(map(int,input().split()))

l = [1]

cumsum_a = numpy.cumsum(a[::-1])[::-1]

if (n > 0) and (a[0] > 0):
    print(-1)
else:
    for i in range(1, n):
        b_max1 = 2 * (l[i - 1] - a[i - 1])
        b_max2 = cumsum_a[i]

        if a[i] > 2 ** i - math.ceil(l[i-1]/2):
            l = -1
            break

        l.append(min(b_max1, b_max2))

    if l != -1:
        l.append(a[-1])
        print(sum(l))
    else:
        print(-1)

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 self.ans != -1:
            return
        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 reversed(list(range(min_nodes, max_nodes+1))):
                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:
if A[0] >= 1:
  print(-1)
else:
  print(1)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
ma1 = [1]*n
ma2 = [0]*n
mi2 = [0]*n

for i in range(1,n):
    ma1[i]=ma1[i-1]*2-a[i]
    if ma1[i]<0:
        print(-1)
        exit()
if n == 1:
    if a[0]==1:
        print(-1)
        exit()
    if a[0]==0:
        if a[1]==1:
            print(2)
            exit()
        elif a[1]==2:
            print(3)
            exit()
        else:
            print(-1)
            exit()

ma2[n-1]=a[n]
ma2[n-2]=ma2[n-1]
mi2[n-1]=a[n]
mi2[n-2]=mi2[n-1]//2 + mi2[n-1]%2
if n!=2:
    for i in range(2,n):
        ma2[n-1-i]=min(ma2[n-i]+a[n-i+1],2**(n-i)-a[n-i])
        mi2[n-1-i]=(mi2[n-i]+a[n-i+1])//2 + (mi2[n-i]+a[n-i+1])%2
        if mi2[n-1-i]>ma2[n-1-i]:
            print(-1)
            exit()
ma2 = [1]+ma2
ans = 0
for i in range(n):
    ans += min(ma1[i],ma2[i])
ans +=sum(a)

print(ans)

Submission status: Runtime Error

Solution code:
import math

n = int(input())

a = list(map(int,input().split()))

l = [1]

for i in range(1, n):
    b_max1 = 2 * (l[i - 1] - a[i - 1])
    b_max2 = sum(a[i:])

    if a[i] > 2 ** i - math.ceil(l[i-1]/2):
        l = -1
        break

    l.append(min(b_max1, b_max2))

if l != -1:
    l.append(a[-1])
    print(sum(l))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    if n == 0:
        if a[0] == 1:
            print(1)
        else:
            print(-1)
    else:
        for i in range(1, n):
            ans[i] = (ans[i - 1] - a[i - 1]) * 2
        for i in range(n - 1):
            ans[- 2 - i] = min(ans[- 2 - i], ans[- 1 - i] + a[- 2 - i])
        print(sum(ans))

main()

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
if a[0]>0:
    ans=-1
x=0
ans=1
nezen=1
suu=0
su=0
for x in a:
    su+=x
    suu+=x
for x in range(1,n):
    if nezen<0:
        ans=-1
        break
    ha=a[x]
    su-=ha
    ne=(min(su,nezen*2-ha))
    if ne<=0:
        ans=-1
        break
    ans+=ne
    nezen=ne
if ans!=-1:
    ans+=suu
    nezen=ne
    if ne<=0:
        ans=-1
print(ans)

Submission status: Runtime Error

Solution code:
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

numLeafs = A
minNonLeafs = [None for i in range(N + 1)]
maxNonLeafs = [None for i in range(N + 1)]

maxNonLeafs[0] = 1
for i in range(1, N + 1):
    maxNonLeafs[i] = 2 * maxNonLeafs[i - 1] - numLeafs[i]

minNonLeafs[N] = 0
maxNonLeafs[N] = 0
if minNonLeafs[N] + numLeafs[N] > 2 ** N:
    print(-1)
    exit()

for i in range(N - 1, -1, -1):
    minNonLeafs[i] = (minNonLeafs[i + 1] + numLeafs[i + 1] + 1) // 2
    if minNonLeafs[i] + numLeafs[i] > 2 ** i:
        print(-1)
        exit()
    maxNonLeafs[i] = min(maxNonLeafs[i], maxNonLeafs[i + 1] + numLeafs[i + 1])
    if minNonLeafs[i] > maxNonLeafs[i]:
        assert False # TODO: do i need this case?
        print(-1)
        exit()

count = 0
for i in range(N + 1):
    count += maxNonLeafs[i] + numLeafs[i]
print(count)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
if n ==0 :
    htakh
    if a == 2:
        print(2)
    else:
        print(-1)
    sys.exit()
    
back = [0 for _ in range(n+1)]
back[n] = a[n]
for i in range(n-1, -1, -1):
	back[i] = back[i+1] + a[i]

v = [1]
for i in range(n):
    #print(v[-1],a[i])
    k = min((v[-1]-a[i])*2,back[i+1])
    if k<=0:
        print(-1)
        sys.exit()
    v.append(k)
print(sum(v))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
ma1 = [1]*n
ma2 = [0]*n
mi2 = [0]*n

for i in range(1,n):
    ma1[i]=ma1[i-1]*2-a[i]
    if ma1[i]<0:
        print(-1)
        exit()
if n == 1:
    if a[0]==1:
        print(-1)
        exit()
    if a[0]==0:
        if a[1]==1:
            print(2)
            exit()
        elif a[1]==2:
            print(3)
            exit()
        else:
            print(-1)
            exit()


ma2[n-1]=a[n]
ma2[n-2]=ma2[n-1]
mi2[n-1]=a[n]
mi2[n-2]=mi2[n-1]//2 + mi2[n-1]%2
for i in range(2,n):
    ma2[n-1-i]=min(ma2[n-i]+a[n-i+1],2**(n-i)-a[n-i])
    mi2[n-1-i]=(mi2[n-i]+a[n-i+1])//2 + (mi2[n-i]+a[n-i+1])%2
    if mi2[n-1-i]>ma2[n-1-i]:
        print(-1)
        exit()
ma2 = [1]+ma2
ans = 0
for i in range(n):
    ans += min(ma1[i],ma2[i])
ans +=sum(a)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
if n == 1:
    htakh
    if a == 2:
        print(2)
    else:
        print(-1)
    sys.exit()
    
back = [0 for _ in range(n+1)]
back[n] = a[n]
for i in range(n-1, -1, -1):
	back[i] = back[i+1] + a[i]

v = [1]
for i in range(n):
    #print(v[-1],a[i])
    k = min((v[-1]-a[i])*2,back[i+1])
    if k<=0:
        print(-1)
        sys.exit()
    v.append(k)
print(sum(v))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
if a[0]>0:
    ans=-1
x=0
ans=1
nezen=1
suu=0
su=0
for x in a:
    su+=x
    suu+=x
for x in range(1,n):
    if nezen<0:
        ans=-1
        break
    ha=a[x]
    su-=ha
    ne=(min(su,nezen*2-ha))
    ans+=ne
    nezen=ne
if ans!=-1:
    ans+=suu
    nezen=ne
    if ne<=0:
        ans=-1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

a = list(map(int,input().split()))

l = [1]

for i in range(1, n):
    b_max1 = 2 * (l[i - 1] - a[i - 1])
    b_max2 = sum(a[i:])

    if b_max1 <= 0:
        l = -1

    l.append(min(b_max1, b_max2))

l.append(a[-1])

print(sum(l))

Submission status: Runtime Error

Solution code:
n = int(input())

a = list(map(int,input().split()))

l = [1]

for i in range(1, n):
    b_max1 = 2 * (l[i - 1] - a[i - 1])
    b_max2 = sum(a[i:])

    if b_max1 <= 0:
        l = -1

    print(a[i + 1:])

    print(i, b_max1, b_max2)

    l.append(min(b_max1, b_max2))

l.append(a[-1])

print(sum(l))

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:
            if l[-(i+2)]<l[-(i+1)]+a[-(i+2)]<= l[-(i+2)]*2:
                w[-(i + 2)] = l[-(i + 1)] + a[-(i + 2)]
            else:

                flag = 1
                break
if f == 1:
    print(-1)
else:
    ans = 0
    for i in w:
        ans += i
    print(ans+1)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input.split()))
 
def solve(N, A):
	if not A or A[0] != 1:
      print(-1)
      return
 
    prev = 1
    rt = 1
    for a in A[1:]:
        if a > prev * 2:
          print(-1)
          return
        rt += (prev * 2 - a) % (prev * 2)
        prev = a

    print(rt)
    
solve(N, A)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input.split()))
 
def solve(N, A):
  if not A or A[0] != 1:
    print(-1)
    return
 
  prev = 1
  rt = 1
  for a in A[1:]:
    if a > prev * 2:
      print(-1)
      return
    rt += (prev * 2 - a) % (prev * 2)
    prev = a
 
  print(rt)
 
solve(N, A)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())))
l = 0
n = 1
b = 0
g = np.zeros(N+1, dtype=np.uint64)
g[0] = 1-a[0]
for i in range(1, N+1):
    g[i] = (g[i-1]-a[i-1])*2
    if g[i] <= 0:
        l = -1
g[N] = a[N]
for i in range(1, N+1):
    if l<0:
        break
    b = N-i
    if g[b] > g[b+1]+a[b]:
        g[b] = g[b+1]+a[b]
    if g[b] <= 0:
        l = -1
        break
if a[0] != 0 or l == -1:
    print(-1)
else:
    print(np.sum(g))

Submission status: Runtime Error

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys
n = int(stdin.readline().rstrip())
data = [int(s) for s in stdin.readline().rstrip().split()]
pre = data[0]
nums = []
pos = n
now = data[pos]
bpos = -1
tes = False
for el in range(n):
    if data[pos-1]+now > 2**(pos-1):
        if bpos == -1:
            bpos = pos
        if int(data[pos]/2)+data[pos] % 2 <= (pos-1)**2:
            nums.append({'pos': pos, 'num': now})
            ideal = 2**(pos-1)-data[pos-1]
            now = 2**(pos-1)
        else:
            print(-1)
            tes = True
    else:
        nums.append({'pos': pos, 'num': now})
        now += data[pos-1]
    pos -= 1
nums.append({'pos': 0, 'num': 1})
if bpos != -1 and not tes:
    pos = 0
    count = 1
    while True:
        if nums[n-pos]['num'] < count:
            break
        else:
            nums[n-pos]['num'] = count
        count = (count-data[pos])*2
        pos += 1
res = 0
for el in nums:
    res += el['num']
if not tes:
    print(res)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())

A = [int(x) for x in input().split()]
B = np.zeros(N+1)
D = np.zeros(N+1)

for i in range(N+1):
    B[i] = 2**(i)

C = B - A

for i in range(N):
    if C[i+1] > C[i]*2:
        C[i+1] = C[i]*2 - A[i+1]

D[-1] = 0
for i in range(N):
    D[-(i+2)] = D[-(i+1)] + A[-(i+1)]
    if C[-(i+1)] > D[-(i+1)]:
        C[-(i+1)] = D[-(i+1)]

che = 0
for i in range(N):
    if C[i] <= 0:
        che = 1
        break

if che == 0:
    ans = np.sum(C+A)
    print(int(ans))
else:
    print(-1)