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:
depth = int(input())
vertex = input().split(' ')
vertex = [int(x) for x in vertex]

if vertex[0] == 1:
    if depth == 0:
        print(1)
    else:
        print(-1)
else:
    is_error = False
    for i in range(depth + 1):
        if vertex[i] > 2**i:
            is_error = True
            break
    
    if is_error:
        print(-1)
    else:
        maxs = []
        i = 1
        for v in vertex:
            i -= v
            maxs.append(i)
            i *= 2

        output = 0
        for i in range(depth, -1, -1):
            if i == depth:
                output += vertex[i]
                next_v = vertex[i]
            else:
                next_v = min([maxs[i], next_v]) + vertex[i]
                output += next_v
        print(output)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
nodes = [0]*(N+1)
s_d = 0 # 飽和してないノードが残ってる深さ
cap_d = 1 - A[0]
failed = False
for i, a in enumerate(A):
    # a個の葉をなるべく浅いノードから取る
    for _ in range(a):
        # これ以上分岐することろがなければ失敗
        if i < s_d or cap_d <= 0:
            failed = True
            break
        # s_dから枝をとる
        for j in range(s_d, i+1):
            nodes[j] += 1
        # s_dがいっぱいになったら深さを一つ進める
        if nodes[s_d] >= cap_d:
            cap_d -= A[s_d]
            cap_d *= 2
            s_d += 1
    if failed:
        break
print(-1 if failed else sum(nodes))

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import math

#H1, M1, H2, M2, K = map(int, input().split())
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

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

sum_a = sum(A)
count = 1
root_num = 1
count_leaf = 0

def calc_node_num(leaf_num, root_num, count_leaf, count):
    count_leaf += leaf_num
    next_root_num = min(root_num*2-leaf_num, sum_a-count_leaf)
    count += (next_root_num + leaf_num)
    return next_root_num, count_leaf, count
    
for i in range(1,N+1):
    root_num, count_leaf, count = calc_node_num(A[i], root_num, count_leaf, count)
    if root_num < 0:
        print(-1)
        break
else:
    print(count)

Submission status: Wrong Answer

Solution code:
import math
def main():
    N = int(input())
    P = list(map(int, input().split()))
    if P[0] >= 1:
        return -1
    ul = [1]
    ll = [1]
    for i, v in enumerate(P[1:]):
        u = (ul[-1] - P[i]) * 2
        l = v
        ul.append(u)
        ll.append(l)
    ul2 = [P[-1]]
    ll2 = [P[-1]]
    for i, v in enumerate(reversed(P[:-1])):
        u = min(ul2[-1] + v, pow(2, N-i-1))
        l = min(math.ceil(ll2[-1]/2) + v, pow(2, N-i-1))
        ul2.append(u)
        ll2.append(l)
    ul2.reverse()
    ll2.reverse()
    r = 0
    for i in range(N+1):
        a = ul[i]
        b = ll[i]
        c = ul2[i]
        d = ll2[i]
        if d > a or b > c:
            return -1
        if max(b, d) > pow(2, i):
            return -1
        r += min(a, c)
    return r
print(main())

Submission status: Wrong Answer

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

print(count)

Submission status: Wrong Answer

Solution code:
import sys

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

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

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

    tree = [set() for _ in range(N+1)]
    tree[0].add(1)

    for i in range(N):
        unsuitable = set()
        for ver_i in tree[i]:
            notleef = ver_i - A[i]
            if notleef <= 0:
                print(-1)
                sys.exit()
                unsuitable.add(ver_i)
                continue
            minimum = notleef
            maximum = 2 * notleef
            tree[i+1] = tree[i+1] | set([j for j in range(minimum, maximum+1)])
        tree[i] -= unsuitable
        print()

    if A[-1] in tree[-1]:
        tree[-1] = set([A[-1]])
    else:
        print(-1)
        sys.exit()
        
    print(sum([max(i) for i in tree]))

main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

if N == 0:
    if A_list[0] == 1:
        print(0)
    else:
        print(-1)
elif A_list[0] != 0:
    print(-1)
elif N == 1:
    if A_list[1] == 1 or A_list[1] == 2:
        print(A_list[1] + 1)
    else:
        print(-1)
else:
    ans = 1
    deathable_node = 1
    sum_rest_A = sum(A_list)
    for i in range(1, N + 1):
        now_A = A_list[i]
        deathable_node = min(sum_rest_A, deathable_node * 2) - now_A

        if deathable_node < 0:
            print(-1)
            break

        sum_rest_A -= now_A
        ans += deathable_node + now_A
#         print(i, now_A, sum_rest_A, deathable_node, ans)
        if deathable_node == 0 and i != N:
            print(-1)
            break
    else:
        if deathable_node == 0:
            print(ans)
        else:
            print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    An = [int(x) for x in input().strip().split()]
    total = sum(An)
    if An[0] != 0 or total == 0:
        print(-1)
        exit()
    if N == 0:
        print(1)
        exit()
    ans = 1
    node = 1
    for n, a in enumerate(An[1:], start=1):
        node_ = min(total, node * 2)
        if node_ <= 0:
            print(-1)
            exit()
        ans += node_
        node = node_ - a
        total -= a

    if node != 0:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
if a[0] != 0:
    ans = -1
p = [1-a[0]]
for i in range(n-1):
    if 2*p[-1]-a[i+1] <= 0:
        ans = -1
    p.append(2*p[-1]-a[i+1])
if n == 0 and a[0] == 1:
    print(1)
elif n == 1:
    if a[0] == 0 and a[1] == 1:
        print(2)
    elif a[0] and a[1] == 2:
        print(3)
    else:
        print(-1)
elif ans == -1:
    print(-1)
else:
    a.reverse()
    p.reverse()
    ans += a[0]
    q = a[0]
    for i in range(1,n+1):
        if q < p[i-1]:
            ans += q+a[i]
            q = q+a[i]
        else:
            ans += p[i-1]+a[i]
            q = p[i-1] + a[i]
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [sum(a)]
for i in range(n):
    b.append(b[-1] - a[i])
flag = True
if a[0] != 0:
    flag = False
else:
    count = 1
    temp = 1
    for i in range(1, n + 1):
        temp2 = min(temp * 2, b[i])
        count += temp2
        temp = temp2 - a[i]
        if temp <= 0:
            if i != n:
                flag = False
                break
if flag == True:
    print(count)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
k=sum(a)
if n==0:
    if k==0:
        print(0)
    else:
        print(-1)
    exit()
elif k==0:
    print(-1)
elif k==1:
    print(n+1)
d=(k-1).bit_length()
ans=1
e=1
for i in range(n):
    e-=a[i]
    k-=a[i]
    if e<0:
        print(-1)
        exit()
    elif e==0 and k>0:
        print(-1)
        exit()
    if 2*e<k:
        e*=2
    elif e<k:
        e=k
    #print("e",e)
    ans+=e
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
c = [0]*(n+1)
r = [0]*(n+1)
c[0] = 1
r[n] = a[n]
ans = r[n]
fl = 1
if a[0] >= 1 and n >= 1:
  fl = 0
else:
  for i in range(1,n+1):
    c[i] = min(2*c[i-1]-a[i],10**8)
    if c[i] <0:
      fl = 0
  for i in reversed(range(n)):
    r[i] = min(r[i+1]+a[i],c[i]+a[i])
    ans += r[i]
if fl == 1:
  print(ans)
else:
  print(-1)
#print('a',a)
#print('c',c)
#print('r',r)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
if lst1[0] != 0:
    print(-1)
    exit()
res2 = [0]
for i in lst1[::-1]:
    res2.append(res2[-1]+i)

res2.reverse()

INF = res2[0]
res = [1] 
res3 = [1]
for i in lst1[1:]:
    res3.append(min(INF,res[-1]*2))
    res.append(min(INF,res[-1]*2-i))

#案2
for i in range(len(res)):
    if i == len(res)-1:
        break
    if res[i] <= 0:
        print(-1)
        exit()

ans = 0
res2 = res2[:-1]
for i in range(len(res3)):
    ans += min(res2[i],res3[i])
print(ans)
"""print(*res)
print(*res3)
print(*ans)
"""

Submission status: Wrong Answer

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

lim = [0]*(n+1)
for i in range(n):
    if i == 0:
        lim[i] = 1
    else:
        lim[i] = lim[i-1]*2 - al[i]
lim[-1] = lim[-2]*2
al = al[::-1]
lim = lim[::-1]

ansl = []
# print(al, lim)

for i in range(n+1):
    if i == 0:
        if al[i] <= 2**n:
            ansl.append(al[i])
    else:
        ansl.append(min(ansl[i-1]+al[i], lim[i]+al[i]))
for l in lim:
    if l <= 0:
        print(-1)
        exit()
print(sum(ansl))

Submission status: Wrong Answer

Solution code:
def main():
    #h,M,h2,M2,K=map(int,input().split())
    N=int(input())
    A=list(map(int,input().split()))
    if N==0 and A[0]!=1:
        print(-1)
        return 
    if N!=0 and A[0]!=0:
        print(-1)
        return 
    ans=1
    tmp=[0]
    for i,v in enumerate(A[1:][::-1]):
        tmp.append(tmp[-1]+v)
    tmp.pop(0)
    t=1
    for i,v in enumerate(tmp[::-1]):
        t*=2
        if A[i+1]==0:
            if t >= v :
                ans+=v
                t=v
            else:
                ans+=t
        else:
            if t < A[i]:
                print(-1)
                return
            t=min(t,v)
            ans+=t
            t-=A[i+1]
    print(ans)


main()

Submission status: Wrong Answer

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

ok = True
max_l =[1-A[0]]

for i in range(1,N+1):
    max_l.append(max_l[i-1] * 2 - A[i])
    if max_l[i] < 0 :
        ok=False

ans = A[N]
now = A[N]

for i in reversed(range(N)):
    now_l = min(now,max_l[i])
    now = now_l + A[i]
    ans += now

if ok == False:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

cnt=[]
now=0
for i in reversed(range(n+1)):
    now+=a[i]
    cnt.append(now)

cnt.reverse()

ans=sum(cnt)
nxt_max=1
for i in range(len(cnt)):
    c=cnt[i]
    if c > nxt_max:
        ans-=(c-nxt_max)
    else:
        nxt_max=c
    nxt_max-=a[i]
    nxt_max*=2
    if i!=len(cnt)-1 and nxt_max <=0:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
k=l[n]
count=1
sumleaf=1
flag=True
if l[0]>2 or l[0]==1 and n>=1:
    flag=False
else:
    for i in range(1,n+1):
        sumleaf*=2
        if i==n and sumleaf<k:
            flag=False
            print(-1)
            break
        elif i==n:
            count+=k
        else:
            if sumleaf<=l[i]:
                flag=False
                print(-1)
                break
            else:
                if sumleaf-l[i]>k:
                    sumleaf=k+l[i]
                count+=sumleaf
                sumleaf-=l[i]
if flag==True:
    print(count)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    #if A[0] != 0:
        #print(-1)
        #return
    piyo = 1
    work = [1]
    for a in A[1:]:
        piyo *= 2
        work.append(piyo)
        piyo -= a
    result = 0
    piyo = 0
    i = N
    for a in A[::-1]:
        piyo += a
        if a > work[i]:
            print(-1)
            return
        piyo = min(piyo, work[i])
        result += piyo
        i -= 1
    print(result)
main()

Submission status: Wrong Answer

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

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

flag=0
ans,point=[1],1
for i in range(1,n+1):
    if flag==0:
        point *=2
    if point>=sum_A:
        point=sum_A
        flag=1
    ans.append(point)
    if point<=0 or sum_A<=0:print(-1);exit()
    point -=A[i]
    sum_A -=A[i]
print(sum(ans))

Submission status: Wrong Answer

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


## 最大で使用できる枝の数を計算する
alloc = 0
EDA = [0]
for idx in range(N+1):
  # max branches
  if idx == 0:
    EDA.append(1-A[idx])
    alloc = 1-A[idx]
  else:
    EDA.append(2 * alloc - A[idx])
    alloc = 2 * alloc - A[idx]
  if alloc < 0:
    print(-1)
    break
else:
  print(EDA)
  ## 其処に存在する葉以外の頂点の数がmax
  edasum=0
  eda = 0
  for idx in range(N+1) :
    max_leaves = 2 * EDA[-1-idx-1]
    # 枝と葉の合計をallocとする
    eda = min(eda+A[-idx-1], max_leaves)
    edasum += eda
  else:
    print(edasum+1)

Submission status: Wrong Answer

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

s = 1
if n == 0:
    if a[0] != 1:
        print(-1)
        quit()
    else:
        print(1)
        quit()
elif a[0] > 0:
    print(-1)
    quit()
memo = [[0,0] for _ in range(n+1)]
memo[0] = [0,1]
for i in range(1,n+1):
    if s == 0:
        print(-1)
        quit()
    s = memo[i-1][1]*2
    if s > 10**10:
        s = 10**10
    memo[i][0] = a[i]
    memo[i][1] = s-a[i]
    if s-a[i] < 0:
        print(-1)
        quit()
ans = [[a[i],0] for i in range(n+1)]
for i in range(n-1,-1,-1):
    if (ans[i+1][0]+ans[i+1][1]) > memo[i][1]*2:
        print(-1)
        quit()
    else:
        ans[i][1] = min(memo[i][1],ans[i+1][0]+ans[i+1][1])
s = 0
for i in range(n+1):
    s += sum(ans[i])
print(s)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math

N = int(input())

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

n_not_leaf = 0
sum_node = 0

num_node = [0 for d in range(N+1)]
max_node = [0 for d in range(N+1)]

# 各層のnodeのmax個を計算
for d in range(N+1):
    if d == 0:
        max_node[0] = 1
    else:
        max_node[d] = (max_node[d-1]-A[d-1])*2
    
    if d != N and max_node[d]-A[d] < 1:
        print(-1)
        exit()

for d in reversed(range(N+1)):
    if d == N:
        num_node[N] = A[N]
    else:
        if num_node[d+1]/2+A[d] > max_node[d]:
            print(-1)
            exit()
        else:
            num_node[d] = min(num_node[d+1]+A[d], max_node[d])

print(sum(num_node))

Submission status: Wrong Answer

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

print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
sums=[0]*(n+1)
node=[0]*(n+1)
p=list(map(int,input().split()))
flag=True

sums[n]=p[n]
for i in reversed(range(n)):
    sums[i]=p[i]+sums[i+1]

node[0]=1
check=-1
for i in range(1,n+1):
    if node[i-1]-p[i-1]<=0:
        flag=False
        break
    node[i]=(node[i-1]-p[i-1])*2
    if node[i]>=sums[i]:
        check=i
        break

if not flag or check==-1:
    print(-1)
else:
    ans=0
    for i in range(check):
        ans+=node[i]
    for i in range(check,n+1):
        ans+=sums[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
	n=int(input())
	a=list(map(int,input().split()))
	if n==0:
		if a[0]==1:
			print(1)
			exit()
		else:
			print(-1)
			exit()
	M=[1]
	now=2
	p=max(a)
	for i in range(n):
		M.append(now)
		now-=a[i+1]
		if now<=p*2:
			now*=2
	now=a[-1]
	for i in range(n):
		r=min(now,M[-i-1])
		M[-i-1]=r
		now=r
		now+=a[-i-2]
	if a[0]!=0:
		print(-1)
		exit()
	for i in range(n+1):
		if M[i]<=0:
			print(-1)
			exit()
	print(sum(M))
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(reversed(list(map(int,input().split()))))
ans=[]
ans2=[1]
flg=0
for i in range(n+1):
  if sum(a[:i+1]) <= 2**(n-i):
    ans.append(sum(a[:i+1]))
  else:
    ans.append(2**(n-i))
a=list(reversed(a))
ans=list(reversed(ans))
for i in range(1,n+1):
  tmp=min(ans[i],(ans2[i-1]-a[i-1])*2)
  if tmp <= 0:
    flg = 1
  ans2.append(tmp)
if flg ==1:
  print(-1)
else:
  print(sum(ans2))

Submission status: Wrong Answer

Solution code:
n = input()
alist = [int(s) for s in input().split(" ")]

def check(alist):
  r = 1
  n = 1
  for i, a in enumerate(alist):
    if a > r:
      return -1
    if a == r and len(alist) - 1 != i:
      return -1
    r = (r - a) * 2
    if len(alist) - 1 != i:
      n += r
  return n

print(check(alist))

Submission status: Wrong Answer

Solution code:
import sys, math,os
from io import BytesIO, IOBase
from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
sys.setrecursionlimit(100000)
from fractions import Fraction
INF = float('inf')
mod = 998244353


def main():

    n=int(data())
    A=mdata()
    act=[0]*(n+1)
    t=1
    for i in range(n):
        act[i]=t-A[i]
        if act[i]<0:
            out(-1)
            exit()
        t=act[i]*2
    for i in range(n,0,-1):
        if act[i-1]<(act[i]+A[i])//2+(act[i]+A[i])%2 :
            out(-1)
            exit()
        act[i-1]=min(act[i]+A[i],act[i-1])
    ans=0
    for i in range(n):
        if act[i]==0 and act[i+1]+A[i+1]!=0:
            out(-1)
            exit()
    for i in range(n+1):
        ans+=act[i]+A[i]
    if ans==0:
        out(-1)
    else:
        out(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

P=[0]*(N+1)
P[N]=A[N]
Q=[0]*(N+1)
Q[N]=A[N]

for i in range(N,0,-1):
    mxp=P[i]+A[i-1]
    mnp=(P[i]//2) + (P[i]%2) +A[i-1]
    mxq=Q[i]+A[i-1]
    mnq=(Q[i]//2) + (Q[i]%2) +A[i-1]
    if mnp>2**i:
        print(-1)
        exit()
    P[i-1]=mnp
    Q[i-1]=min(mxq,2**i)

Q[0]=1

for i in range(1,N):
    if Q[i]>2**i and 2**i>=P[i]:
        Q[i]=2**i
    if Q[i]>(Q[i-1]-A[i-1])*2:
        Q[i]=(Q[i-1]-A[i-1])*2

print(sum(Q))

Submission status: Wrong Answer

Solution code:
n=int(input())
sums=[0]*(n+1)
node=[0]*(n+1)
p=list(map(int,input().split()))
flag=True

sums[n]=p[n]
for i in reversed(range(n)):
    sums[i]=p[i]+sums[i+1]

node[0]=1
check=-1
for i in range(1,n+1):
    if node[i-1]-p[i-1]<0:
        flag=False
        break
    node[i]=(node[i-1]-p[i-1])*2
    if node[i]>=sums[i]:
        check=i
        break

if not flag or check==-1:
    print(-1)
else:
    ans=0
    for i in range(check):
        ans+=node[i]
    for i in range(check,n+1):
        ans+=sums[i]
    print(ans)

Submission status: Wrong Answer

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

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

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

for i in range(n-1,0,-1):
    if a[i]>x[i]:
        print(-1)
        exit()
    x[i] = min(x[i],x[i+1]+a[i])
print(sum(x))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    An = [int(x) for x in input().strip().split()]
    total = sum(An)
    if An[0] != 0:
        print(-1)
        exit()
    ans = 1
    node = 1
    for n, a in enumerate(An[1:], start=1):
        node_ = min(total, node * 2)
        if node_ <= 0:
            print(-1)
            exit()
        ans += node_
        node = node_ - a
        total -= a

    if node != 0:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    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
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 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 > 0 and (math.log(newnod, 2) > 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:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
if a[0] > 0:
    print(-1)
    exit()
elif n == 0:
    print(1)
    exit()
elif n < 30 and a[-1] > (1 << n):
    print(-1)
    exit()
s = sum(a)
ans = 1
dp = [0] * n
dp[0] = 1
for i in range(1, n):
    dp[i] = min(s, 2 * dp[i - 1])
    ans += dp[i]
    dp[i] -= a[i]
    if dp[i] < 0:
        print(-1)
        exit()
    s -= a[i]
ans += a[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
# C

N = int(input())
A_N = list(map(int, input().split()))
reversed_A_N = list(reversed(A_N))

if A_N[0] != 0:
    print(-1)
    exit()
    
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]

print(sum(r_reversed_A_N))

Submission status: Wrong Answer

Solution code:
from math import ceil

def a():
    N = int(input())
    A = list(map(int,input().split()))
    INF = 2 * 10 ** 8

    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    BMAX = [INF] * (N+1)
    BMIN = [1] * (N+1)

    BMAX[N] = 0
    BMAX[0] = 1
    BMIN[N] = 0
    BMIN[0] = 1

    for i in range(N-1,-1,-1):
        BMAX[i] = min(BMAX[i],BMAX[i+1]+A[i+1])
        BMIN[i] = max(BMIN[i],ceil((BMIN[i+1]+A[i+1])/2))

    for i in range(1,N+1):
        BMAX[i] = min(BMAX[i],BMAX[i-1]*2-A[i])
        BMIN[i] = max(BMIN[i],BMIN[i-1]-A[i])

    if BMAX[0] + A[0] > 1:
        return -1

    ans = 0
    for i in range(0,N+1):
        if BMIN[i] > BMAX[i]:
            return -1
        ans += (BMAX[i] + A[i])
    return ans

print(a())

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
k=sum(a)
if n==0:
    if k==0:
        print(0)
    else:
        print(-1)
    exit()
elif k==0:
    print(-1)
elif k==1:
    print(n+1)
d=(k-1).bit_length()
ans=1
e=1
for i in range(0,n):
    e-=a[i]
    k-=a[i]
    if e<0:
        print(-1)
        exit()
    if 2*e<k:
        e*=2
    elif e<k:
        e=k
    #print("e",e)
    ans+=e
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
k = sum(A)
###syuutenの個数
c = 1  
###考えている列の〇の個数(次の列につながる個数)
aa = 1
ans = 1
if A[0] != 0:
    if N != 0:
        print(-1)
    else:
        if A[0] == 1:
            print(1)
        else:
            print(-1)
else:
    for i in range(1,N + 1):
        c *= 2
        ##次の列につながる個数の最大値
        if A[i] > c:
            ###A[i]はここが終点になるということ。終点の方が多いことは認められない
            aa = 0
            break
        elif A[i] == c:
            ###終点と同数だとこれより下には繋がらない。もし最下段でなければアウト
            if i != N:
                aa = 0
                break
            else:
                ans += c
        else:
            c -= A[i]
            k -= A[i]
            ans += A[i]
            ###終点の個数を引く。ここで終点の個数だけansを足す
            if c >= k:
                ###次の列につながる個数はこれよりしたにある終点の個数を超えれない
                c = k
            ans += c
            ###この段で下につながる個数を足す

if aa == 0:
    print(-1)
else:
    print(ans)

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.array([1]) # その深さのノード数
possible = np.array([1]) # その深さの子を生やせるノード数
aki = 1
for i in range(1, n+1):
    arr = np.append(arr, 1)
    possible = np.append(possible, 1)
    ai = a[i]
    if i == n: ai -= 1
    while ai > 0:
        if arr[aki] < possible[aki-1]*2:
            arr[aki:] += 1
            possible[aki:i] += 1
            ai -= 1
        else:
            aki += 1
        if aki > i:
            print(-1)
            exit()
    
print(arr.sum())

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
# step 1 後ろからの累積
cum = [0] * (n + 1)
cum[n] = a[n]
for i in range(n):
    cum[n - 1 - i] = cum[n - i] + a[n - 1 - i]
# step2 dpを更新する
# dp はその深さに存在する頂点の数
dp = [0] * (n + 1)
dp[0] = 1
ans = dp[0]
ng = 0
for i in range(n):
    if dp[i] < a[i]:
        ng = 1
    dp[i + 1] = min(2 * (dp[i] - a[i]), cum[i + 1])
    if i < n and dp[i + 1] <= 0:
        ng = 1
    ans += dp[i + 1]
if n == 0:
    if a[0] == 1:
        print(1)
    else:
        print(-1)
elif ng:
    print(-1)
else:
    print(ans)
# -1 ではないケースで落ちてる

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
if lst1[0] != 0:
    print(-1)
    exit()
res2 = [0]
for i in lst1[::-1]:
    res2.append(min(10**8,res2[-1]+i))

res2.reverse()

INF = res2[0]
res = [1] 
res3 = [1]
for i in lst1[1:]:
    res3.append(min(INF,res[-1]*2))
    res.append(min(INF,res[-1]*2-i))

#案2
for i in range(len(res)):
    if i == len(res)-1:
        break
    if res[i] <= 0:
        print(-1)
        exit()

ans = 0
res2 = res2[:-1]
for i,j in zip(res3,res2):
    ans += min(i,j)
print(ans)
"""print(*res)
print(*res3)
print(*ans)
"""

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
flag=True
ans=0
B=[0 for i in range(N+1)]
for i in range(N+1):
  if(i==0):
    if(A[i]==0):
      B[i]=1
    if(A[i]==1 and N>0):
      flag=False
  else:
    B[i]=B[i-1]*2-A[i]
  if(B[i]<0):
    flag=False
#print(B)
x=B[-1]#層の葉でない頂点数
y=A[-1]#層の頂点数
ans=A[-1]
#print(x,y,ans)
for i in range(N):
  if(x>B[N-1-i]*2):
    flag=False
    break
  else:
    #ans+=min(y,B[N-1-i])
    x=min(y,B[N-1-i])
    y=x+A[N-1-i]
    ans+=y
if flag:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil
input = lambda: sys.stdin.readline().rstrip()

MAX = 2 ** 40
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] == 0:
    print(-1)
    exit()
# その層で作ることができるノードの最大値
max_i = [MAX] * (n+1)
max_i[0] = 1

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

# print(max_i)

a = a[::-1]
cnt = 0
# 下の層の頂点の数
pre_cnt = 0
for i, v in enumerate(a):
    idx = n - i
    if v + ceil((pre_cnt) / 2) > max_i[idx]:
        # print(ceil((v + pre_cnt) / 2), max_cnt + v)
        print(-1)
        exit()
    # 上の頂点数
    if idx < 40:
        pre_cnt = min(v + pre_cnt, max_i[idx])
    else:
        pre_cnt = v + pre_cnt
    cnt += pre_cnt
    # print(pre_cnt, cnt)

print(cnt)

Submission status: Wrong Answer

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

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

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

for i in range(n-1,0,-1):
    if a[i]>x[i]:
        print(-1)
        exit()
    x[i] = min(x[i],x[i+1]+a[i])
print(sum(x))

Submission status: Wrong Answer

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

ret = 1
children = 1 - A[0]
bottom -= A[0]

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= 0:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    An = [int(x) for x in input().strip().split()]
    total = sum(An)
    if An[0] != 0:
        print(-1)
        exit()
    ans = 1
    node = 1
    for n, a in enumerate(An[1:], start=1):
        node_ = min(total, node * 2)
        if node_ < 0:
            print(-1)
            exit()
        ans += node_
        node = node_ - a
        total -= a

    if node != 0:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()