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:
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, a in enumerate(A):
        if i == 0:
            B[0] = 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)

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
 
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])
    v.append(min((v[-1]-a[i])*2,back[i+1]))
print(sum(v))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    A = list(map(int,input().split()))
    ans = 1
    befc = 1 - A[0] 
    tmp = sum(A[1::])
    for i in range(1,N+1):
        curc = min(befc * 2, tmp)
        if curc < A[i]:
            return -1
        ans += curc
        befc = curc - A[i]
        tmp -= A[i]
    return ans

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

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)
    lowN = [0] * (N + 1)
    maxN[N] = A[N]
    Limit = [10 ** 15] * (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 <= 46: 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 - 1):
            if (maxN[i] - A[i]) * 2 <= maxN[i+1]: maxN[i + 1] = (maxN[i] - A[i]) * 2
        if (maxN[N-1] - A[N-1]) * 2 == A[N]: print(sum(maxN))
        else: print(-1)
        #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 = 0

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


start = 1
way = sum(A)

for i in range(1,n+1):
    start *= 2

    if start < A[i]:
        print(-1)
        exit()
    if start > way:
        start = way

    ans += start
    #print(start, start-A[i])
    start -= A[i]
    way -= A[i]
#print()
print(ans+1)

Submission status: Wrong Answer

Solution code:
n =int(input())
a = int()

#leaves = input()
leaves = list(map(int, input().split()))
points = list(range(n+1))
lines  = list(range(n+1))

for i in lines:
  lines[i] = sum(leaves[i:n+1])

lines[0] = 1
points[0] = 1

for i in range(n-1):
  if 2*(points[i] - leaves[i]) < leaves[i+1] +1:
    print(-1)
    a = -1
    break
  else:
    points[i+1] = min(2*(points[i]-leaves[i]), lines[i+1])

if 2*(points[n-1] - leaves[n-1]) < leaves[n]:
  print(-1)
  a = -1
else:
  points[n] = min(2*(points[n-1]-leaves[n-1]), lines[n])

if a != -1:
  print(sum(points[0:n+1]))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
Z = A[-1]
A[-1] = 0
flag = 0
B = A[::-1]
if N==0:
    if Z!=1:
        print(-1)
    else:
        print(1)
elif A[0]!=0:
    print(-1)
elif N==1:
    if Z>=3 or Z==0:
        print(-1)
    else:
        print(Z+1)
else:
    sita = [0]*(N+1)
    sita[0] = Z
    for i in range(1,N+1):
        X = B[i-1]+sita[i-1]
        if X<=0:
            flag = 1
            break
        if math.log2(X+B[i]) > (N-i):
            sita[i] = 2**(N-1)-B[i]
        else:
            sita[i] = X
    if flag==0:
        ue = [0]*(N+1)
        ue[0] = 1
        for i in range(1,N+1):
            Y = ue[i-1]*2-A[i]
            if Y>=sita[N-i]:
                ue[i] = sita[N-i]
            else:
                ue[i] = Y
            if ue[i]<=0:
                flag = 1
                break
    if flag==1:
        print(-1)
    else:
        print(sum(B)+sum(ue))

Submission status: Wrong Answer

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    whole = sum(a)

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

    ans = 0
    base = 1
    for i in range(n + 1):
        ans += base
        base -= a[i]
        whole -= a[i]
        base = min(base * 2, whole)
        if base <= 0 and i != n:
            print(-1)
            exit(0)

    print(ans)


if __name__ == '__main__':
    main()

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)
    lowN = [0] * (N + 1)
    maxN[N] = A[N]
    lowN[N] = A[N]
    Limit = [10 ** 15] * (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 <= 46: Limit[i] = min(pow(2, i), Limit[i])
        low = (low + 1) // 2 + leaf
        high += leaf
        if low > Limit[i]:
            print(-1)
            break
        else: 
            lowN[i] = low
            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()))

up = [0] * (N+1)
down = [0] * (N+1)

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

up = up[::-1]
down[0] = 1
for i in range(1, N+1):
    down[i] = (down[i-1] - A[i-1])*2
    if down[i] > up[i]:
        break

flug = True
lst = [0] * (N+1)
for i in range(N+1):
    if flug and down[i] < up[i]:
        lst[i] = down[i]
    else:
        flug = False
        lst[i] = up[i]

# print(up, down, lst)
flug = False
for i in lst:
    if i <= 0:
        flug = True
if flug:
    print(-1)
else:
    print(sum(lst))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
if (n != 0 and a_list[0] != 0) or (n == 0 and n != 1):
    print(-1)
    exit()

asc = [0] * (n + 1)
desc = [0] * (n + 1)
asc[0] = 1
desc[-1] = a_list[-1]
sum = 1

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]

for i in range(1, n + 1):
    num = min(asc[i], desc[i])
    sum += num
    if num < a_list[i] or num < 1:
        print(-1)
        exit()

print(sum)

Submission status: Wrong Answer

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
max_node = [0] * (N+1)
for i in range(N-1,-1,-1):
    max_node[i] = max_node[i+1]+A[i+1]


ans = 1
node = 1
for i in range(N+1):
    node -= A[i]
    if (i < N and node <= 0) or node < 0:
        print(-1)
        break
    node = min(node*2,max_node[i])
    ans += node
print(ans)

Submission status: Wrong Answer

Solution code:
n= int(input())

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

#print(a)

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

b=1
count=1
asum =sum(a)
alim = asum

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

        count += b



print(count+ asum)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
Z = A[-1]
A[-1] = 0
flag = 0
B = A[::-1]
if N==0:
    if Z!=1:
        print(-1)
    else:
        print(1)
elif A[0]!=0:
    print(-1)
elif N==1:
    if Z>=3 or Z==0:
        print(-1)
    else:
        print(Z+1)
else:
    sita = [0]*(N+1)
    sita[0] = Z
    for i in range(1,N+1):
        X = B[i-1]+sita[i-1]
        if X<=0:
            flag = 1
            break
        if math.log2(X+B[i]) > (N-i):
            sita[i] = 2**(N-1)-B[i]
        else:
            sita[i] = X
    if flag==0:
        ue = [0]*(N+1)
        ue[0] = 1
        for i in range(1,N+1):
            Y = ue[i-1]*2-A[i]
            if Y>=sita[N-i]:
                ue[i] = sita[N-i]
            else:
                ue[i] = Y
            if ue[i]<=0:
                flag = 1
                break
    if flag==1:
        print(-1)
    else:
        print(ue,sita)
        print(sum(B)+sum(ue))

Submission status: Wrong Answer

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.int)
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: Wrong Answer

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

if n == 0:
  if a[0] == 1:
    print(1)
  else:
    print(-1)
else:
  accum = [0]*(n+1)
  new_list = list(reversed(a))
  accum[0] = new_list[0]
  for i in range(n-1):
      accum[i+1] = accum[i] + new_list[i+1]
  hat = list(reversed(accum))
  #print(hat)

  b = [1]*(n+1)
  flag = 0
  cand = 0

  for i in range(1,n+1):
    cand = (b[i-1]-a[i-1])*2
    if cand < 1:
      flag = 1
      break
    if cand > hat[i-1]:
      b[i] = hat[i-1]
    else:
      b[i] = cand

  #print(b)
  if flag != 1:
    print(sum(b))
  else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    A = list(iim())

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

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

    A.reverse()
    B.reverse()
    ans = node = 0
    for d, lim in zip(A, B):
        node = min(node, lim)
        node += d
        ans += node

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
if A[0]>=1:
  print(-1)
  sys.exit()
ans=A[N]
left=1
P=[1 for i in range(N+1)]
for i in range(1,N+1):
  point=left*2
  P[i]=point
  if i!=N and point-A[i]<0:
    print(-1)
    sys.exit()
  if i==N and point-A[i]<0:
    print(-1)
    sys.exit()
  left=point-A[i]
root=A[N]
for i in range(N,0,-1):
  root=min(P[i-1],root+A[i-1])
  ans+=root
print(ans)

Submission status: Wrong Answer

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

l = []

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

temp = 1
for i in range(N+1):
    l.append(temp-A[i])
    temp = (temp-A[i])*2

for i in range(N+1):
    if l[i] < 0:
        print(-1)
        sys.exit()

if sum(A) == 0:
    print(-1)
    sys.exit()

ans = 1
node = 0
for i in range(N, 0, -1):
    if l[i-1] >= node + A[i]:
        node += A[i]
        ans += node
    else:
        ans += node + A[i]
        node = l[i-1]

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0] *(N+1)
B[0] = 1
ans = 0
for i in range(1, N+1):
    B[i] = (B[i-1] - A[i-1])*2
    if B[i] <= 0:
        ans = -1
        break
if B[N] < A[N]:
    ans = -1
if ans == 0:
    check = 0
    for j in range(N, 0, -1):
        check += A[j]
        if check < B[j]:
            ans += check
        else:
            last = j
            for k in range(last+1):
                ans += B[k]
            break
if N == 0 and A[0] == 1:
    ans = 1
print(ans)

Submission status: Wrong Answer

Solution code:

N=int(input())
A=list(map(int,input().split()))
sum_value = sum(A)
chiled_value = 1
top_value = 1
if(N==0 & A[0]==1):
    print(1)
    exit()
if(A[0]!=0):
    print(-1)
    exit()
for i in range(1,N):
    if(sum_value >= chiled_value*2):
        top_value += chiled_value*2
        chiled_value = chiled_value*2-A[i]
        sum_value=sum_value-A[i]
        if(A[i+1]>chiled_value*2):
            print(-1)
            exit()
    elif(sum_value < chiled_value*2):
        chiled_value=sum_value
        top_value += chiled_value
        sum_value=sum_value-A[i]
    if(A[i]>=2**i):
        print(-1)
        exit()
if((sum_value-A[N])!=0):
    print(-1)
    exit()
print(top_value+A[N])

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
if A[0]>=1:
  print(-1)
  sys.exit()
ans=A[N]
left=1
P=[1 for i in range(N+1)]
for i in range(1,N+1):
  point=left*2
  P[i]=point
  if i!=N and point-A[i]<1:
    print(-1)
    sys.exit()
  if i==N and point-A[i]<0:
    print(-1)
    sys.exit()
  left=point-A[i]
root=A[N]
for i in range(N,0,-1):
  root=min(P[i-1],root+A[i-1])
  ans+=root
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
al = [int(i) for i in input().split()]
total = 0
mi = 0
ma = 0
l_mami = []
f = True
import math

for i in reversed(range(n+1)):
  mi = math.ceil(mi / 2) + al[i]
  if mi > 2**i:
    print(-1)
    f = False
    break
  ma = ma + al[i]
  l_mami.append((mi, ma))  
  
if f:
  ma = 1
  total = 1
  for i in range(1,n):
    ma = min((ma - al[i-1])*2, l_mami[n - i][1])
    total += ma
  total += al[-1]
  print(total)

Submission status: Wrong Answer

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)
for i in range(N+1):
    if a[i] > n * 2:
        l = -1
        break
    if a[i] > 2**i:
        l = -1
        break
    g[i] = n
    l += n
    n = (n-a[i])*2
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 a[0] != 0 or l == -1:
    print(-1)
else:
    print(int(sum(g)))

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a_li = list(map(int, input().split()))
sum_li = []
tmp = 0
for a in reversed(a_li):
    tmp += a
    sum_li.append(tmp)

if a_li[0]>0 and n>0:
    print(-1)
else:
    cnt = 1
    node = 1
    for i in range(1, n+1):
        node = min(node*2-a_li[i], sum_li[n-i-1])
        if i!=n:
            if node <= 0:
                print(-1)
                break
            cnt += node + a_li[i]
        else:
            if node < 0:
                print(-1)
                break
            cnt += a_li[i]
    else:
        print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    whole = sum(a)

    ans = 0
    base = 1
    for i in range(n + 1):
        ans += base
        base -= a[i]
        whole -= a[i]
        base = min(base * 2, whole)
        if base <= 0 and i != n:
            print(-1)
            exit(0)

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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]

for i in range(1, n + 1):
    num = min(asc[i], desc[i])
    sum += num
    if num < a_list[i]:
        print(-1)
        exit()

print(sum)

Submission status: Wrong Answer

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

    max_node = []

    for i in range(n, -1, -1):
        if i == n:
            max_node.append(A[i])
        elif i == 0:
            max_node.append(1)
        else:
            max_node.append(max_node[n-i-1] + A[i])
    
    max_node = max_node[::-1]
    res = 0

    for i in range(len(max_node)):
        if i == 0:
            continue
        elif i == 1 and max_node[i] > 2:
            max_node[i] = 2
        
        if max_node[i] > 2 * (max_node[i-1] - A[i-1]):
            max_node[i] = 2 * (max_node[i-1] - A[i-1])
        
        if max_node[i] >= max_node[i-1]*2 and max_node[i] <= A[i]:
            res = -1
            break

    
    if n != 0 and A[0] == 1:
        res = -1
    
    if n == 0 and A[0] > 1:
        res = -1
        
    if res == 0:
        print(sum(max_node))
    else:
        print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
su = sum(a)
# print(su)
l = [su]*(n+1)
for i in range(1,n+1):
    l[i]=l[i-1]-a[i-1]
# print(l)
count=0
x = 0
m=[1]*(n+1)
for j in range(1,n+1):
    m[j] = m[j-1]*2
    if m[j]>l[j]:
        m[j]=l[j]
    if (m[j]<a[j])or(m[j]==a[j] and j!=n):
        # print(m[j],a[j])
        x = 1
        break
    # print(m[j])
    count += m[j]
    m[j] -= a[j]
count+=1

if x==1 or a[0]!=0 or n==0:
    print(-1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)
 
if bottom == 0 or A[0] >= 1:
  print(-1)
  exit()
 
ret = 1
children = 1
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
 
    if children <= 0 and i != N-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 = list(map(int,input().split()))
P = [2**i for i in range(len(A))]
import sys
sys.setrecursionlimit(10**9)


if N==0 and A[0]==1:
    print(1)
    exit()
if A[0] == 1:
    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]


    if (i!=N and node[0] - A[i] <= 0) or (node[0] - A[i] < 0):
        print(-1)
        exit()
    return node[0] - A[i]
rec(N)
print (ans[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
last = A[-1]
count = last
root = 1
for i in range(N):
  if i+1 == N and root > A[i+1]:
    root = last + A[i]
  elif root > (last + A[i+1])*2:
    root = (last + A[i+1])*2
  count+=root
  root = (root-A[i])*2
  if root < A[i+1]:
    print(-1)
    break
else:
  print(count)

Submission status: Wrong Answer

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

ans = 0

parents = 1

if n == 0:
    if a[0] > 1:
        ans = -1
    else:
        ans = a[0]

if a[0] == 1:
    parents = 0
    ans = 1
    if n != 0:
        ans = -1

parentsls = [0 for _ in range(n+1)]
parentsls[0] = parents

bicapls = [0 for _ in range(n+1)]

for i in range(1, n+1):
    if i != n and parents == 0:
        ans = -1    
        break
    if a[i] > parents*2:
        ans = -1
        break
    else:
        parents = parents*2 - a[i]
        parentsls[i] = parents
    
if ans != -1:
    node = 0
    for i in range(n):
        if parentsls[n-1-i] >= node + a[n-i]:
            ans += node + a[n-i]
            node = node + a[n-i]
        else:
            ans += node + a[n-i]
            node = parentsls[n-1-i]

    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
Z = A[-1]
A[-1] = 0
flag = 0
B = A[::-1]
if N==0:
    if Z!=1:
        print(-1)
    else:
        print(1)
elif A[0]!=0:
    print(-1)
else:
    sita = [0]*(N+1)
    sita[0] = Z
    for i in range(1,N+1):
        X = B[i-1]+sita[i-1]
        if X<=0:
            flag = 1
            break
        if math.log2(X+B[i]) > (N-i):
            sita[i] = 2**(N-1)-B[i]
        else:
            sita[i] = X
    if flag==0:
        ue = [0]*(N+1)
        ue[0] = 1
        for i in range(1,N+1):
            Y = ue[i-1]*2-A[i]
            if Y>=sita[N-i]:
                ue[i] = sita[N-i]
            else:
                ue[i] = Y
            if ue[i]<=0:
                flag = 1
                break
    if flag==1:
        print(-1)
    else:
        print(sum(B)+sum(ue))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
from itertools import accumulate
Ac = list(accumulate(A))
import sys
ans = 1
num = 1
for i in range(N):
    num = min(2*(num-A[i]),Ac[N]-Ac[i]) 
    if num<=0:
        print("-1")
        sys.exit()
    ans += num
print(ans)

Submission status: Wrong Answer

Solution code:
n= int(input())

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

#print(a)

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

b=1
count=1
asum =sum(a)
alim = asum

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

        count += b



print(count+ asum)

Submission status: Wrong Answer

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

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

if d[-1] < 0:
    print(-1)
    exit()
else:
    d[-1] = A[-1]
for i in range(N, 0, -1):
    x = d[i]
    x += A[i-1]
    if d[i-1] * 2 < x:
        y = x - A[i-1]
        if (y+1) // 2 + A[i-1] <= d[i-1] * 2:
            x = d[i-1] * 2
        else:
            print(-1)
            exit()
    d[i-1] = min(x, d[i-1]+A[i-1])
print(sum(d))

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))

    if(N == 0):
        if(A[0] == 1):
            print(1)
        else:
            print(-1)
        exit(0)
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 1 and A[1] != 2):
        print(-1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] > pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        a[i] = node[i - 1] + cur
        # print("i={}, cur={}".format(i, cur))
    # print(node)
    # print(a)
    # 最初の頂点
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      # if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

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)
    lowN = [0] * (N + 1)
    maxN[N] = A[N]
    lowN[N] = A[N]
    Limit = [10 ** 15] * (N + 1)

    for i in reversed(range(N)):
        leaf = A[i]
        Limit[i] = min(Limit[i], high + leaf)
        if i <= 46: Limit[i] = min(pow(2, i), Limit[i])
        low = (low + 1) // 2 + leaf
        high += leaf
        if low > Limit[i]:
            print(-1)
            break
        else: 
            lowN[i] = low
            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:
import sys

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


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

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

    for i in range(N - 1, -1, -1):
        low, up = v[i + 1][0], v[i + 1][1]
        up = min(2 ** i, up + A[i])
        if low % 2 == 0:
            low = low // 2 + A[i]
        else:
            low = low // 2 + A[i] + 1

        if low < 0 or up < 0 or (low > up):
            print('-1')
            exit()
        v[i] = (low, up)

    # print(v)
    for i in range(N):
        low, up = v[i][0], v[i][1]
        low = max(v[i + 1][0], low - A[i])
        up = min(v[i + 1][1], (up - A[i]) * 2)
        if low < 0 or up < 0 or (low > up):
            print('-1')
            exit()
        v[i + 1] = (low, up)

    # print(v)
    ans = 0
    for i in range(N + 1):
        ans += v[i][1]

    # print(v)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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


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

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

suma=sum(a)

cnt=1
bk=1

for i,aa in enumerate(a[1:]):
    node=min(suma,bk*2)
    cnt+=node
    #print(i,aa,node)
    bk=node-aa
    suma-=aa

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if A[0] != 0:
  print(-1)
  quit()

n = [0] * (N+1)
n[0] = 1
for i in range(1, N+1):
  a = A[i]
  m = n[i-1] * 2
  n[i] = m - a
  if n[i] < 0:
    print(-1)
    quit()

n[-1] = 0
for i in range(N-1, 0, -1):
  nn = n[i+1]
  a = A[i+1]
  n[i] = min(n[i], a + nn)

print(sum(n) + sum(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
su = sum(a)
# print(su)
l = [su]*(n+1)
for i in range(1,n+1):
    l[i]=l[i-1]-a[i-1]
# print(l)
count=0
x = 0
m=[1]*(n+1)
for j in range(1,n+1):
    m[j] = m[j-1]*2
    if m[j]>l[j]:
        m[j]=l[j]
    if (m[j]<a[j])or(m[j]==a[j] and j!=n):
        # print(m[j],a[j])
        x = 1
        break
    # print(m[j])
    count += m[j]
    m[j] -= a[j]
count+=1

if x==1 or a[0]!=0 :
    print(-1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
An = list(map(int,input().split()))
Sum = 0
Sum += 2**N
for i in An:
	Sum+=2**i

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    A = list(map(int,input().split()))
    A = np.array(A)

    if (N != 0) & (A[0] != 0):
        print(-1)
        sys.exit()

    M = np.sum(A)
    already = 1
    end = 0

    now = 1
    res = 1

    for d in range(1,N+1):
        temp = min(2*now-now,M-already)
        now += temp
        # print(now)
        res += now
        # print(d,now,res)
        already += temp
        end += A[d]
        now -= A[d]
        # print(d,res)
        if (d != N) & (now <= 0):
            res = -1
            break

    print(res)



main()