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:
import sys
import numpy
n=int(input())
a=input()
a=a.split()
M=1
m=int(a[n])
Ml=list()
ml=list()
Ml.append(M)
ml.append(m)
Q=0
if int(a[0])>=1:
    print(-1)
    sys.exit()
for i in range(n):
    M=2*M-int(a[i+1])
    if M<0:
        print(-1)
        sys.exit()
    M1=M+int(a[i+1])
    Ml.append(M1)
    m=m+int(a[n-i-1])
    ml.insert(0,m)
numpy.array(Ml)
numpy.array(ml)
Q1=numpy.minimum(Ml,ml)
Q1=sum(Q1)
print(Q1)

Submission status: Wrong Answer

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

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

lief = [0 for i in range(n+1)]
root = [0 for i in range(n+1)]
lief[0], root[0] = 1, 1

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

else:
    flag = True
    for i in range(1, n+1):
        lief[i] = root[i-1] * 2 if root[i-1] * 2 <= limit[i] else limit[i]
        root[i] = lief[i] - a[i] if i != n else a[i]
        if root[i] < 0:
            flag = False
            break
    print(sum(lief) if flag else -1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

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


for i in range(n):
    if (ans[i+1]+1)//2 + a[i] > ans[i]:
        # print(ans[i+1])
        print(-1)
        exit()
if ans[-1] != a[-1]:
    print(-1)
    exit()

print(sum(ans))

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]

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

Submission status: Wrong Answer

Solution code:

def resolve():
  N = int(input())
  if N == 0:
    print(-1)
    return True
  A = [int(x) for x in input().split(" ")]
  max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # 各 depth における最小値
  min_node_in_depth = [0] * (len(A))
  min_node_in_depth[-1] = max_node_in_depth[-1]
  index = -1
  for i in range(1, len(A)):
    min_node_in_depth[index] = -(-min_node_in_depth[index + 1] // 2) + A[index]
    index = index - 1

  result = 1
  recent = 1
  for i in range(1, len(A)):
    num_of_node = (recent - A[i - 1]) * 2
    if num_of_node < min_node_in_depth[i]:
      print(-1)
      return True

    if num_of_node <= max_node_in_depth[i]:
      result += num_of_node
      recent = num_of_node
    else:
      result += max_node_in_depth[i]
      recent = max_node_in_depth[i]

  print(result)


if __name__ == "__main__":
    resolve()

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()

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

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:
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 A[0]!=0:
        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:
import numpy as np

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

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

arr = np.zeros(n+1) # その深さのノード数
arr[0] = 1

ruiseki = np.zeros(n+2) # その深さのノード数
ruiseki[0] = 1

possible = np.zeros(n+1) # その深さの子を生やせるノード数
possible[0] = 1
aki = 1
start = 0
for i in range(1, n+1):
    arr[i] += 1
    ai = a[i]
    if i == n: ai -= 1
    while ai > 0:
        if possible[aki-1] != 0:
            ruiseki[aki] += 1
            ruiseki[i+1] -= 1
            possible[aki-1] -= 1
            ai -= 1
        else:
            while start < aki:
                ruiseki[start+1] += ruiseki[start]
                start += 1
            possible[aki] = (ruiseki[aki]-a[aki])*2 - (ruiseki[aki] + ruiseki[aki+1])
            aki += 1
        if aki > i:
            print(-1)
            exit()

while start < n+1:
    ruiseki[start+1] += ruiseki[start]
    start += 1
print(int(ruiseki.sum())-1)

Submission status: Wrong Answer

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 n==1 and a[1]<2: ans = -1
print(ans)

Submission status: Wrong Answer

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

if N>0 and alist[0]>0:
  print(-1)
  sys.exit(0)

#pow2d=1<<N
blist=[0]*(N+1)
for d in reversed(range(1,N+1)):
  if d>50:
    blist[d-1]=alist[d]+blist[d]
  else:
    blist[d-1]=min(alist[d]+blist[d],(1<<(d-1))-alist[d-1])
  if blist[d-1]<0:
    print(-1)
    sys.exit(0)
  #pow2d>>=1
  
#print(alist,blist)
cmax_bu=[0]*(N+1)
for d in range(N+1):
  cmax_bu[d]=alist[d]+blist[d]
#print(cmax_bu)

pow2d=1
blist=[0]*(N+1)
if alist[0]==0:
  blist[0]=1
for d in range(1,N+1):
  if pow2d<10**10:
    pow2d<<=1
    c=min(2*blist[d-1],pow2d,cmax_bu[d])
  else:
    c=min(2*blist[d-1],cmax_bu[d])
  blist[d]=c-alist[d]
  if blist[d]<0:
    print(-1)
    sys.exit(0)
#print(alist,blist)

answer=0
for i in range(N+1):
  answer+=alist[i]+blist[i]
  
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    a = list(map(int, input().split()))
    maxnum = [0] * (n + 1)
    num = [0] * (n + 1)
    maxnum[0] = 1
    num[0] = 1
    if n > 0:
        num[-1] = a[-1]

    if a[0] > 0 and n >= 1:
        print(-1)
    elif a[0] == 1 and n == 0:
        print(1)
    elif n == 0 and a[0] == 0:
        print(-1)
    elif n == 1 and a[1] == 0:
        print(-1)
    elif n == 1 and a[1] == 1:
        print(2)
    elif n == 1and a[1] == 2:
        print(3)
    else:
        for i1 in range(1, n + 1):
            if maxnum[i1-1] * 2 < a[i1]:
                print(-1)
                sys.exit()
            else:
                maxnum[i1] = maxnum[i1-1] * 2 - a[i1]

        for j1 in range(n-1, 0, -1):
            numt = a[j1] + min(num[j1 + 1], maxnum[j1-1]*2 - a[j1])
            num[j1] = numt
        r = sum(num)
        print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

L[0]=1
for i in range(1,n+1):
    L[i]=min((L[i-1]-a[i-1])*2, L[i])
    if L[i]<a[i]:
        ans=-1
        break
else:
    ans=sum(L)
    if a[0]==1 and n!=0:
        ans=-1
for i in range(n,0,-1):
    if L[i]//2 > L[i-1]:
        ans=-1
        break
print(ans)

Submission status: Wrong Answer

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

ans = 0
h = 1
tree = [1]
for i in range(1,n+1):
    if p[i] > h:
        print(-1)
        quit()
    tree.append(tree[i-1]*2-p[i]-p[i-1]*2)
    h *= 2

ans = 0
tree = list(reversed(tree))
p = list(reversed(p))
tree[0] = p[0]
for i in range(1,n+1):
    if p[i] == 0:
        tree[i] = tree[i-1]
    if pow(2,i) > tree[i]:
        tree[i] = min(pow(2,(n-i)),tree[i])
print(sum(tree))

Submission status: Wrong Answer

Solution code:
import sys

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

ch = [0] * (n+1)
pa = [0] * (n+1)
pa[0] = 0 if a[0] == 1 else 1
t = 2
for i in range(1,n+1):
    ch[i] = 2*ch[i-1] + a[i]
    pa[i] = t - ch[i]
    t *= 2

ans = 0
chi = a[n]
for i in reversed(range(n)):
    if pa[i]*2 < chi:
        print(-1)
        sys.exit(0)
    ans += chi
    chi = min(chi + a[i], pa[i] + a[i])
print(ans + 1)

Submission status: Wrong Answer

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

elif N == 2:
  if A == [0,1,1]:
    ans = 4
  elif A == [0,1,2]:
    ans = 5
  elif A == [0,0,2]:
    ans = 5
  elif A == [0,0,3]:
    ans = 6
  elif A == [0,0,4]:
    ans = 7
  else:
    ans = -1

else:
  TOP = [0 for _ in range(len(A))]
 
  impossible =0
  TOP[0] = 1
 
  for n in range(len(A)-1):
    max_TOP = TOP[n] * 2 - A[n+1]
 
 
    if n != len(A)-2:
      if max_TOP <= 0:
        impossible = 1
        break
      else:
        TOP[n+1] = max_TOP
    else:
      if max_TOP < 0:
        impossible = 1
        break
      else:
        TOP[-1] = TOP[-2]*2
 
  if impossible == 0:
    if TOP[-1] != A[-1]:
      ans = sum(TOP)+sum(A)-TOP[-1]
      cuts = TOP[N] - A[N] - TOP[N-1]
      for n in range(N,2,-1):
        if cuts <= 0:
          break
        else:
          ans -= cuts
          cuts = cuts- TOP[n-2]
    else:
      ans = sum(TOP)+sum(A)-TOP[-1]
  else:
    ans = -1
  
  
print(ans)

Submission status: Wrong Answer

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

internal_max = [1]*(n+1)
internal_max[0] = 1-As[0]

for i in range(1,n+1):
    internal_max[i] = 2*internal_max[i-1]-As[i]

depth_sum = [0]*(n+1)
depth_sum[n] = As[n]
judge = False

for i in range(n-1, -1, -1):
    if depth_sum[i+1] > internal_max[i]*2:
        judge = True
        break
    else:
        depth_sum[i] = As[i] + min(internal_max[i], depth_sum[i+1])

if judge:
    print(-1)
else:
    summa = 0
    for i in depth_sum:
        summa += i
    print(summa)

Submission status: Wrong Answer

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

if A[0] != 0 or A[N] == 0:
    print(-1)
else:
    B = [0]*(N+1)
    C = [0]*(N+1)
    B[0] = 1
    C[N] = A[N]
    for i in range(1,N+1):
        B[i] = (B[i-1]-A[i-1]) * 2
        C[N-i] = C[N+1-i]+A[N-i]
    sum = 0
    flag = True
    for i in range(0,N+1):
        sol = min(B[i],C[i])
        if (i < N and sol <= A[i]) or (i == N and sol != A[N]): 
            flag = False
            break
        sum += sol
    if flag == True:
        print(sum)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if a[0] != 0:
    print(-1)
    quit()
    
two = [0] * (n + 1)
two[0] = 1
for i in range(1, n + 1):
    two[i] = two[i - 1] * 2

s = [0] * (n + 1)
s[0] = 1
for i in range(1, n + 1):
    s[i] = s[i - 1] + two[i]
  
sum_ = s[n]
for i in range(1, n):
    if a[i] >= 2:
        print(-1)
        quit()
    if a[i] == 1:
        index = n - i
        sum_ -= s[index] - 1
print(sum_)

Submission status: Wrong Answer

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

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

lief = [0 for i in range(n+1)]
root = [0 for i in range(n+1)]
lief[0], root[0] = 1, 1

flag = True
for i in range(1, n+1):
    lief[i] = root[i-1] * 2 if root[i-1] * 2 <= limit[i] else limit[i]
    root[i] = lief[i] - a[i] if i != n else a[i]
    if root[i] < 0:
        flag = False
        break
    print(i, root[i-1] * 2, limit[i], lief[i], a[i], root[i])

print(sum(lief) if flag else -1)

Submission status: Wrong Answer

Solution code:
a=[0]*100010
mx=[0]*100010
num=[0]*100010

n =int(input())
flag=1
last =int(0)
now = int(0)
a =list(map(int,input().split()))
if a[0]==0 :
    last=1
else:
    last=0
for i in range(n):
    j=i+1
    now =2*last
    if j<n:
        mx[j]=now-a[j]
        last = now -a[j]
    else :
        mx[j]=now

if mx[n]<a[n]:
    flag=0

res=int(a[n])
down=int(a[n])
mx[0]=1

for i in range(n):
    j=n-1-i
    miup =(down+1)//2
    if miup >mx[j]:
        flag=0
    now = min(mx[j],down)
    now+=a[j]
    res+=now
    num[j]=now
    down=now

for i in range (min(n+1,31)):
    if num[i]>pow(2,i):
        flag =0
if flag:
    print(res)
else :
    print(-1)

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()

Submission status: Wrong Answer

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

able = True
count = 0
if A[0] > 1:
  able = False
else:
  bb = 1-A[0]
  count += 1
  for a in A[1:]:
    print(count)
    b = 2*bb - a
    if 0 <= b and b <= 2*bb:
      count += 2*bb
      bb = b
    else:
      able = False
      break
if able:
  print(count)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_l = list(map(int,input().split()))
if a_l[0] > 0:
    print(-1)
    quit()
ans = 0
graph_1 = []
graph_1.append(1)
for i in range(1,n):
    a = graph_1[i-1]*2 - a_l[i]
    graph_1.append(a)
graph_1[-1] = a_l[-1]

for i in range(1,n):
    if graph_1[-i] + a_l[-i-1] <= graph_1[-i-1]:
        graph_1[-i-1] = graph_1[-i] + a_l[-i-1]
    elif (graph_1[-1]+1)//2 + a_l[-i-1] <= graph_1[-i-1]:
        graph_1[-i-1] = (graph_1[-1]+1)//2 + a_l[-i-1]
    elif graph_1[-1] + a_l[-i-1] > graph_1[-i-1]*2:
        print(-1)
        quit()
        break
print(sum(a_l)+sum(graph_1))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = A[::-1]
ans = 1
keep = 0
check = 1
for i in range(n):
    if (keep + B[i]) >= 2**(n - i + 1):
        check = 0
    ans += min((B[i] + keep), 2**(n - i))
    keep = min((B[i] + keep), 2**(n - i))
if (B[-1] + keep - 1) // 2 != 1:
    check = 0
print([-1, ans][check])

Submission status: Wrong Answer

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

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

tree = [0]*(n+1)
tree[0] = 1
for i in range(1,n+1):
    tree[i] = (tree[i-1] - a_l[i-1]) * 2
# print(tree)

if tree[-1] < a_l[-1]:
    print(-1)
    exit()

# print(tree)
tree[-1] = a_l[-1]
for i in range(2,n+2):
    # print(i, tree[-i], tree[-(i-1)] + a_l[-i])
    if tree[-i] == tree[-(i-1)] + a_l[-i]:
        break
    else:
        tree[-i] = min(tree[-i], tree[-(i-1)] + a_l[-i])
    # print(tree)
# print(tree)

# while tree[-1] != a_l[-1]:
#     tree[-1] -= 1
#     i = 1
#     while True:
#         i += 1 
#         if tree[-(i-1)] >= (tree[-i] - a_l[-i]):
#             break
#         tree[-i] -= 1
# print(tree)

ans = 0
for val in tree:
    ans += val
print(ans)

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:
        res = -1
        
    if res == 0:
        print(sum(max_node))
    else:
        print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.buffer.readline

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

c = 1
ans = 1

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

# 数える
A = A[::-1]

cnt = A[0]
c = A[0]

can = [A[0]]

for i in range(1, N + 1):
    c += A[i]

    if c > 2**(N - i):
        c = 2**(N - i)

    cnt += c
    can.append(c)

can = can[::-1]
A = A[::-1]

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

print(sum(can) if A[-1] == can[-1] else -1)

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()

if N == 2:
    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: Wrong Answer

Solution code:
n = int(input())
a_l = list(map(int,input().split()))
if a_l[0] > 0:
    print(-1)
    quit()
ans = 0
graph_1 = []
graph_1.append(1)
for i in range(1,n):
    a = graph_1[i-1]*2 - a_l[i]
    graph_1.append(a)
graph_1[-1] = a_l[-1]

for i in range(1,n):
    if graph_1[-i] + a_l[-i-1] <= graph_1[-i-1]:
        graph_1[-i-1] = graph_1[-i] + a_l[-i-1]
    elif (graph_1[-1]+1)//2 + a_l[-i-1] <= graph_1[-i-1]:
        graph_1[-i-1] = (graph_1[-1]+1)//2 + a_l[-i-1]
    elif graph_1[-1] + a_l[-i-1] > graph_1[-i-1]*2:
        print(-1)
        quit()
        break
print(sum(a_l)+sum(graph_1))


    


print(graph_1)
print(a_l)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

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

Rev_A = list(reversed(A))

num = 0
d = N
bran = Rev_A[0]
flag = True

for i in range(N-1):
    num += Rev_A[i]
    max_bran = 2**d
    if bran/2 > max_bran:
        flag = False
        break
    if bran > max_bran:
        bran = max_bran
    num += bran 
    d -= 1


if flag == True:
    print(num)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()


show_flg=False
show_flg=True
ans=0


n=I()
a=LI()
b=a[:]
c=[0]*(n+1)

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

#ans=(1<<(n+1))-1
ans=sum(b)

t=1
#show(t)
for i in range(n):
    
    if c[i]+a[i]>l[i]*2:
        l[i+1]=l[i]*2-a[i]
    else:
        l[i+1]=l[i]*2-a[i]
    l[i+1]=min(l[i]*2-a[i],t-a[i])
    if i+1==n:
        l[i+1]=0
    
    if a[i]+1>t:
        print(-1)
        exit()
    x=max(a[i]+c[i]-t,0)
    ans-=x
    #show(t,x,ans)

    t<<=1

ans=sum(l)+sum(a)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = a[-1]
now = 0
for i in range(n, -1, -1):
    if 2**i <= a[i]:
        print(-1)
        exit()
    if i == n:
        if a[i] % 2 == 0:
            now = a[i] // 2
        else:
            now = a[i] // 2 + 1
    else:
        if now % 2 == 0:
            now = now // 2 + a[i]
        else:
            now = now // 2 + 1 + a[i]
        ans += now
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = reversed(A)
counter = 0
if A[0]>=1:
    print(-1)
    exit()
for b in B:
    if b==2:
        counter += 2
    if b == 1:
        counter += 1
    
       
        

print(counter)

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

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

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


# ok[i] : 深さiの葉以外の頂点の最大数
ok = [1]
for i in range(1, n + 1):
    t = ok[i - 1] * 2 - A[i]
    if i < n and t <= 0:
        print(-1)
        exit()
    ok.append(min(t, MAX))

if ok[n] < 0:
    print(-1)
    exit()

ans = [0] * (n + 1)

ans[n] = A[n]
# 深さ[親]の許容範囲を超えないように、できるだけたくさん親を使う
for i in range(n, 0, -1):
    ans[i - 1] = min(ok[i - 1], ans[i]) + A[i - 1]
# ans[上] = min(ok[上]*2, (ans[今]+A[今]))//2

print(sum(ans))

# print(ok)
# print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
n = int(input())
a = map(int,input().split(" "))
a = [int(i) for i in a]
#print(a)
b = np.zeros(n+1)
c = np.zeros(n+1)
mxbc = np.zeros(n+1)
ans = 0
mxbc[0] = 1 - a[0]
for i in range(1,n+1):
    mxbc[i] = mxbc[i-1]*2 - a[i]
for j in range(1,n+1):
    i = n-j
    S = a[i+1]+b[i+1]+c[i+1]
    c[i] = max(0,S-mxbc[i])
    b[i] = S-2*c[i]
    if b[i] < 0 or b[i]+2*c[i] != S or b[i]+c[i] > mxbc[i] or mxbc[i] < 0:
        print(-1)
        quit()
ans = np.sum(a) + np.sum(b) + np.sum(c)
print(int(ans))

Submission status: Wrong Answer

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

if n == 0:
  flag=1
  if a[0] == 1:
    print(1)
  else:
    print(-1)
else:
  accum = [0]*n
  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:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = inpl()
non_leaf = [0] * (n + 1)
leaf = [0] * (n + 1)
MAX = a[-1]
non_leaf[0] = 1
leaf[-1] = a[-1]
dp = [0] * (n + 1)
yoyu_idx = 0
yoyu = [0] * n
yoyu_idx = -1
if a[0] == 1:
    if n == 0:
        print(1)
    else:
        print(-1)
    exit()
elif a[0] > 1:
    print(-1)
    exit()
for i in range(n - 1):
    if non_leaf[i] < a[i + 1]:
        print(-1)
        exit()
    non_leaf[i + 1] = min(MAX, non_leaf[i] * 2 - a[i + 1])
    if MAX < non_leaf[i] * 2 - a[i + 1]:
        if yoyu_idx != -1:
            tmp = a[i + 1]
            while True:
                if yoyu[yoyu_idx] >= tmp:
                    leaf[i + 1] += (i - yoyu_idx) * tmp
                    yoyu[yoyu_idx + 1] += tmp
                    yoyu[yoyu_idx] -= tmp
                    break
                else:
                    leaf[i + 1] += (i - yoyu_idx) * yoyu[yoyu_idx]
                    yoyu[yoyu_idx + 1] += tmp
                    tmp -= yoyu[yoyu_idx]
                    yoyu_idx += 1
        else:
            yoyu_idx = i
            yoyu[i] = non_leaf[i] * 2 - a[i + 1] - MAX
    leaf[i + 1] += a[i + 1]
# print(non_leaf)
# print(leaf)
# print(yoyu)
print(sum(non_leaf) + sum(leaf))

Submission status: Wrong Answer

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

def f():
    if n == 0:
        if a[0] == 1:
            return 1
        elif a[0] == 0:
            return 0
        else:
            return -1
    if a[0] != 0:
        return -1
    ans = 1
    v = 1
    for i in range(1, n + 1):
        if a[i] == 0:
            ans += 2 * v
        elif a[i] <= v:
            ans += a[i]
        else:
            v = 2 * v - a[i]
            ans += a[i] + v
    return ans
print(f())

Submission status: Wrong Answer

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

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

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

if ans == 0:
    num = 0
    for i in range(N, -1, -1):
        if L[i] == "inf" or num <= L[i]:
            num += A[i]
        else:
            num = L[i]+A[i]
        if i <= 30:
            num = min(num, pow(2, i))
        ans += num
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = [int(a) for a in map(int, input().split())]
root = [1 - A[0]]
for i in range(1, A.__len__()):
    r = root[i-1] * 2 - A[i]
    if r > 0:
        root.append(r)
    elif r == 0 and i == N:
        root.append(r)
    else:
        print(-1)
        sys.exit()
print(root)
ans = 0
for a in A:
    ans += a
for i in range(A.__len__() - 1):
    ans += min(root[i] + A[i], A[N])

print(ans)