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: Wrong Answer

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

nodeList = dict()
totalCount = 0
currentLeafCount = 0
currentLeafs = []
if values[0] == 0:
    # 一番上の根を追加
    currentLeafCount = 1
    currentLeafs.append(0)
elif values[0] >= 2:
    print(-1)
    exit()
par = dict()
for i in range(n):
    a = values[i]
    if a > currentLeafCount:
        print(-1)
        exit()


    vs = []
    if len(currentLeafs) <= 2:
        vs = list(range(len(currentLeafs)))
    else:
        for l in range(len(currentLeafs)):
            if l < (len(currentLeafs) // 2):
                vs.append(l*2)
            else:
                vs.append((l-len(currentLeafs)//2)*2 + 1)

    if i == n-1:
        candidate = currentLeafs[:]
        buffer = []
        for i, v  in enumerate(vs):
            if i == len(vs) - a:
                break
            buffer.append(candidate[v])
        currentLeafs = buffer
        break

    nextLeafs = []
    adding = 0


    for index in vs:
        leaf = currentLeafs[index]

        adding += 1
        if adding <= a:
            continue
        va = [totalCount + 1, totalCount + 2]
        nodeList[leaf] = va
        par[totalCount+1] = leaf
        par[totalCount+2] = leaf
        totalCount += 2
        currentLeafCount += 2
        nextLeafs = nextLeafs + va

    currentLeafs = nextLeafs

# 最後だけ手動で足していく
a = values[n]
from collections import deque
que = deque(currentLeafs * 2)
adding = 0

if a > len(que) or len(que) == 0:
    print(-1)
    exit()

while adding < a:
    leaf = (que.popleft() if adding % 2 == 0 else que.pop())
    adding+=1

    if leaf in nodeList:
        nodeList[leaf].append(totalCount+1)
    else:
        nodeList[leaf] = [totalCount + 1]
    totalCount += 1
    par[totalCount + 1] = leaf
    if leaf in currentLeafs:
        currentLeafs.remove(leaf)


lastLeafs = currentLeafs
removeList = deque(lastLeafs)
removeCount = dict()

while len(removeList) > 0:
    cand = removeList.popleft()
    parent = par.pop(cand)

    if parent in removeCount:
        removeCount[parent] = removeCount[parent] + 1
    else:
        removeCount[parent] = 1
    if removeCount[parent] >= 2 and not parent in removeList:
        removeList.append(parent)


print(len(par)+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int,input().split()))
ans = [0]*(n+1)
ans[0] = 1
c_sum = [0]*(n+1)
c_sum[0] = arr[0]
for i in range(1,n+1):
    c_sum[i] = c_sum[i-1] + arr[i]
root = [0]*(n+1)
for d in range(n+1):
    if d==0:
        ans[d] = min(1,c_sum[-1])
    else:
        ans[d] = min(root[d-1]*2,(c_sum[-1] - c_sum[d-1]))
    if ans[d] < 0:
        print(-1)
        exit()
    root[d] = ans[d] - arr[d]
print(sum(ans))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def main():
    MAX = 10 ** 100
    n = int(input())
    A = list(map(int, input().split()))

    if n  == 0:
        if A[0] == 1:
            return 1
        else:
            return -1
    elif A[0] != 0:
        return -1
    
    nodes = 0
    bound = list(accumulate(A[::-1]))
    bound.reverse()
    # print('bound: ', bound)
    
    above = [0] * (n+1)
    above[0] = 1
    B = [0] * (n+1)
    for i in range(n+1):
        if i == 0:
            B[i] = 1
        else:
            above[i] = min((above[i-1] - A[i-1]) * 2, MAX)
            if above[i] < 0:
                return -1
            B[i] = min(above[i], bound[i])
    # print('above: ', above)
    # print('B: ', B)
    return sum(B)

print(main())

Submission status: Wrong Answer

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

ans = 1
L = [0]*(N+2)
for i in range(N+1):
    L[i+1] = L[i]+A[i]

v = 1
for i in range(1, N+1):
    v = min(2*v, L[-1]-L[i])
    ans += v
    v -= A[i]
    if v < 0:
        ans = -1
        break
if A[0] > 0 and N > 0:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


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

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

    if N == 0:
        print('1')
        exit()

    v = [0 for _ in range(N + 1)]
    v[N] = A[N]

    for i in range(N - 1, -1, -1):
        up = min(2 ** i, v[i + 1] + A[i])
        v[i] = up

    # print(v)
    for i in range(N):
        up = min(v[i + 1], (v[i] - A[i]) * 2)
        v[i + 1] = up

    # print(v)
    ans = 0
    for i in range(N + 1):
        if v[i] < A[i]:
            print('-1')
            exit()
        ans += v[i]

    # print(v)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

if A[0] == 1:
    print(-1)
else:
    Asum = [a for a in A]
    for i in range(N-1, -1, -1):
        Asum[i] += Asum[i+1]

    ans = 0
    v = 1  # 子になれる頂点数
    for i in range(N+1):
        if v < A[i]:
            ans = -1
            break

        ans += v
        p = v-A[i]
        if i < N:
            if p > Asum[i+1]:
                ans = -1
                break
            v = min(Asum[i+1], 2*p)
        else:
            if v != A[i]:
                ans = -1

    print(ans)

Submission status: Wrong Answer

Solution code:
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: Wrong Answer

Solution code:
print(- 1)

Submission status: Wrong Answer

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

res = 0

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

s = sum(A)
n = 1

res += n
if A[0] != 0:
    print(-1)
    exit()

for i in range(1,N+1):
    current = 0
    if n*2 < s:
        current = n*2

    else:
        current = s

    res += current
    s -= A[i]
    n = current -A[i]
    if n <0:
        print(-1)
        exit()

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def main():
    n = int(input())
    A = list(map(int, input().split()))

    if n == 0:
        if A[0] == 1:
            return 1
        else:
            return -1
    elif A[0] != 0:
        return -1
    
    nodes = 0
    bound = list(accumulate(A[::-1]))
    bound.reverse()
    # print('bound: ', bound)
    
    above = [0] * (n+1)
    above[0] = 1
    B = [0] * (n+1)
    for i in range(n+1):
        if i == 0:
            B[i] = 1
        else:
            above[i] = (above[i-1] - A[i-1]) * 2
            if above[i] < 0:
                return -1
            B[i] = min(above[i], bound[i])
    # print('above: ', above)
    # print('B: ', B)
    return sum(B)

print(main())

Submission status: Wrong Answer

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

ans = 1
L = [0]*(N+2)
for i in range(N+1):
    L[i+1] = L[i]+A[i]

v = 1
for i in range(1, N+1):
    v = min(2*v, L[-1]-L[i])
    ans += v
    v -= A[i]
    if v < 0:
        ans = -1
        break
if A[0] > 0 or A[-1] == 0:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    v = [1] * (n + 1)
    for i in range(n):
        v[i + 1] = min((v[i] - a[i]) * 2, 2**(i + 1))
        if v[i + 1] <= 0:
            print(-1)
            return
    if v[-1] == a[-1]:
        print(sum(v))
        return
    for i in range(1, n + 1):
        if ceil(v[-i] / 2) <= a[-1]:
            d = v[-1] - a[-1]
            for j in range(1, i + 1):
                v[-1] -= d
            print(sum(v))
            return
        d = v[-i] // 2
        for j in range(1, i + 1):
            v[-j] -= d
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if a[0] != 0:
    print(-1)
    exit()
v = [1] * (n + 1)

for i in range(1, n + 1):
    if i != n:
        if v[i - 1] * 2 <= a[i]:
            print(-1)
            exit()
        else:
            v[i] = v[i - 1] * 2 - a[i]
    else:
        if v[i - 1] * 2 < a[i]:
            print(-1)
            exit()
        else:
            v[i] = a[i]

ans = 0
sum_v = 0
for i in range(1, n + 1):
    sum_v += a[-i]
    if sum_v > v[-i - 1] * 2:
        print(-1)
        exit()
    ans += min(v[-i - 1], sum_v)
    sum_v = min(v[-i - 1], sum_v)

print(ans + sum(a))

Submission status: Wrong Answer

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 = 1
leaf = 1
for i in range(1, N+1):
        leaf = min((leaf - A[i - 1]) * 2, s[N+1] - s[i])
        # if leaf <= 0 :
        #     print(-1)
        #     break;
        node += leaf
else :
    print(node)

Submission status: Wrong Answer

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

res = 0

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

s = sum(A)
n = 1

res += n
if A[0] != 0:
    print(-1)
    exit()

for i in range(1,N+1):
    current = 0
    if n*2 - A[i] < s:
        current = n*2

    else:
        current = s

    res += current
    s -= A[i]
    n = current -A[i]
    if n <0:
        print(-1)
        exit()

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
if A[0]>1:
    print(-1)
    exit()
if A[-1]>2**n:
    print(-1)
    exit()
node1=[0]*(n+1)
node1[0]=1
node2=[0]*(n+1)
node2[-1]=A[-1]
for i in range(n):
    x=(node1[i]-A[i])*2
    if x<1:
        print(-1)
        exit()
    node1[i+1]=x
#print(node1)
for i in range(n-1,-1,-1):
    x=(node2[i+1]+A[i])
    if i<32:
        x=min(2**i, x)
    node2[i]=x
ans=[]

for i in range(n+1):
    ans.append(min(node1[i],node2[i]))
print(sum(ans))

Submission status: Wrong Answer

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

if A[0] == 1:
    print(-1)
else:
    Asum = [a for a in A]
    for i in range(N-1, -1, -1):
        Asum[i] += Asum[i+1]

    ans = 0
    v = 1  # 子になれる頂点数
    for i in range(N+1):
        if v < A[i]:
            ans = -1
            break

        ans += v
        p = v-A[i]
        if i < N:
            if p > Asum[i+1]:
                ans = -1
                break
            v = min(Asum[i+1], 2*p)

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    low, high = A[N], A[N]
    maxN = [0] * (N + 1)
    maxN[N] = A[N]
    Limit = [2 ** 50] * (N + 1)
    Limit[N] = A[N]

    for i in reversed(range(N)):
        leaf = A[i]
        Limit[i] = min(Limit[i], Limit[i+1] + leaf)
        if i <= 50: Limit[i] = min(pow(2, i), Limit[i])
        low = (low + 1) // 2 + leaf
        high += leaf
        if low > Limit[i]:
            print(-1)
            break
        else: 
            maxN[i] = min(high, Limit[i])
    else:
        #print(maxN)
        for i in range(N):
            if maxN[i] == A[i]:
                print(-1)
                break
            if (maxN[i] - A[i]) * 2 <= maxN[i+1]: 
                maxN[i + 1] = (maxN[i] - A[i]) * 2
        else: print(sum(maxN))
        #print(maxN)
        #print(lowN)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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 = 1
leaf = 1
for i in range(1, N+1):
        leaf = min((leaf - A[i - 1]) * 2, s[N+1] - s[i])
        if leaf <= 0 :
            print(-1)
            break;
        node += leaf
else :
    print(node)

Submission status: Wrong Answer

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

if A[0] >= 2:
  print(-1)
else:
  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: Wrong Answer

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

ans = 1
L = [0]*(N+2)
for i in range(N+1):
    L[i+1] = L[i]+A[i]

v = 1
for i in range(1, N+1):
    v = min(2*v, L[-1]-L[i])
    ans += v
    v -= A[i]
    if v < 0:
        ans = -1
        break
if A[0] > 0:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


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

    v = [0 for _ in range(N + 1)]
    v[N] = A[N]

    for i in range(N - 1, -1, -1):
        up = min(2 ** i, v[i + 1] + A[i])
        v[i] = up

    # print(v)
    for i in range(N):
        up = min(v[i + 1], (v[i] - A[i]) * 2)
        v[i + 1] = up

    # print(v)
    ans = 0
    for i in range(N + 1):
        if v[i] < A[i]:
            print('-1')
            exit()
        ans += v[i]

    # print(v)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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

    # Init
    node_num = 0
    next_node_w_children = 1
    next_node_num = 1
    
    for i in range(N+1):
        node_in_the_dept = next_node_num
        node_w_children = next_node_w_children      

        if(i == N):
            node_num += node_in_the_dept
            print(node_num)
        else:
            next_leaf_num = A[i+1]
            all_leave_num -=A[i]

            next_node_num = min(2 * node_w_children, all_leave_num)
            next_node_w_children = next_node_num - next_leaf_num
            if(next_node_num > node_w_children * 2 or next_node_num < node_w_children or next_node_w_children < 0):
                print(-1)
                return
            node_num += node_in_the_dept
    

main()

Submission status: Wrong Answer

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

res = 0
s=0
s1 = [1]
s2 = {}

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

s = sum(A)
n = 1

res += n
if A[0] == 1:
    print(-1)
    exit()

for i in range(1,N+1):
    current = 0
    if n*2 - A[i] < s:
        current = n*2

    else:
        current = s

    res += current
    s -= A[i]
    n = current -A[i]
    if n <0:
        print(-1)
        exit()

print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if a[0]>=2:
    print(-1)

else:
    pN=1
    s=1
    l=[]
    S=sum(a)
    b=0
    z=1
    for k in range(len(a)):
        b+=a[k]
        l.append(b)

    for i in range(1,n):
        if a[i]>2*pN:
            print(-1)
            z=0
            break
        else:
            pN=min(2*pN-a[i],S-l[i])
            s+=pN
    s+=S
    if n==0 and a[0]==0:
        print(-1)
        z=0
            
    if a[0]==1 and n>=1:
            print(-1)
            z=0

    if z:
        print(s)

Submission status: Wrong Answer

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

l = [0]*(n+1)
l[-1] = a[-1]
for i in range(n-1,-1,-1):
    l[i] += l[i+1]+a[i]

if a[0] == 1:
    if n > 0:
        print(-1)
        exit()
    else:
        print(1)
        exit()
b = 2
ans = 1
for i in range(1,n+1):
    if b*2 < a[i]:
        print(-1)
        exit()
    else:
        if i == n:
            ans += a[-1]
        else:
            b = (b-a[i])*2
            ans += min(b,l[i+1])

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
if a[0]!=0:
    print(-1)
    exit()
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
print(ans+sum(a))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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


from itertools import accumulate
acc = reversed(a)
acc = list(accumulate(acc))
acc= list(reversed(acc))

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

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

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

ans[n]=a[n]

def dfs(fukasa):
    if fukasa == 0:
        if ans[fukasa] == 1:
            return True
        else:
            return False

    mi = a[fukasa] -(-ans[fukasa+1]//2)
    ans[fukasa] = mi
    if not dfs(fukasa-1):
        return False

    tmp = a[fukasa]+ans[fukasa+1]
    tmp = min(tmp,2**fukasa)
    tmp = min(tmp,acc[fukasa])

    while tmp >= a[fukasa] -(-ans[fukasa+1]//2):
        ans[fukasa]=tmp
        if dfs(fukasa-1):
            break
        tmp -= 1
    else:
        return False
    return True


tmp = dfs(n-1)

if tmp:
    print(sum(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    low, high = A[N], A[N]
    maxN = [0] * (N + 1)
    maxN[N] = A[N]
    Limit = [2 ** 50] * (N + 1)
    Limit[N] = A[N]

    for i in reversed(range(N)):
        leaf = A[i]
        Limit[i] = min(Limit[i], Limit[i+1] + leaf)
        if i <= 50: Limit[i] = min(pow(2, i), Limit[i])
        low = (low + 1) // 2 + leaf
        high += leaf
        if low > Limit[i]:
            print(-1)
            break
        else: 
            maxN[i] = min(high, Limit[i])
    else:
        #print(maxN)
        for i in range(N):
            if (maxN[i] - A[i]) * 2 <= maxN[i+1]: maxN[i + 1] = (maxN[i] - A[i]) * 2
        print(sum(maxN))
        #print(maxN)
        #print(lowN)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

ans, cnt, node = 0, sum(a), 1
for i in range(n + 1):
    ans += node
    if node <= 0:
        print(-1)
        break
    cnt -= a[i]
    node = min(cnt, (node - a[i]) * 2)
else:
    print(ans)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A == [0]:
            print('0')
        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

    if A[0] != 0:
        print('-1')
        return

    f = [0 for i in range(N)]

    f[0] = 1
    count = sum(A) - 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 -= max(min(f[d - 1], count), 0)
        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: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
print(ans+sum(a))

Submission status: Wrong Answer

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

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

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: Wrong Answer

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]
  h = Ha[i]
  pw = pow(2,i)

  a = min(pw-h, f*2-h)

  if a<=0:
    print(-1)
    exit(0)

  Fushi.append( a )


Fushi[N]=0

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


#for f in reversed(Fushi[:-1]):
#  print(f)

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: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
if n == 0:
    if a[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
d = [-1 for _ in range(n + 1)]
s = [0 for _ in range(n + 2)]
for i in reversed(range(n + 1)):
    s[i] = s[i + 1] + a[i]
d[0] = 1
for i in range(1, n + 1):
    d[i] = min((d[i - 1] - a[i - 1]) * 2, s[i])
    if d[i] <= 0:
        print(-1)
        exit()
print(sum(d))

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
from collections import defaultdict

import time

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

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

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq

n = readInt()
a = readInts()

tar = []
for i in range(len(a)):
	tar.append(2**i-a[i])
tar[-1] = 0

if n==0:
	print(1)
	exit()

while 1:
	changed = 0
	for i in range(len(tar)-1):
		if tar[i]*2<tar[i+1]+a[i]:
			changed = 1
			tar[i+1] = tar[i]*2-a[i+1]
		elif tar[i]<0:
			print(-1)
			exit()
			


	for i in range(len(tar)-1,0,-1):
		if tar[i]+a[i]<tar[i-1]:
			changed = 1
			tar[i-1] = tar[i]+a[i]
		elif tar[i]<0:
			print(-1)
			exit()

	if changed==0:
		break


print(sum(a)+sum(tar))

Submission status: Wrong Answer

Solution code:
print(-1)
exit()

Submission status: Wrong Answer

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

ans = 0
prev = 1
L = [0]*(N+1)
L[0] = 1
for i in range(1, N+1):
    if prev*2 > A[i]:
        prev = prev*2-A[i]
    elif prev*2 == A[i] and i == N:
        continue
    else:
        ans = -1
        break
    L[i] = prev
    if prev > 10**10:
        for j in range(i+1, N+1):
            L[j] = "inf"
        break

if A[0] > 0:
    ans = -1

if ans == 0:
    L = [0]*(N+2)
    for i in range(N+1):
        L[i+1] = L[i]+A[i]
    prev = 1
    ans = 1
    for i in range(1, N+1):
        d = min(2*prev, L[-1]-L[i])
        ans += d
        prev = d-A[i]
        
print(ans)

Submission status: Wrong Answer

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

import math
count = 0
prev = 0
for n in range(N+1):
    depth = N - n
    print("depth:",depth)
    now = A.pop(depth)
    print("now:",now)
    border = 2**depth - sum([A[depth-i-1]*2**(i+1) for i in range(len(A))])
    print("border:",border)
    if now+math.ceil(prev/2) > border:
        count = -1
        break

    print("now:",now)
    if now+prev <= border:
        now += prev
    else:
        now = border
    print("now:",now)
    print("prev:",prev)
    count += now
    prev = now
    print("prev:",prev)
    print("count:",count)
    print("\n")

Submission status: Wrong Answer

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

sita_maxi = [0 for i in range(n+1)]
sita_maxi[n] = a[n]
for i in range(n-1, -1, -1):
    sita_maxi[i] = sita_maxi[i+1] + a[i]

lst = [1]
for i in range(1, n+1):
    lst.append(min((lst[i-1]-a[i-1])*2, sita_maxi[i]))
    if lst[-1] < a[i]:
        print(-1)
        exit()

print(sum(lst))

Submission status: Wrong Answer

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

if bottom == 0:
  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: Wrong Answer

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]
  h = Ha[i]
  pw = pow(2,i)

  if pw-h<=0:
    print(-1)
    exit(0)

  Fushi.append( min(pw-h, f*2-h) )


Fushi[N]=0

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


#for f in reversed(Fushi[:-1]):
#  print(f)

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

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

  Fushi[i] = min(Fushi[i], h+f)



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


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