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:
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
class BinarySearchTree:
    def __init__(self, key):
        self.root = Node(key)
 
    def search(self, key):
        node = self.root
        while node:
            if node.key == key:
                print("Found!")
                return node
            elif node.key > key:
                node = node.left
            else:
                node = node.right
        return None
 
    def insert(self, key):
        node = self.root
        while node:
            parent = node
            if node.key == key:
                print("Data already exists.")
                return
            elif node.key > key:
                node = node.left
                flag = "left"
            else:
                node = node.right
                flag = "right"
        new = Node(key)
        if flag == "left":
            parent.left = new
        else:
            parent.right = new
 
    def deletemin(self, node):
        parent = node
        tmp = node.right
        while tmp.left:
            parent = tmp
            tmp = tmp.left
        parent.right = tmp.right
        return tmp
 
    def delete(self, key):
        node = self.root
        parent = node
        flag = None
        while node:
            if node.key == key:
                if node.left == None and node.right == None:
                    if flag == "left":
                        parent.left = None
                    else:
                        parent.right = None
                elif node.left == None:
                    if flag == "left":
                        parent.left = node.right
                    else:
                        parent.right = node.right
                elif node.right == None:
                    if flag == "left":
                        parent.left = node.left
                    else:
                        parent.right = node.left
                else:
                    tmp = self.deletemin(node)
                    if flag == "left":
                        parent.left = tmp
                    else:
                        parent.right = tmp
                    tmp.right = node.right
                    tmp.left = node.left
            parent = node
            if node.key > key:
                node = node.left
                flag = "left"
            else:
                node = node.right
                flag = "right"
 
    def inorder(self, tree):
        tmp = tree
        if tmp == None:
            return
        else:
            self.inorder(tmp.left)
            print(tmp.key)
            self.inorder(tmp.right)
 
t = BinarySearchTree(4)
t.insert(2)
t.insert(1)
t.insert(3)
t.insert(6)
t.insert(5)
t.insert(7)
print("delete 6")
t.delete(6)
print("print data...")
t.inorder(t.root)

Submission status: Wrong Answer

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

v=[0 for i in range(n+2)]
import time

#start=time.time()
nextv=0

nec=2**n

for i in range(n,-1,-1):

    if nec>=v[i+1]+a[i]:
        v[i]=v[i+1]+a[i]
    else:
        v[i]=nec

    nec=nec >>1



#print(time.time()-start)

for i in range(1,n+1):
    if v[i-1]-a[i-1]<0:
        ok=False
        break
    if (v[i-1]-a[i-1])*2<v[i]:
        v[i]=(v[i-1]-a[i-1])*2

if a[0]!=0:ok=False

ans=sum(v)

if ans==0:ok=False

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

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]<(act[i+1]+A[i+1])//2+(act[i+1]+A[i+1])%2 or act[i]>(act[i+1]+A[i+1]):
            out(-1)
            exit()
    for i in range(n+1):
        ans+=act[i]+A[i]
    out(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def floor(x):
    if x%2 == 1:
        return int(x/2)+1
    else:
        return int(x/2)

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 floor(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:
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = ZZ()
    if A[0] != 0:
        print(-1)
        return

    v = [[1, 1] for _ in range(N+1)]

    for i in range(N):
        x = v[i][1] - A[i]
        if x < 0:
            print(-1)
            return
        v[i+1][1] = 2 * x
    if v[N][0] > A[N] or A[N] > v[N][1]:
        print(-1)
        return
    v[N] = [A[N], A[N]]
    for i in range(N):
        x = (v[N-i][0]+1)//2 + A[N-i-1]
        y = v[N-i][1] + A[N-i-1]
        v[N-i-1][0] = max(v[N-i-1][0], x)
        v[N-i-1][1] = min(v[N-i-1][1], y)
        if v[N-i-1][0] > v[N-i-1][1]:
            print(-1)
            break
    v[0] = [1, 1]
    output = 0
    for i in range(N+1): output += v[i][1]
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    # N = int(input().strip())
    # A = list(map(int, input().strip().split(" ")))
    N = 4
    A = list(map(int, "0 0 1 0 2".strip().split(" ")))

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

    tree = [0] * (sum([2 ** i for i in range(N + 1)]))
    for i, a in enumerate(A[::-1]):
        depth = len(A) - 1 - i
        depth_hierarchy_start_index = sum([2 ** i for i in range(depth)]) if depth != 0 else 0
        depth_hierarchy_end_index = sum([2 ** i for i in range(depth + 1)]) if depth != 0 else 1

        # keisho
        if depth != N:
            for i in range(depth_hierarchy_start_index, depth_hierarchy_end_index):
                if tree[2 * i + 1] != 0 or tree[2 * i + 2] != 0:
                    tree[i] = 2

        # 1 ume
        count = 0
        part = 2
        while True:
            try:
                for i in range(0, 2 ** depth, int(2 ** depth / part) if int(2 ** depth / part) != 0 else 1):
                    if tree[depth_hierarchy_start_index + i] == 0:
                        tree[depth_hierarchy_start_index + i] = 1
                        count += 1
                    if count == a:
                        break
                    part *= 2
                if count == a:
                    break
            except:
                print(-1)

    print(sum([1 if i != 0 else 0 for i in tree]))

Submission status: Wrong Answer

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

MAX = []
e = 1
for i in range(N+1):
    if e > 0:
        MAX.append(e)
        e -= A[i]
        e *= 2
    else:
        print(-1)
        exit()

A.reverse()
MAX.reverse()

MIN = []
s = 0
for i in range(N+1):
    s = min(s+A[i],2**(N-i))
    MIN.append(min(MAX[i],s))
print(sum(MIN))

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

for i in range(n+1):
    if pow(2,i) < a[i]:
        print(-1)
        exit()
    if pow(2,i) > 10**9:
        break

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:
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)
    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()))
su = sum(a)
# print(su)
l = [su]*n
for i in range(1,n):
    l[i]=l[i-1]-a[i-1]
count=0
x = 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]
    if m[j]<a[j]:
        x = 1
        break
    # print(m[j])
    count += m[j]
    m[j] -= a[j]
count+=a[-1]+1

if x==1:
    print(-1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=1
flag=0
sum_=0
for i in range(N+1):
  sum_+=A[i]
node=2
if A[0]>0:
  flag=1
  if A==[1] and N==1:
    flag==2
if N!=0:
  sum_-=A[1]
for i in range(1,N+1):
  if i!=N and node-A[i]<=0:
    flag=1
  elif i!=N:
    sum_-=A[i+1]
    ans+=node
    if 2*(node-A[i])-A[i+1]<=sum_:
      node=2*(node-A[i])
    else:
      node=sum_+A[i+1]   
  else:
    if node-A[i]<0:
      flag=1
    else:
      ans+=A[i]
if N==0 and A==[0]:
  flag=1
if flag==1:
  print("-1")
elif flag==2:
  print("1")
else:
  print(ans)

Submission status: Wrong Answer

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
b=1

l_sita=[0]*n
h_sita=[0]*n
ans=1
if l[0]>0:
  print(-1)
else:
  r=0
  if l[n]%2==1:
    r=l[n]//2+1
  else:
    r=l[n]//2
  l_sita[n-1]=r+l[n-1]
  h_sita[n-1]=l[n]+l[n-1]
  for d in range(n-2):
    r=0
    if l[n-d-1]%2==1:
      r=l[n-d-1]//2+1
    else:
      r=l[n-d-1]//2
    l_sita[n-d-2]=r+l[n-d-2]
    h_sita[n-d-2]=h_sita[n-d-1]+l[n-d-2]
  for d in range(n):
  #深さdに対してl[d]は葉の数。
  #bは深さdでの枝の数。
  #d+1での葉の数+dの葉の数
  #深さdの最大頂点数
  #上二つのうち小さい方が最大値。
  #枝の最小値はd+1の葉の数/2(切り上げ)+dの葉の数
    if d==n-1:
      ans+=l[d+1]
      b=2*b-l[d+1]
      if b<=0:
        ans=-1
        break
    else:
      ans+=min(h_sita[d+1],2*b)
      b=min(h_sita[d+1],2*b)-l[d+1]
      if b<=0 or 2*b<l_sita[d+1]:
        ans=-1
        break
  print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n == 0:
    print(a[0])
    exit()
if a[0] > 0:
    print(-1)
    exit()
l = [0] * (n + 1)
u = [0] * (n + 1)
l[n] = a[n]
u[n] = a[n]
for i in range(n, 0, -1):
    l[i - 1] = -(-l[i] // 2) + a[i - 1]
    u[i - 1] = u[i] + a[i - 1]
if l[0] > 1:
    print(-1)
    exit()
u[0] = 1 + a[0]
itr = 0
while True:
    update = False
    for i in range(n):
        if u[i] < l[i]:
            print(-1)
            exit()
        n_u = 2 * (u[i] - a[i])
        if n_u < u[i + 1]:
            update = True
            u[i + 1] = n_u
    if not update:
        break
    update = False
    for i in range(n, 0, -1):
        if u[i] < l[i]:
            print(-1)
            exit()
        n_u = u[i] + a[i - 1]
        if n_u < u[i - 1]:
            update = True
            u[i - 1] = n_u
    if not update:
        break
for i in range(n + 1):
    if u[i] < l[i]:
        print(-1)
        exit()
print(sum(u))

Submission status: Wrong Answer

Solution code:
n = int( input() )
p = [ int( pi ) for pi in input().split() ]

sump = int( 0 )
for pi in p:
    sump += pi

ans = int( 0 )
for i in range( n+1 ):
    if i == 0:
        ans += 1
        px = 1
        if p[ i ] == 1:
            ans = -1
            break
    else:
        if px*2 <= sump:
            ans += px*2
            px = px*2 - p[ i ]
            sump = sump - p[ i ]
        else:
            ans += sump
            px = sump - p[ i ]
            sump = sump - p[ i ]
        if px < 0:
            ans = -1
            break

print( ans )

Submission status: Wrong Answer

Solution code:
a = input()
b = input().split(" ")
N = int(a)
leaf = [int(x) for x in b]
# print(leaf)
feuille = 0
racine = 0
i = 0
element = 0 
while i < N+1:
    feuille = leaf[i]
    if(2**racine >= feuille):
        racine = 2**racine - feuille
    else:
        print(-7)
        exit()
    element += feuille + racine
    i += 1
print(element)

Submission status: Wrong Answer

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

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

#print("{}回目:　count = {}".format(i, count))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
V = [0]*(N+1)
A_sum = A[:] #その深さ以降で必要な葉の数
for i in range(N,0,-1):
    A_sum[i-1] += A_sum[i]
#print(A_sum)
V[0] = 1
for i in range(1,N+1):
    if A[i] > 2*(V[i-1] - A[i-1]):
        print(-1)
        exit()
    V[i] = min(2*(V[i-1] - A[i-1]), A_sum[i])
ans = sum(V)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*a = map(int, read().split())



L = [0]*(n+1)
R = [0]*(n+1)
l = r = a[n]
L[n] = R[n] = 0


ok = 1
for i in range(n-1,-1,-1):
    ai = a[i]
    l = (l+1)//2
    r = min(r,1<<i)
    if i <= 60:
        if l+ai > 1<<i:
            ok = 0
            break
        else:
            r = min(r,(1<<i)-ai)
    L[i] = l
    R[i] = r
    l += ai
    r += ai

        
if not ok or n==a[0]==0:
    print(-1)
else:
    #print(L,R)
    ans = living = R[0]
    ans += a[0]

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

        #print(living,a[i],R[i])
        
        living = min(living,R[i])
        
        ans += living + a[i]        
        
        #print(living,R[i])

    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input().split(" ")
for i in range(len(a)):
	a[i] = int(a[i])
min = [0] * (n+1)
max = [0] * (n+1)
f = 0
if a[0] == 0:
	min[0] = 1
	max[0] = 1
for i in range(1, len(a)):
	min[i] = min[i-1] - a[i-1]
	max[i] = (max[i-1] - a[i-1]) * 2
	if max[i] < a[i]:
		f = 1
max[-1] = a[-1]
t = a[-1]
for i in range(1, len(a)):
	j = n - i
	m = max[j+1] + a[j]
	if m <= max[j]:
		max[j] = m
		t += m
	elif m > max[j]:
		t += max[j]
	if m < min[j]:
		f = 1
if f == 1:
	print(-1)
else:
	print(t)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
b=1

l_sita=[0]*n
print(len(l_sita))
h_sita=[0]*n
ans=1
if l[0]>0:
  print(-1)
else:
  r=0
  if l[n]%2==1:
    r=l[n]//2+1
  else:
    r=l[n]//2
  l_sita[n-1]=r+l[n-1]
  h_sita[n-1]=l[n]+l[n-1]
  for d in range(n-2):
    r=0
    if l[n-d-1]%2==1:
      r=l[n-d-1]//2+1
    else:
      r=l[n-d-1]//2
    l_sita[n-d-2]=r+l[n-d-2]
    h_sita[n-d-2]=h_sita[n-d-1]+l[n-d-2]
  for d in range(n):
  #深さdに対してl[d]は葉の数。
  #bは深さdでの枝の数。
  #d+1での葉の数+dの葉の数
  #深さdの最大頂点数
  #上二つのうち小さい方が最大値。
  #枝の最小値はd+1の葉の数/2(切り上げ)+dの葉の数
    if d==n-1:
      ans+=l[d+1]
      b=2*b-l[d+1]
      if b<=0:
        ans=-1
        break
    else:
      ans+=min(h_sita[d+1],2*b)
      b=min(h_sita[d+1],2*b)-l[d+1]
      if b<=0 or 2*b<l_sita[d+1]:
        ans=-1
        break
  print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
for i in range(N):
    if A[i]>i:
        print(-1)
        exit()

Submission status: Wrong Answer

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

for i in range(n+1):
    if pow(2,i) > a[i]:
        print(-1)
        exit()
    if pow(2,i) > 10**9:
        break

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:
import sys
n=int(input())
a=input()
a=a.split()
M=1
m=int(a[n])
Ml=list()
ml=list()
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)
ml.append(m)
for i in range(n):
    m=m+int(a[n-i-1])
    ml.insert(0,m)
for i in range(n+1):
    Q=Q+min(Ml[i],ml[i])
print(Q)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
ans = 1
children = 0
flag = False
for i in reversed(range(1, len(a))):
    #2*(2**(i-1) - a[i-1])#最大値
    #2**i
    #math.ceil(children/2) + a[i]#最小値
    if 2*(2**(i-1) - a[i-1]) < math.ceil(children/2) + a[i]:
        flag = True
        break
    if math.ceil(children/2) + a[i] > 2**i:
        flag = True
        break
    if 2*(2**(i-1) - a[i-1]) < 1:
        flag = True
        break
    children = min([2**i, a[i]+children, 2*(2**(i-1) - a[i-1])])
    ans += children

if flag:
    print(-1)
else:
    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
for i in range(1,n+1):
  c[i] = 2*c[i-1]-a[i]
  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)
  #print('a',a)
  #print('c',c)
  #print('r',r)
else:
  print(-1)

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
    num[-1] = a[-1]
    r = 0
    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)
    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())
al = list(map(int, input().split()))

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

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 = [0]*(n+1)
# print(al, lim)

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

for l in lim:
    if l <= 0:
        print(-1)
        exit()

if sum(ansl) <= 0:
    print(-1)
    exit()

print(sum(ansl))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=1
flag=0
sum_=0
for i in range(N+1):
  sum_+=A[i]
node=2
if A[0]>0:
  flag=1
  if A==[1] and N==1:
    flag==2
if N!=0:
  sum_-=A[1]
for i in range(1,N+1):
  if i!=N and node-A[i]<=0:
    flag=1
  elif i!=N:
    sum_-=A[i+1]
    ans+=node
    if 2*(node-A[i])-A[i+1]<=sum_:
      node=2*(node-A[i])
    else:
      node=sum_+A[i+1]   
  else:
    if node-A[i]<0:
      flag=1
    else:
      ans+=A[i]

if flag==1:
  print("-1")
elif flag==2:
  print("1")
else:
  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 or As[0] == 1:
    print(-1)
else:
    print(sum(depth_sum))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
if A[0] != 0:
    print(-1)
    exit()
total = []
num = 0
for i in reversed(range(N+1)):
    num += A[i]
    total.append(num)
total.reverse()
ans = 1
num = 1
for i in range(1,N+1):
    num = min(2*num, total[i])
    ans += num
    num -= A[i]
    if num < 0:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

def power(a, n):
	tmp = 1
	cnt = 0
	while cnt <= n or tmp <= 10**18:
		tmp *= a
		cnt += 1
	return tmp

num = [0]*(N+1)  # 各層でとれるノード

ma = 1
for i, a in enumerate(A):
	if i == N and a <= ma:
		num[i] = ma
	elif a <= ma-1:
		num[i] = ma
		ma = (ma-a)*2
	else:
		print(-1)
		exit()
num_reml = num.copy()
for i in range(N+1):
	num_reml[i] -= A[i]
# print(num)
# print(num_reml)  # 各層で葉を除いてとれるノード

tmp = A[-1]
ans = A[-1]
for i, a in enumerate(A[::-1]):
	if i == 0: continue
	d = N-i
	if tmp > num_reml[d]:
		tmp = -(-tmp//2)
	tmp += a
	ans += tmp

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
a=1
k=0
f=0
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if a<=0:
    f+=1
    break
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  print(l[0])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import math


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

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

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

if bool_ == 1:
	print(-1)
else:
	print(sum(vert) + sum(A))

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()]
    if N == 0:
        print(1)
        exit()
    if An[0] != 0:
        print(-1)
        exit()
    ans = 1
    node = 1
    total = sum(An)
    for n, a in enumerate(An[1:], start=1):
        node_ = min(total, node * 2)
        ans += node_
        node = node_ - a
        if node_ < 0:
            print(-1)
            exit()
        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()))
k=sum(a)
if n==0:
    if k==0:
        print(0)
    else:
        print(-1)
    exit()
elif k==0:
    print(-1)
    exit()
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:
import sys
from math import ceil
input = lambda: sys.stdin.readline().rstrip()

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

for i in range(1, n+1):
    if max_i[i-1] * 2 - a[i] < INF:
        max_i[i] = max_i[i-1] * 2 - a[i]
    else:
        max_i[i] = INF
for i in range(1, n+1):
    max_i[i] += a[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(-1)
        exit()
    # 上の頂点数
    pre_cnt = min(v + pre_cnt, max_i[idx])
    cnt += pre_cnt


print(cnt)

Submission status: Wrong Answer

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

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

sums[0]=1
for i in range(1,n+1):
    c=(sums[i-1]-p[i-1])*2
    if c<=0:
        flag=True
        break
    if c<sums[i]:
        sums[i]=c
    else:
        break

if flag or p[0]>0:
    print(-1)
else:
    print(sum(sums))

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)
    exit()
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)
print(ans)

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 < A[i]:
                print(-1)
                return
            t=min(t,v)
            ans+=t
        else:
            t=min(t,v)
            if t < A[i+1]:
                print(-1)
                return
            ans+=t
            t-=A[i+1]
    print(ans)

main()