Problem:


Score : 600 points

Problem Statement

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

Notes

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

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

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

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

Constraints

0 \leq N \leq 10^5

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

A_N \geq 1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 A_2 \cdots A_N

Output

Print the answer as an integer.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

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

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

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

Sample Output 5

264



Sample input:
3
0 1 1 2


Sample output:
7

Submission status: Runtime Error

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

sort()
sorted(reverse=true)

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

Decimal()
'''

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

Submission status: Runtime Error

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

def solve(N, A):
  if not A or A[0] != 1:
    print(-1)
    return

  prev = 1
  rt = 1
  for a in A[1:]:
    if a > prev * 2:
      print(-1)
      return
    rt += (prev * 2 - a) % (prev * 2)
    prev = a

  print(rt)

solve(N, A)

Submission status: Runtime Error

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

for i in range(1,n):
    ma1[i]=ma1[i-1]*2-a[i]

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

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = a[-1]
now = 0
bl = True
y = float("inf")
for i in range(n, -1, -1):
    if 2**i <= a[i]:
        print(-1)
        exit()
    if i == n:
        if a[i] % 2 == 0:
            if bl:
                x = i
                bl = False
            now = a[i] // 2
        else:
            now = a[i] // 2 + 1
    else:
        if now % 2 == 0:
            if bl:
                x = i
                bl = False
            now = now // 2 + a[i]
        else:
            if not bl:
                y = min(y, i)
            now = now // 2 + 1 + a[i]
        ans += now

print(ans + x - y - 1)

Submission status: Runtime Error

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)
            print(aaa)
            exit()
    d[i-1] = min(x, d[i-1]+A[i-1])
print(sum(d))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

N = int(input())

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

R = [0]*(N+1)
R[0]= 1

res = 0
k = 0
count = []

def dfs():
    global k
    k += 1
    if k == N:
        if A[k] <= 2 * R[k-1] and A[k] >= R[k-1] :
            count.append(sum(A) + sum(R))
        k -= 1
        return
    if 1 + A[k] <= 2 * R[k-1]:
        for i in range(R[k-1] - A[k], 2 * R[k-1] - A[k] + 1):
            R[k] = i
            dfs()
    k -= 1
    return

dfs()

if count == [] or (A[0] != 0 and N >= 1 ):
    res = -1
else:
    res = max(count)

print(res)

Submission status: Runtime Error

Solution code:
from numba import jit
N = int(input())
A = [int(i) for i in input().split()]

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


zero = -1

@jit
def main():
    for i in range(0, N + 1):
        if A[i] > 0:
            C = [0] * (N + 1)
            for j in range(zero + 1, i):
                B[j] += C[j]
                if A[i]==0:
                    C[j + 1] += C[j]
                    continue
                if B[j] > 0:
                    h = min(A[i], B[j])
                    B[j] -= h
                    A[i] -= h
                    C[j] += h
                    ans += h * (i - j)
                    if B[j] == 0:
                        zero = j
                C[j + 1] += C[j]
            if A[i] > 0:
                print(-1)
                exit()
    print(ans)


main()

Submission status: Runtime Error

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

sort()
sorted(reverse=true)

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

Decimal()
'''

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

Submission status: Runtime Error

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

pm = sum(A)
te = 1
if A[0] != 0 or A[N] == 0:
    print(-1)
else:
    for i in A:
        pm -= i
        e = min((e-i) * 2,pm)
        if e < 0:
            break
        te += e
    if e < 0:
        print(-1)
    else:
        print(te)

Submission status: Runtime Error

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

sort()
sorted(reverse=true)

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

Decimal()
'''

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

Submission status: Runtime Error

Solution code:
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)
elif n==0:
    print(1)
else:
    print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
A=np.array(A)
v=0
j=0
k=0
for i in reversed(range(0, N+1)):
  j+=A[i]/(2**i)
  if i==N:
    k=A[i]
  else:
    k=min(k+A[i],2**i-np.sum(np.array([A[k]*(2**(i-k)) for k in range(i)])))
  v+=k

if j>1:
  print(-1)
else:
  print(int(v))

Submission status: Runtime Error

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

l = []

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

for i in range(N+1):
    if A[i] > 2*A[i+1]:
        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()

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: Runtime Error

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1

nodeM = nodeS[0]-A[0]

laS = [0 for i in range(N+1)]

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


for i in range(N):
    nodeS[i+1] = nodeM*2
    nodeM = nodeS[i+1] - A[i+1]
    if nodeS[i] >= laS[i]:
        j = i
        break
    if i == N-1:
        if nodeS[i+1] >= laS[i+1]:
            j = i+1
        else:
            print(-1)
            exit()

for i in nodeS:
    if i < 0:
        print(-1)
        exit()

ans = sum(nodeS[:j]) + sum(laS[j:])
print(ans)

Submission status: Runtime Error

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



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

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

Submission status: Runtime Error

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

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

ind = 1
for a in A[1:-1]:
    V[ind] -= a
    if V[ind] < 0:
        print(-1)
        exit()
    V[ind+1] = V[ind] * 2
    ind += 1
# 最終的に葉を作りすぎてしまった場合はそれを裁断する
if V[N] > A[N]:
    rest_cut = V[N] - A[N]
elif V[N] == A[N]:
    print(sum(V[:N])+sum(A))
    exit()
else:
    print(-1)
    exit()
# なるべく葉を残すように選定していく
ind = N
cut = 0
while rest_cut>int(V[ind]//2) :
    rest_cut = (rest_cut)-int(V[ind]//2)
    cut += rest_cut
    ind -= 1
print(sum(V[:N])+sum(A)-cut)

Submission status: Runtime Error

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

def main():
    n = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    INF = 10**9
    g_l = [INF] * (n + 1)
    g_l[0] = 1
    if n != 0 and A[0] == 1:
        print('-1')
        return 0
    if n == 1:
        if A[0] > 3 or A[0] == 0:
            print('-1')
        if A[0] == 2:
            print('3')
        if A[0] == 1:
            print('2')
        return 0

    
    for x in range(n-1):
        max_nord = (g_l[x] - A[x]) * 2
        # 存在できるノード数の最大より葉の数の多い
        if max_nord < A[x+1]:
            print('-1')
            return 0
        g_l[x+1] = max_nord
    
    #最後の深さと葉の数が合わない場合だめ
    if g_l[-2] * 2 < A[-1]:
        print('-1')
        return 0
    g_l[-1] = A[-1]
    #print(g_l)

    for i in range(n-1, 0, -1):
        # これだけなら最多
        # 親ノードになれる最大の数 + 葉の数の場合
        if g_l[i] > g_l[i+1] + A[i]:
            g_l[i] = g_l[i+1] + A[i]
            #print(g_l)
    print(sum(g_l))
    return 0

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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



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

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

Submission status: Runtime Error

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



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

Submission status: Runtime Error

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

l = []

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

if N == ０:
    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()

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: Runtime Error

Solution code:
def step(n, lis):
  return [l+n for l in lis]

def func(lis):
  if len(lis)==0:
    return -1
  maxval = max(lis)
  lis.pop(lis.index(maxval))
  if maxval==2:
    lis.append(1)
  if maxval>2:
    lis.append(maxval-1)
    lis.append(maxval-2)
  lis.sort()
  lis = lis[:maxA]
  return [maxval,lis]
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)

lis = [0]
count = 0
ans = 0
flag=False
for i in range(N+1):
  count += 1
  if flag:
    break
  if A[i]==0:
    continue
  lis = step(count, lis)
  count=0
  a = A[i]
  #print(i,lis)
  for j in range(a):
    
    res, lis = func(lis)
    #print(i, res, lis)
    if res == -1:
      flag=True
      break
    else:
      ans += res
  
if flag:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

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

#存在するかどうか
b = 1
B=[0]*(n+1)
count = 0
for i in range(n):
    B[i] = b
    if 2*(b - A[i]) < A[i+1]:
        count += 1
    b = 2*(b - A[i])

B[n] = b

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

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

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

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

Submission status: Runtime Error

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



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

Submission status: Runtime Error

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



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

Submission status: Runtime Error

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

def main():
    n = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    INF = 10**9
    g_l = [INF] * (n + 1)
    g_l[0] = 1
    if n != 0 and A[0] == 1:
        print('-1')
        return 0
    if n == 1:
        if A[0] == 1:
            print('2')
            return 0
        if A[0] == 0:
            print('-1')
            return 0
            
    
    for x in range(n-1):
        max_nord = (g_l[x] - A[x]) * 2
        # 存在できるノード数の最大より葉の数の多い
        if max_nord < A[x+1]:
            print('-1')
            return 0
        g_l[x+1] = max_nord
    
    #最後の深さと葉の数が合わない場合だめ
    if g_l[-2] * 2 < A[-1]:
        print('-1')
        return 0
    g_l[-1] = A[-1]
    #print(g_l)

    for i in range(n-1, 0, -1):
        # これだけなら最多
        # 親ノードになれる最大の数 + 葉の数の場合
        if g_l[i] > g_l[i+1] + A[i]:
            g_l[i] = g_l[i+1] + A[i]
            #print(g_l)
    print(sum(g_l))
    return 0

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def solve(N, A):
  if not A or A[0] != 1:
    print(-1)
    return

  prev = 1
  rt = 1
  for a in A[1:]:
    if a > prev * 2:
      print(-1)
      return
    rt += (prev * 2 - a) % (prev * 2)
    prev = a
solve(N, A)
print(rt)

Submission status: Runtime Error

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



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

Submission status: Runtime Error

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

b = [1]
for i in range(n):
    tmp = b[i] - a[i]
    if tmp < 1 or tmp * 2 < a[i + 1]:
        print(-1)
        break
else:
    if n == 0:
        ans = 1 if a[0] == 1 else -1
        print(ans)
    else:
        print(sum(b))

Submission status: Runtime Error

Solution code:
feuille = 0
racine = 0
i = 0
element = 0 
while i < N+1:
    feuille = leaf[i]
    if(2**racine >= feuille):
        racine = 2**racine - feuille
        element += feuille + racine
    else:
        element = -7
        exit()
    
    i += 1
print(element)

Submission status: Runtime Error

Solution code:
N = int(input())
num = input().split()
print(num)
if N == 0:
  print(1)
else:
  for i in range(N-1):
    chk = 2**i-int(a[i])
    if int(a[i]) >= chk:
      print(-1)
      break
  	if int(a[i]) <　(chk):
      ans_list.append(int(a[i]))
    if i==N-1:
      for i in range N-1:
      	ans = ans_list[i] + (ans_list[i]//2+1)
      print(ans)

Submission status: Runtime Error

Solution code:

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

ch = [1]
t = 0
for e,i in enumerate(A):
    t+=i
    if t>=2**i:
        print(-1)
        exit()

cH = [1]
if A[0]>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 cH[0] 

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

ans = 0
n = 0
for e,i in enumerate(A[:]):
    # print(n,ch[e],-1)
    if n//2+(n%2!=0)>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)

Submission status: Runtime Error

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

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1

nodeM = nodeS[0]-A[0]

laS = [0 for i in range(N+1)]

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


for i in range(N):
    nodeS[i+1] = nodeM*2
    nodeM = nodeS[i+1] - A[i+1]
    if nodeS[i] >= laS[i]:
        j = i
        break
    if i == N-1:
        if nodeS[i+1] >= laS[i+1]:
            j = i+1
        else:
            print(-1)
            exit()

for i in nodeS:
    if i < 0:
        print(-1)
        exit()

ans = sum(nodeS[:j]) + sum(laS[j:])
print(ans)

Submission status: Runtime Error

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)
node=1
cnt=0
for i,aa in enumerate(a[::-1]):
    cnt+=min(cnt+aa,2**(i-1))

print(cnt)
    
        


                    
        


    
print(cnt)

Submission status: Runtime Error

Solution code:
a=(input() for i in range(2))

N=a[0]
A=[]
ad=a[1]#d=N+1

error=0

A_sum=0

def search(x,d):
	x/2>2**d
	error+=1

for i in range(len(ad)):
	A=ad[-(i+1)]
	a.append()

Submission status: Runtime Error

Solution code:

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

ch = [1]
t = 0
for e,i in enumerate(A):
    t+=i
    if t>2**i:
        print(-1)
        exit()

cH = [1]
if A[0]>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 cH[0] 

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

ans = 0
n = 0
for e,i in enumerate(A[:]):
    # print(n,ch[e],-1)
    if n//2+(n%2!=0)>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)

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a_li = list(map(int, input().split()))

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

N = int(input())

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

R = [0]*2**(N+1)
R[0]= 1

res = 0
k = 0
count = []

def dfs():
    global k
    k += 1
    if k == N:
        if A[k] <= 2 * R[k-1] and A[k] >= R[k-1] :
            count.append(sum(A) + sum(R))
        k -= 1
        return
    if 1 + A[k] <= 2 * R[k-1]:
        for i in range(R[k-1] - A[k], 2 * R[k-1] - A[k] + 1):
            R[k] = i
            dfs()
    k -= 1
    return

dfs()

if count == []:
    res = -1
else:
    res = max(count)

print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=np.zeros(N+1)
a=list(map(int,input().split()))
for i in range(N+1):
  A[i]=a[i]
v=0
j=0
k=0
for i in reversed(range(0, N+1)):
  j+=A[i]/(2**i)
  if i==N:
    k=A[i]
  else:
    k=min(k+A[i],2**i-np.sum(np.array([A[k]*(2**(i+1-(N-k))) for k in range(i)])))
  v+=k

if j>1:
  print(-1)
else:
  print(int(v))

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n = iinput()
a = iarr()

cum = []; sum = 0
for num in a: sum += num; cum.append(sum)

ans = 1
now = 1
for i in range(n):
    next = min(2*(now - a[i]), cum[n]-cum[i])
    now = next
    if n==i and next<0 : ans = -1; break
    if n!=i and next<=0 : ans = -1; break
    ans += next

if a[n] > 2**n: ans = -1
if a[1] < 2: ans = -1
print(ans)

Submission status: Runtime Error

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

#print(A)

maxa = [1]
for j in range(N):
    maxa.append(2*(maxa[j]-A[j]))
maxa.reverse()
#print(maxa)
A.reverse()

item = [0]
for i in range(N+1):
    if A[i]+item[i] > 2**i:
        item = (-1) * 2**50
        break
    elif A[i]+item[i] <= maxa[i]:
        item.append(A[i]+item[i])
    elif A[i] + item[i] > maxa[i]:
        item.append(maxa[i])
    

if sum(item)>0:
    print(sum(item))

else:
    print(-1)

Submission status: Runtime Error

Solution code:
a=input()
b=input()
c=b.replace(" ","")
for i in (a-1):0:
    if b[i]>=2^i:
      print(-1)

Submission status: Runtime Error

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

#print(A)

maxa = [1]
for j in range(N):
    maxa.append(2*(maxa[j]-A[j]))
maxa.reverse()
#print(maxa)
A.reverse()

item = [0]
for i in range(N+1):
    if A[i]+item[i] > 2**i:
        item = (-1) * 2**50
        break
    if A[i]+item[i] <= maxa[i]:
        item.append(A[i]+item[i])
    elif A[i] + item[i] > maxa[i]:
        item.append(maxa[i])
    

if sum(item)>0:
    print(sum(item))

else:
    print(-1)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
isOK = True
B = [0]*(N+1)
B[0] = 1-A[0]
M = 1
i = 1
while i <= N:
  B[i] = B[i-1]*2-A[i]
  i += 1
if B[i] < 0 or N > 0 and A[-1] == 0:
  isOK = False
B[-1] = A[-1]
i = N-1
while i >= 0:
  if B[i] < 1 or i > 0 and B[i] > B[i-1]*2:
    isOK = False
    break
  else:
    B[i] = min(B[i], B[i+1])+A[i]
  i -= 1
print(-1 if not isOK else sum(B))

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10 ** 9)

N = int(input())

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

R = [0]*2**(N+1)
R[0]= 1

res = 0
k = 0
count = []

def dfs():
    global k
    k += 1
    if k == N:
        if A[k] <= 2 * R[k-1] and A[k] >= R[k-1] :
            count.append(sum(A) + sum(R))
        k -= 1
        return
    if 1 + A[k] <= 2 * R[k-1]:
        for i in range(R[k-1] - A[k], 2 * R[k-1] - A[k] + 1):
            R[k] = i
            dfs()
    k -= 1
    return

dfs()

if count == []:
    res = -1
else:
    res = max(count)

print(res)

Submission status: Runtime Error

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1

nodeM = nodeS[0]-A[0]

laS = [0 for i in range(N+1)]

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


for i in range(N):
    nodeS[i+1] = nodeM*2
    nodeM = nodeS[i+1] - A[i+1]
    if nodeS[i] >= laS[i]:
        j = i
        break
    if i == N-1:
        if nodeS[i+1] >= laS[i+1]:
            j = i+1
        else:
            print(-1)
            exit()

for i in nodeS:
    if i < 0:
        print(-1)
        exit()

ans = sum(nodeS[:j]) + sum(laS[j:])
print(ans)

Submission status: Runtime Error

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


node_list = []
i = 0

flg ==3
node = 1
sum_leaf = sum(A)
for i in range(N+1):
#     print("sum_leaf", sum_leaf)
#     print("node", node)
    node_list.append(node)
    if node < A[i]:
        flg = -1
        break
    elif node == A[i]:
        flg = 0
        break
    else:
        if node < sum_leaf:
            if 2*(node-A[i])<sum_leaf:
                next_node = 2*(node-A[i])
                sum_leaf -= A[i]
                node = next_node
            else:
                sum_leaf -= A[i]
                next_node = sum_leaf
                node = next_node
        else:
            sum_leaf -= A[i]
            next_node = sum_leaf
            node = next_node
if flg ==-1:
    print(-1)
elif flg ==0:
    if len(node_list)==(N+1):
        print(sum(node_list))
    else:
        print(-1)
else:
    print(sum(node_list))