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())
A = list(map(int,input().split()))
saidaiA =[]
oya = 1
flag = True
for i in range(len(A)):
    if oya >= 5*10**13:
        ko = 10**14
    else:
        ko = oya *2
    if i == 0:
        ko = 1
    oya = ko - A[i]
    saidaiA.append(ko)
    if oya < 0:
        flag = False
ans = 0
# print(saidaiA)
motikosi = 0
for i in range(len(A)):
    if A[-i] + motikosi >= saidaiA[-i]:
        ans += saidaiA[-i]
        motikosi = saidaiA[-i]
    else:
        ans += A[-i] + motikosi
        motikosi = A[-i] + motikosi
if flag == True:
    print(ans+1)
else:
    print(-1)

Submission status: Wrong Answer

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

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

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

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

print(sum)

Submission status: Wrong Answer

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

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

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]

d = [0]*(n+1)
flag = 0
for k in range(n+1):
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1

for l in range(n):
    flag += 1 if d[l+1] < d[l] - a[l] or 2*d[l] - a[l] < d[l+1] else 0

print(sum(d) if flag == 0 else -1)

Submission status: Wrong Answer

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

ch = [1]

cH = [1]
if A[0]>0:
    print(-1)
    exit()
if A[-1]==0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
    # ch.append((cH[-1]*2)//(2**i))
# print(ch)
print(cH)
# ch = ch[:-1]
# ch = ch[::-1]
# ch[0]*=2
# print(ch)
cH = cH[:-1]
cH.append(cH[-1]*2)
cH = cH[::-1]
print(cH)
if 0 in cH:
    print(-1)
    exit()
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:-1]):
    # print(n,ch[e],-1)
    if n//2>cH[e]:
        print(-1)
        exit()
    if n  <= cH[e]:
        # print('ans:',ans,'n:',n)
        ans += n+i
        n+=i
    else:
        # print('ans:',ans,'ch:',cH[e],'i:',i)
        ans +=cH[e]+i
        n = cH[e]+i

    # print('ans:',ans,'n:',n)
print(ans+1)

Submission status: Wrong Answer

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

top_m = [0] * (n+1)
top = 1
for i, x in enumerate(a):
    top_m[i] = top - x
    top = top_m[i] * 2
top_m = top_m[::-1][1:]
# print(top_m)

p_max = a[-1]
p_min = math.ceil(p_max/2)
top = p_max
a = a[::-1][1:]
for i, x in enumerate(a):
    # print(x, p_max, p_min, top_m[i], top)
    if p_min > top_m[i]:
        print(-1)
        exit()
    now = x + min(p_max, top_m[i])
    p_max = now
    p_min = math.ceil(now/2)
    top += now
print(top)

Submission status: Wrong Answer

Solution code:
N =int(input())
A = list(map(int,input().split()))
leaf = sum(A)
if A[0] != 0:
    print(-1)
    exit()
v = [[0,a] for a in A]
v[0][0] = 1
MAX = 2
for i in range(1,N+1):
    v[i][0] = min((v[i-1][0]-v[i-1][1])*2,leaf)
    leaf -= v[i][1]
    MAX *= 2

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

ans = 0
for a,b in v:
    if a <= 0:
        print(-1)
        exit()
    ans += a

print(ans)

Submission status: Wrong Answer

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

nodes = [0] * (N + 1)
nodes[0] = 1 - A[0]

if all([a == 0 for a in A]):
    print(-1)
else:
    for index, a in enumerate(A[1:], start=1):
        nodes[index] = nodes[index - 1] * 2 - a
        if nodes[index] < 0:
            print(-1)
            break
    else:
        fixed_nodes = [0] * (N + 1)
        fixed_nodes[-1] = A[-1]
        for i in reversed(range(N)):
            if nodes[i] * 2 < fixed_nodes[i + 1]:
                print(-1)
                break
            fixed_nodes[i] = min(nodes[i], fixed_nodes[i + 1])
            fixed_nodes[i] += A[i]
        else:
            if fixed_nodes[0] == 0:
                print(-1)
            else:
                print(sum(fixed_nodes))

Submission status: Wrong Answer

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

    if m >= l*2:
        ans += l * 2
        l *= 2
    else:
        ans += m
        l = m
        #gr = False
    if x > 0:
        m -= x
        l -= x
        if m < 0:
            print(-1)
            exit()
print(ans)

Submission status: Wrong Answer

Solution code:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    # print(1 if A_N[0] == 1 else -1)
    print(-1)
    exit()

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [1]
if a[0] != 0:
    print(-1)
    exit()
cnt = 2
ans = 1
for i in range(1, n+1):
    if i != n:
        if a[i] >= cnt:
            ans = -1
            break
        l.append(a[i]+(cnt-a[i])//2)
        ans += cnt
        cnt -= a[i]
        cnt *= 2
    if i == n:
        if cnt < a[i]:
            ans = -1
        else:
            ans += cnt
            l.append(cnt//2)
if ans == -1:
    print(ans)
else:
    ind = -1
    while cnt > a[n]:
        if cnt - l[ind] <= a[n]:
            ans += (cnt - a[n]) * ind
            cnt = a[n]
        else:
            cnt -= l[ind]
            ans += l[ind] * ind
        ind -= 1
        if ind == 0:
            ans = -1
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10


    N = II()
    A = LMIIS()


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


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


    sum_top = 1

    tmp = 1
    
    for i in range(1,N+1):
        max_l = tmp*2
        if max_l >= max_nodes[i]:
            print(sum_top+sum(max_nodes[i:]))
            return
        sum_top += max_l
        tmp = max_l - A[i]
        if tmp < 0:
            print(-1)
            return

    dbg(sum_top)
    print(-1)


main()

Submission status: Wrong Answer

Solution code:
import math
#3
#0 1 1 2

N = int(input())+1
leaves = list(map(int, input().split()))

nod = 0
total = 0

maxx = [0]*(N+1)
#toward
maxx[0] = 1
if N == 1 and leaves[0] == 1:
    total = 1
else:

    for i in range(1, N):
        notleave = maxx[i-1] - leaves[i-1]
        if notleave <= 0:
            total = -1
            break
        maxx[i] = notleave*2
        if maxx[i] < leaves[i]:
            total = -1
            break
        # if i == N-1:
        #     total += leaves[i]
        # else:
        #     total += maxx[i]


if total >= 0:
    #backward
    for i in range(1, N+1):
        ii = N-i
        #at least need newnod nodes
        newnod = int((nod+1)/2) + leaves[ii]
        if newnod > maxx[ii]:
            total = -1
            break
        #maximum is?
        newnod = nod + leaves[ii]
        if newnod > maxx[ii]: newnod = maxx[ii]
        if newnod <= 0:
            total = -1
            break
        total += newnod
        nod = newnod


if total <= 0: total = -1
print(total)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
D = [0]*(N+1)
prev = 0
for i in range(N,-1,-1):
    D[i] = prev+A[i]
    prev = D[i]
prev = 1
for i in range(N+1):
    tmp = min(2**i,prev*2)
    if D[i] > tmp:
        D[i] = tmp
    prev = tmp-A[i]
for i in range(N,-1,-1):
    tmp = 0
    if i != N:
        tmp = (A[i+1]+1)//2
    if tmp+A[i] > 2**i:
        print(-1)
        exit()
print(sum(D))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
lim = 2**(n-1)
lim_1 = 2**(n-2)
ans = a[-1]+1
temp = a[-1]

for i in range(1,n):
  if a[-(i+1)] + (temp+1)//2 > lim:
    ans = -1
    break
   
  if (a[-(i+1)] + temp <= lim) and (a[-(i+2)] + a[-(i+1)] + temp <=(lim_1-a[-(i+2)])*2):
    ans += a[-(i+1)] + temp
    temp = a[-(i+1)] + temp
  elif (a[-(i+1)] + temp > lim) and (a[-(i+2)] + a[-(i+1)] + lim <=(lim_1-a[-(i+2)])*2):
    ans += a[-(i+1)] + lim
    temp = a[-(i+1)] + lim
  else:
    if (temp+1)//2 + a[-(i+1)] > (lim_1-a[-(i+2)])*2:
      ans = -1
      break
    
    ans += (lim_1-a[-(i+2)])*2
    temp = (lim_1-a[-(i+2)])*2

      
  print(temp)
      
  lim = lim//2
  lim_1 = lim_1//2
      
if n == 1:
  ans = a[1] + 1
if a[0] > 0:
  ans = -1
  
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if A[0]!=0:
    print(-1)
    exit()
else:
    C=[0]*(N+1)
    C[0]=1
    for i in range(1,N-1):
        if C[i-1]*2-A[i]<0:
            print(-1)
            exit()
        else:
            C[i]= C[i-1]*2-A[i]
        
    print(sum(A)+sum(C)+A[N]-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import log2

N = int(input())
A = [int(i) for i in input().split()] + [0]

def solve() :
  M = [1]
  pre = 1
  if A[-2] == 0 :
    return -1
  for i in range(N) :
    M.append(pre * 2)
    pre = pre * 2 - A[i + 1]
    if (A[i + 1] + 1) // 2 + A[i] == 0 :
      continue
    if i < log2((A[i + 1] + 1) // 2 + A[i]) :
      return -1
  
  ret = A[-2]
  pre = A[-2]
  for i in range(N - 1, -1, -1) :
    cur = min(M[i], A[i] + pre)
    ret += cur
    pre = cur
  
  return ret
  
print(solve())

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)
# A = A[::-1]
# P = P[::-1]

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

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

# for a,p in zip(A[::-1],P[::-1]):
#     if a > p:
#         print (-1)
#         exit()

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

    if (i!=N and node[0] - A[i] <= 0) 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()))
s = [0]*(n+1)
y = 1
p = 0
for i in range(n+1):
    if(y-a[i] > 0):
        s[i] = y
        y -= a[i]
        y *= 2
    else:
        if(i != n):
            p = -1
            break
        elif(y == a[i]):
            s[i] = y
if(p == -1):
    print(-1)
elif(n == 0):
    if(a[0] == 1):
        print(1)
    else:
        print(-1)
else:
    q = 0
    for i in range(n+1):
        q += a[-1-i]
        if(q <= s[-1-i]):
            p += q
        else:
            p += s[-1-i]
    print(p)

Submission status: Wrong Answer

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

a = 1
answer = 1
f = 1
i = 0
while f == 1 and i < n:
    a = (a - vert[i]) * 2 #i+1で持てる頂点数
    if a <= 0:
        f = 0
        break
    else:
        answer += a
        i += 1
        
if vert[n] < a:
    answer = answer - (a - vert[n])

if f == 1:
    print(answer) 
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
saidai=[1]*(N+1)
back=[0]*(N+1)
if N!=0:
    ans=0
    saidai[0]=1
    for n in range(1,N+1):
        saidai[n]=(saidai[n-1]-A[n-1])*2
        if saidai[n]<=0:
            ans=-1
    for n in range(N+1):
        a=N-n
        if a==N:
            back[a]=A[a]
        else:
            back[a]=back[a+1]+A[a]
    if ans!=-1:
        for n in range(N+1):
            a=N-n
            if saidai[a]>back[a]:
                ans+=back[a]
            else:
                ans+=saidai[a]
    print(ans)

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

Submission status: Wrong Answer

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

for i in range(n):
  if a[i]>x-1:
    print(-1)
    exit()
  ans+=x
  x-=a[i]
  if i<n-1 and x<=0:
    print(-1)
    exit()
  if s>=0:
    if s>=x:
      s-=x
      x=x*2
    else:
      x=(x-s)+s*2
      s=0
ans+=a[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    print(0 if A_N[0] == 1 else -1)
    exit()

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

Submission status: Wrong Answer

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

nodes = [0] * (N + 1)
nodes[0] = 1 - A[0]

if all([a == 0 for a in A]):
    print(-1)
else:
    for index, a in enumerate(A[1:], start=1):
        nodes[index] = nodes[index - 1] * 2 - a
        if nodes[index] < 0:
            print(-1)
            break
    else:
        fixed_nodes = [0] * (N + 1)
        fixed_nodes[-1] = A[-1]
        for i in reversed(range(N)):
            if nodes[i] * 2 < fixed_nodes[i + 1]:
                print(-1)
                break
            fixed_nodes[i] = min(nodes[i], fixed_nodes[i + 1])
            fixed_nodes[i] += A[i]
        else:
            print(sum(fixed_nodes))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
a_list_r = a_list[::-1]
ruisekiwa = [a_list_r[0]]
for i in range(1,n+1):
  ruisekiwa.append(ruisekiwa[-1] + a_list_r[i])
ruisekiwa = ruisekiwa[::-1]
max_leaf = a_list[-1]
count = 0
check = True
node = 0
for i in range(n):
  if i == 0:
    if  n == 0 and a_list[0] == 1:
      count = 1
      break
    elif a_list[0] != 0:
      check = False
      break
    else:
      count = 1
      node = 1
  else:
    cand = 2 * node
    if cand < a_list[i]:
      check = False
      break
    node = min(ruisekiwa[i+1],2*node - a_list[i])
    count += node + a_list[i]
if check == False:
  print(-1)
else:
  print(count + a_list[-1])

Submission status: Wrong Answer

Solution code:
DoesExist = True

N = int(input())
As = input().split()

for i in range(len(As)):
    As[i] = int(As[i])

for num in range(len(As)):
    if As[num] > 2**num - 1:
        DoesExist = False

nodes_num = 0
nodes_limit = []

def nibungi():
    global nodes_num, nodes_limit, As
    nodes_num += N
    for i in range(len(As)):
        nodes_num += As[i]
    print(nodes_num)
    
if DoesExist == False:
    print("-1")
    
else:
    nibungi()

Submission status: Wrong Answer

Solution code:

from math import ceil
N = int(input())
A = list(map(int, input().split()))
if(A[0] != 0):
    print(-1)
    exit(0)
# curは作り出せる最大ノード数
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):
    if(A[i] > cur):
        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)

'''

Submission status: Wrong Answer

Solution code:
import sys
import math


def input():
    return sys.stdin.readline()[:-1]

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

sumA = sum(A) - 1
vert = [1]
bool_ = 0
for i,a in enumerate(A):
	#print(i, a, sumA)
	if a > 2**i:
		bool_ = 1
		break
	
	if i == 0:
		if a != 0:
			bool_ = 1
			break
	else:
		if sumA > 0:
			if sumA > vert[i-1]:
				sumA -= vert[i-1]
				#print(vert[i-1]*2 - a)
				if vert[i-1]*2 - a < 0:
					bool_ = 1
					break
				else:
					vert.append(vert[i-1]*2 - a)
			else:
				if sumA*2 + vert[i-1]-sumA - a < 0:
					bool_ = 1
					break
				else:
					vert.append(sumA*2 + vert[i-1]-sumA - a)
					sumA = 0
		else:
			if vert[i-1]- a < 0:
				bool_ = 1
				break
			else:
				vert.append(vert[i-1] - a)

#print(vert)
if bool_ == 1 or vert[-1] != 0 or A[-1] == 0:
	print(-1)
else:
	print(sum(vert) + sum(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = sum(a)
if a[0] != 0:
    print(-1)
    exit()
if n == 1:
    print(a[1]+1)
    exit()
l = 1
ans = 1
for i in range(n):
    x = a[i+1]
    if x > l*2:
        print(-1)
        exit()

    if m >= l*2:
        ans += l * 2
        l *= 2
    else:
        ans += m
        l = m
        #gr = False
    if x > 0:
        m -= x
        l -= x
        if m < 0:
            print(-1)
            exit()
print(ans)

Submission status: Wrong Answer

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

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


cnt = 1
roots = 1
for i in range(N):
    roots = roots * 2
    k = sum(A[i+1:])
    if roots > k:
        roots = k

    if roots - A[i+1] < 0:
        print("-1")
        exit()

    cnt += roots
    roots -= A[i+1]
print(cnt)

Submission status: Wrong Answer

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


mod = 1000000007


def combinations_count_mod(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x, y: x*y % mod, range(n, n - r, -1), 1)
    denom = pow(reduce(lambda x, y: x*y % mod, range(1, r + 1), 1), mod-2, mod)
    return numer * denom % mod


def solve(n,a):
    miki = [1] + [0 for _ in range(n)]
    for i in range(0, n):
        eprint('i,a[i] , miki[i], a[i] + miki[i] ',end=':\n')
        eprint(i,a[i] , miki[i], a[i] + miki[i])
        if a[i] + miki[i] > 2**i:
            return(-1)
        else:
            if a[i+1] + (miki[i] * 2) < 2**(i+1):
                miki[i+1] = miki[i] * 2
            elif a[i+1] + miki[i] < 2**(i+1):
                miki[i+1]=2**(i+1) - a[i+1] - 1  # miki[i] * 2
            else:
                return 0
    return(sum(miki+a))

n = int(input().strip())
a = list(map(int, input().strip().split()))
print(solve(n,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+=a[0]

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if A[0]!=0:
    print(-1)
    exit()
else:
    C=[0]*(N+1)
    C[0]=1
    for i in range(1,N-1):
        if C[i-1]*2-A[i]<0:
            print(-1)
            exit()
        else:
            C[i]= C[i-1]*2-A[i]
        
    print(sum(A)+sum(C)+A[N])

Submission status: Wrong Answer

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

"""
crt = 0
ttl = 0
for i in range(n,0,-1):
  crt += a[i]
  ttl+= crt
  print(crt)
  crt = crt // 2 + crt % 2
  print("next:{}".format(crt))
if crt!=1:
  print(-1)
else:
  print(ttl)
"""

ans = 0
ls = [0 for _ in range(n+1)]
crt = 1
ttl = 1
for i,l in enumerate(a):
  ls[i] = crt
  if i!=n and crt - l < 1:
    ans =-1
    break
  if i == n:
    break
  crt = (crt-l)*2
  #print("crt{}".format(crt))
  ttl += crt
  #print("ttl{}".format(ttl))

crt = 0
for i in range(n,0,-1):
  #print("ls")
  #print(ls[i])
  #print(a[i])
  #print(crt)
  if ls[i] - a[i] - crt > 0:
    ttl -= (ls[i] - a[i] - crt)
    crt = a[i] + crt
  else:
    crt = ls[i]

if ans == -1:
  print(ans)
else:
  print(ttl)

Submission status: Wrong Answer

Solution code:
N =int(input())
A = list(map(int,input().split()))
leaf = sum(A)
if A[0] != 0:
    print(-1)
    exit()
v = [[0,a] for a in A]
v[0][0] = 1
MAX = 2
for i in range(1,N+1):
    v[i][0] = min((v[i-1][0]-v[i-1][1])*2,leaf)
    leaf -= v[i][1]
    MAX *= 2

if v[N] != v[N]:
    print(-1)
    exit()

ans = 0
for a,b in v:
    if a <= 0:
        print(-1)
        exit()
    ans += a

print(ans)
v

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush


def solve():
    n = II()
    A = LI()
    # print(A)

    R = A[::-1]

    # max_root_num == child_node_num
    def dfs(max_root_num, min_root_num, depth, max_node, ans):
        leaf = A[depth]
        # print(depth, max_root_num, min_root_num, leaf, ans, max_node)
        if min_root_num + leaf > max_node:
            # print('    No')
            return
        if depth == 0:
            for root_num in range(max_root_num, min_root_num-1, -1):
                if root_num + leaf > max_node: continue
                print(ans + root_num + leaf)
                sys.exit()

        for root_num in range(max_root_num, min_root_num-1, -1):
            # print('  rr', root_num, leaf)
            if root_num + leaf > max_node: continue
            if root_num * 2 < max_root_num: return
            dfs(root_num + leaf, ceil(root_num/2), depth-1, max_node // 2, ans + root_num + leaf)

    bottom_leaf = A[-1]
    dfs(bottom_leaf, ceil(bottom_leaf / 2), n-1, pow(2, n-1), bottom_leaf)

    print(-1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
a = LI()
for i in range(n):
    if a[i] > 2**i - 1:
        print(-1)
        quit()
if a[-1] > 2**n:
    print(-1)
    quit()

lst = [1]
for i in range(1, n+1):
    l = lst[-1] - a[i-1]
    if l <= 0:
        print(-1)
        quit()
    lst.append(2*l)
i = n-1
tmp = a[-1]
ans = 0
lst2 = [a[-1]]
while i >= 0:
    tmp += a[i]
    tmp = min(tmp, 2**i)
    lst2.append(tmp)
    i -= 1
lst2 = lst2[::-1]
for i in range(n+1):
    ans += min(lst[i], lst2[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import math


def solve(N, As):
    # print(N, ", ", As)
    prev_leaf = 0
    branch_maxes = []
    branch_mines = []
    for i, a in enumerate(As[::-1]):
        if i == 0:
            branch_maxes.append(0)
            branch_mines.append(0)
        else:
            n = N - i
            branch_maxes.append(min(2 ** n, math.ceil(branch_maxes[-1] + prev_leaf)))
            branch_mines.append(math.ceil((branch_mines[-1] + prev_leaf) / 2))
        prev_leaf = a

    branch_maxes = branch_maxes[::-1]
    branch_mines = branch_mines[::-1]
    # print(f"leaf :         {As}")
    # print(f"branch_maxes : {branch_maxes}")
    # print(f"branch_mines : {branch_mines}")
    prev_branch = 1
    branches = []
    for i in range(N):
        if i == 0:
            branch = prev_branch - As[i]
        else:
            branch = max(min(prev_branch * 2 - As[i], branch_maxes[i]), branch_mines[i])
            if (branch + As[i]) > branches[-1] * 2:
                return -1
        if branch == 0:
            return -1

        prev_branch = branch
        branches.append(branch)
    branches.append(0)
    # print(f"branches :     {branches}")
    # print(f"ans : {sum(branches) + sum(As)}")
    return sum(branches) + sum(As)


# solve(4, [0, 0, 1, 0, 2])
# solve(3, [0, 1, 1, 2])
# #
# assert (solve(4, [0, 0, 1, 0, 2]) == 10)
# assert (solve(3, [0, 1, 1, 2]) == 7)
# assert (solve(10, [0, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]) == 264)
# assert (solve(2, [0, 3, 1]) == -1)
# assert (solve(1, [1, 1]) == -1)
# print("OK")

if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    print(solve(N, As))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = 1
c = [1-a[0]]+[1]*(n)
# print(c)
if a[0] == 1 and n >= 1:
    print(-1)
    exit()
for i in range(1,n+1):
    c[i] = c[i-1]*2-a[i]
    # print(i)
    if c[i] < 0:
        # print(c)
        print(-1)
        exit()
c[n] = 0
m = a[n]
for i in range(n-1,-1,-1):
    c[i] = min(c[i],m)
    m+=a[i]
# print(c)
print(sum(a)+sum(c))
# b = [0]*(n) + [a[-1]]
# for i in range(n-1,-1,-1):
#     b[i] = min(b[i+1]+a[i],2**(i))
# print(b)

Submission status: Wrong Answer

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

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

#rint(lis)



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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

for i in range(n+1):
    d += (1+i)*a[i]
    
k = sum(a)-1
d = d - 1/2*k*(k+1)

if d < 2:
    print('-1')
else:
    print(int(d))

Submission status: Wrong Answer

Solution code:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    print(A_N[0])
    exit()

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