Problem:


Score : 600 points

Problem Statement

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

Notes

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

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

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

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

Constraints

0 \leq N \leq 10^5

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

A_N \geq 1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 A_2 \cdots A_N

Output

Print the answer as an integer.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

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

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

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

Sample Output 5

264



Sample input:
3
0 1 1 2


Sample output:
7

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
edge=[0]*(n+1)
ans=0
edge[0]=1
for i in range(1,n):
    edge[i]=edge[i-1]*2-a[i]
for i in range(n-1,-1,-1):
    bcnt=edge[i+1]+a[i+1]
    if bcnt//2+bcnt%2>edge[i]:
        ans=-1
        break
    if bcnt<edge[i]:
        edge[i]=bcnt
if ans!=-1:
    ans=sum(edge)+sum(a)
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

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
    break
x=B[N]#層の葉でない頂点数
y=A[N]#層の頂点数
ans=A[N]
for i in range(N):
  if(x>B[N-1-i]*2):
    flag=False
    break
  else:
    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:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    flag = True
    kuki = []
    kuki.append(1)
    if A[0] != 0:
        flag = False
    for i in range(1,N+1):
        if A[i] < kuki[i-1]*2:
            kuki.append(kuki[i-1]*2 - A[i])
        elif A[i] == kuki[i-1]*2 and i == N:
            kuki.append(kuki[i-1]*2 - A[i])
        else:
            flag = False
            break
    
    if flag:
        ne = A[N]
        for i in range(0,N+1):
            j = N-i
            if kuki[j] > ne:
                kuki[j] = ne
            else:
                break
        
    if flag:
        count = sum(A) + sum(kuki[:N])
    else:
        count = -1
    print(count)
    print(A)
    print(kuki)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
asum=[]
s=sum(a)
for i in range(n):
    s=s-a[i]
    asum.append(s)
ans=1
x=2**n
p=1
for i in range(n):
    x//=2
    p-=a[i]
    if 2*p<asum[i]/x or asum[i]<p:
        print(-1)
        sys.exit()
    p=min(2*p,asum[i])
    ans+=p
print(ans)

Submission status: Wrong Answer

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
    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
    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)
        #else:print('unichi')
    print(sum(g_l))
    return 0

if __name__ == "__main__":
    main()

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

print(ans)

Submission status: Wrong Answer

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

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

B = dict()
sm = 0
for i in range(len(A)-1, -1, -1):
    sm += A[i]
    B[i] = sm


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

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

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

Submission status: Wrong Answer

Solution code:
depth = int(input()) 
leaves = list(map(int, input().split(" ")))
limited = []
limited_a = []

def solve (depth) :
    _min = _max = 0
    cur = 1
    i = 0 
    if leaves[0] != 0 :
        return False 

    while i <= depth :
        limited_a.append( cur )
        cur=(cur-leaves[i])*2
        i+=1 

    i = depth
    while i >= 0 :
        if i==depth: 
            limited.append(leaves[i])
            _max = leaves[i]
            _min = (leaves[i]+1)//2
        else :
            _max = min(limited_a[i], _max+leaves[i])
            if _max < _min :
                return False 
            limited.append(_max)
            _min = (_min+leaves[i]+1)//2
        i -= 1
        cur = (cur-leaves[i])*2
    return True

if solve(depth) :
    print(sum(limited))
else :
    print (-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
if A[0]>0:
    print(-1)
    exit()
node1=[0]*(n+1)
node1[0]=1
node2=[0]*(n+1)
node2[-1]=A[-1]
for i in range(n):
    x=(node1[i]-A[i])*2
    if x<1:
        print(-1)
        exit()
    node1[i+1]=x
#print(node1)
for i in range(n-1,-1,-1):
    x=(node2[i+1]+A[i])
    if i<27:
        x=min(2**i, x)
    node2[i]=x
ans=[]

for i in range(n+1):
    ans.append(min(node1[i],node2[i]))
print(sum(ans))

Submission status: Wrong Answer

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

node_max = [1]
for i in range(1, n+1):
    node_max.append(min(10**18, node_max[i-1]*2-a[i]))

a.reverse()
node_max.reverse()

node_max
ans = 0
main = 0
node_max.append(0)


flag = 1

for i in range(n+1):
    main = min(main+a[i], node_max[i+1])
    ans += main + a[i]
    if i == 0:
        continue
    if (main+a[i]) > node_max[i+1]*2:
        flag = 0
        break


if flag == 1:
    print(ans)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
A = list(map(int,input().split()))
leaf= [-1 for i in range(N+1)]
notleaf = [-1 for i in range(N+1)]
flag=0

if N == 0 and A[0] == 1:
    print(1)
elif N != 0 and A[0]>=1:
    print(-1)
else:
    leaf[0]=0
    notleaf[0]=1
    for d in range(1, N+1):
        leaf[d] = A[d]
        notleaf[d] = 2*notleaf[d-1] - leaf[d]
        if notleaf[d]<0:
            flag=1
            print(-1)
            break
    #if flag==0 and notleaf[N] != 0:
    #    print(-1)
    else:
        sleaf = 0
        for i in range(N+1):
            sleaf += leaf[i]
        
        d1 = 0
        for i in range(N+1):
            d1 += (i+1) * leaf[i]
        
        sleaf -= 1
        for i in range(1,N+1):
            if sleaf>0:
                d1 -= i*( min(sleaf, leaf[i]+notleaf[i] - notleaf[i-1]))
                sleaf -= (leaf[i]+notleaf[i] - notleaf[i-1])
            else:
                print(d1)
                break

Submission status: Wrong Answer

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

flag = True
for i in range(n):
    if a[i+1] != 0:
        flag = False
        break

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

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

nleaf = 1
ans = 0
v = list()

for i in range(n):
    nleaf -= a[i]
    v.append(nleaf)
    nleaf *= 2

nleaf = a[n]
ans += a[n]
for i in range(n-1, 0, -1):
    if v[i]*2 < nleaf:
        print(-1)
        exit()
    if v[i] > nleaf:
        v[i] = nleaf
    nleaf = v[i] + a[i]
    ans += nleaf
print(ans + 1)

Submission status: Wrong Answer

Solution code:

from math import ceil
N = int(input())
A = list(map(int, input().split()))
if(A[0] != 0):
    print(-1)
    exit(0)
# curは作り出せる最大ノード数
if(N == 0 and A[0] == 0):
    print(-1)
    exit(0)
cur = 0
S = [0] * (N + 1)
for i in range(N, 0, -1):
    cur += A[i]
    S[i - 1] = cur
# print(S)

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

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

'''

Submission status: Wrong Answer

Solution code:
t = int(input())
num_list = list(map(int, input().split()))

pair_node_list = []
not_flag = False
for i,num in enumerate(num_list):
  if i==0:
    if num!=0:
      not_flag = True
      break
    elif num==0:
      pair_node_list.append(1)
  else:
    _pair_num = pair_node_list[i-1]*2 - num
    if _pair_num >= 0:
      pair_node_list.append(_pair_num)
    else:
      not_flag = True
      break
      
if not_flag:
  print(-1)
else:
  print(_pair_num)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

b = 2**n
e = 2**n
B = [0]*(n+1)
for i in range(n+1):
    e -= A[i] * b
    b = b // 2
    if i == 0:
        B[i] = 1 - A[i]
    else:
        B[i] = 2*(B[i-1]) - A[i]
print(B)
if e < 0:
    print(-1)
else:
    ans = 0
    p = A[-1]
    t = 0
    for i in range(1,n+2):
        t += A[-1*i]
        if t > B[-1*i]:
            t = B[-1*i] + A[-1*i]
        ans += t
    print(ans)

Submission status: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = list(mapi())
res =a[n]
mp = [min(2**(i),int(1e8)) for i in range(n+1)]
#print(*mp)
lst = 1
pst = [0]*(n+1)
for i in range(n+1):
    #print(lst,a[i])
    #res+=lst
    pst[i] = lst
    if pst[i]<=0:
        print(-1)
        exit()
    lst-=a[i]
    lst*=2
#print(*pst,"c")
#print(*mp,"d")
mx = a[n]
for i in range(n-1,-1,-1):
    if a[i]>=mp[i] or mx+a[i]>=pst[i]:
        res = -1
        break
    mx = min(mx+a[i],mp[i])
    res+=min(mx,pst[i])
    #print(res,mx,mp[i],a[i])
print(res)

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)
    if eda<=0:
      print(-1)
      break
    edasum += eda
  else:
    print(edasum+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A == [0]:
            print('-1')
        elif A == [1]:
            print('1')
        else:
            print('-1')
        return

    if N == 1:
        if A == [0, 1]:
            print('2')
        elif A == [0, 2]:
            print('3')
        else:
            print('-1')
        return

    f = [0 for i in range(N)]

    f[0] = 1
    count = sum(A) - 1

    for d in range(1, N):
        f[d] = 2 * min(f[d - 1], count) - A[d] + min(max(f[d - 1] - count, 0), f[d - 1])
        count -= min(f[d - 1], count)
        if f[d] < 0:
            print('-1')
            return
    print(sum(f) + sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys #追加
from collections import deque
sys.setrecursionlimit(10**9) #追加

n = int(input())
A = list(map(int, input().split()))
ans = 0

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

start = 1
way = sum(A)

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

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

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

Submission status: Wrong Answer

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

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

ret = 1
children = 1

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0 and a[0]==1:
	print(1)
elif n==0:
	print(a[0])
elif a[0]!=0:
	print(-1)
elif a[n]==0:
	print(-1)
else:
	ruisekiwa = [0 for _ in range(n+1)]
	ruisekiwa[n] = a[n]
	for i in range(n)[::-1]:
		ruisekiwa[i] = a[i] + ruisekiwa[i+1]
	cnt=1
	ans=1
	for i in range(1,n+1):
		target = a[i]
		if cnt*2 - target <= 0 and i != n:
			print(-1)
			exit()
		elif i == n:
			if cnt * 2 - target < 0:
				print(-1)
				exit()
			else:
				cnt = min(cnt*2, a[n])
				ans += cnt
		else:
			if cnt*2-a[i] < ruisekiwa[i]:
				ans += cnt*2
				cnt = cnt*2-a[i]
			else:
				ans += ruisekiwa[i]
				cnt = ruisekiwa[i]
	print(ans)

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:
import math

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

result=0
tr=[0 for _ in range(N+1)]
miki=0
max_miki=[0 for _ in range(N+1)]

for i in range(N+1):
    if i==0:
        max_miki[i]=1
    else:
        max_miki[i]=(max_miki[i-1]-lf[i-1])*2

i=N

while i>=0:
    if i==N:
        tr[N]=lf[N]
        result+=lf[N]
        i-=1
    else:
        miki=int(min(tr[i+1]+lf[i],max_miki[i]))
        tr[i]=miki
        result+=miki

        if (miki-lf[i])*2<tr[i+1]:
            result=-1
            break
        i-=1

print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if a[0] == 1:
    if n == 0:
        print(1)
    else:
        print(-1)
        exit()
elif a[0] != 0:
    print(-1)
    exit()
acc = [0 for i in range(n+1)]
acc[-1] = a[-1]
for i in range(n, 0,-1):
    acc[i-1] = acc[i] + a[i-1]
ans = count = 1
for i in range(1,n+1):
    #print("{}回目:　count = {}".format(i, count))
    count *= 2
    if count < a[i]:
        print(-1)
        exit()
    if count > acc[i] - a[i]:
        count = acc[i] - a[i]
    else:
        count -= a[i]
    ans += a[i]
    ans += count
if ans < n:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:

from math import ceil
N = int(input())
A = list(map(int, input().split()))
if(A[0] != 0):
    print(-1)
    exit(0)
# curは作り出せる最大ノード数
if(N == 0 and A[0] == 0):
    print(1)
    exit(-1)
cur = 0
S = [0] * (N + 1)
for i in range(N, 0, -1):
    cur += A[i]
    S[i - 1] = cur
# print(S)

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

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

'''

Submission status: Wrong Answer

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

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

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)
    elif n >= 1 and a[-1] == 0:
        print(-1)
    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])
            if numt > maxnum[j1-1] * 2:
                print(-1)
                sys.exit()
            num[j1] = numt
        r = sum(num)
        print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
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):
        tmp = node*2-a_li[i]
        if tmp < 0:
            print(-1)
            break
        if i!=n:
            node = min(tmp, sum(a_li[i+1:]))
            cnt += node + a_li[i]
        else:
            cnt += a_li[i]
    else:
        print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list( map(int, input().split()) )
B = [i for i in A]

for i in range(N):
  B[N-i-1] += B[N-i]

if(0 in B):
  print(-1)
  exit()
  
if(A[0] != 0):
  print(-1)
  exit()
if(N == 0):
  print(1)
  exit()
a = 1
sum = a
for i in range(1, N):
  if(2*(a-A[i-1]) > B[i]):
    a = B[i]
  else:
    a = 2*(a-A[i-1])
    
  if(a <= A[i]):
    print(-1)
    exit()
  sum += a

if(2*(a-A[-2]) < A[-1]):
  print(-1)
  exit()
print(sum + A[-1])

Submission status: Wrong Answer

Solution code:
def check(d, nums):

  if  d > 0 and not(nums[0]==0):
    return "-1"

  if d==0 and nums[0] == 0:
    return "-1"
  
  for i in range(len(nums)):
    if nums[i] > 2**i:
      return "-1"
    
  fullnode = 2**(d+1)-1
  lostnode = 0
  for i, n in enumerate(nums):
    lostnode += n*(2**(d+1-i)-2)
    print(lostnode)
  return str(fullnode-lostnode)
"""
def recTree(d,nums,children):
  if d==0 and len(nums) == 1 and nums[0]==0:
    return 1
  if d > 0 and len(nums) == d+1:
    print(d,":",((children+1)//2) ,"+", nums[-1])
    return ((children+1)//2) + nums[-1] + recTree(d-1, nums[:-1], nums[-1])
  
"""
d = int(input())
nums = list(map(int,input().split(" ")))
print(check(d, nums))

Submission status: Wrong Answer

Solution code:
import sys #追加
from collections import deque
sys.setrecursionlimit(10**9) #追加

n = int(input())
A = list(map(int, input().split()))
ans = 0

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

start = 1
way = sum(A)

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

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

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

Submission status: Wrong Answer

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

ls = []

for s in A:
  ans = s+1
  ls.append(ans)
  
print(sum(ls)-1)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0
branch_num = 0

candidates = [1]
possible = 1
for a in As:
    possible -= a
    possible *= 2
    candidates.append(possible)

candidates.pop(-1)

for i in range(1, N+1):
    index = -i
    a = As[index]
    c = candidates[index]
    if c < a:
        result = -1
        break
    branch_num += a
    result += min(branch_num, c)
    if math.ceil(branch_num/2) >= c:
        branch_num = math.ceil(branch_num/2)

if result != -1:
    result += 1

print(result)

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
    

if (N==0)&(A[0]>0)&(A[0]<=2):
    print(A[0])
elif (N==0)&(A[0]==0):
    print(-1)
elif (N==0)&(A[0]>2):
    print(-1)
else:
    for i in range(1,N+1):
        root_num, count_leaf, count = calc_node_num(A[i], root_num, count_leaf, count)
        if A[0]>0:
            print(-1)
            break
        if (i<N)&(root_num==0):
            print(-1)
            break
        if root_num < 0:
            print(-1)
            break
    else:
        print(count)

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
cnt = 0
dic = defaultdict(int)
prv = -1
ans = 0
nya = False
max_ = 0
for i in range(n+1):
    if i == 0:
        if A[i] == 0:
            max_ = max(A[i],max_)
            dic[0] = 1
            cnt += 1
        else:
            print(-1)
            exit()
    else:
        if max_ <= A[i]:
            if not dic[A[i]]:
                max_ = max(A[i],max_)
                dic[A[i]] = 1
                ans += A[i] * cnt
            else:
                if A[i] != 0:
                    dic[A[i]] += 1
                    ans += cnt * dic[A[i]] * A[i]
                    #cnt += 1
                    cnt += 1
                else:
                    cnt += 1
                max_ = max(A[i],max_)
        else:
            if dic[A[i]]:
                ans += cnt * dic[A[i]] * A[i] if A[i] != 0 else cnt
                cnt += 1
            else:
                print(-1)
                exit()
    #print(ans)
print(ans)

Submission status: Wrong Answer

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

if n == 0:
    print(1)
    exit()

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
if a[0] > 0:
    print(-1)
    exit()
if n == 0:
    print(1)
    exit()
# if n < 30 and a[-1] > (1 << n):
#     print(-1)
#     exit()
# for i in range(min(n, 30)):
#     if a[i] > (1 << i) - 1:
#         print(-1)
#         exit()
s = sum(a)
ans = 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
    dp[i + 1] = min(s, 2 * dp[i])
    ans += dp[i + 1]
    dp[i + 1] -= a[i + 1]
    s -= a[i + 1]
    if dp[i] <= 0:
        print(-1)
        exit()
if dp[-1] < 0:
    print(-1)
    exit()
print(ans)

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)
FLAG = 0
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 FLAG:
            leaf[i + 1] += (i - FLAG) * a[i + 1]
        else:
            FLAG = i
    leaf[i + 1] += a[i + 1]
# print(non_leaf)
# print(leaf)
print(sum(non_leaf) + sum(leaf))

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

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:
    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- (A[n-1] + TOP[n-2])
  else:
    ans = -1
  
  
print(ans)