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:
# 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:
    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=list(map(int,input().split()))
if n==0:
	x=a[0]
	if x==1:
		print(1)
		exit()
	else:
		print(-1)
		exit()
M=[1]
now=2
for i in range(n):
	M.append(now)
	now-=a[i+1]
	if now<=10**8:
		now*=2
now=a[-1]
for i in range(n):
	M[-i-1]=min(now,M[-i-1])
	now=min(now,M[-i-1])
	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))

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)
        v[N-i-1][0] += A[N-i-1]
        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:
from sys import stdin, stdout
n = int(stdin.readline())
nmleaves = list(map(int, stdin.readline().strip().split()))

# pref[i]: sum of all elements in nmleaves after i, i.e. sum(nmleaves[i+1:])
full = sum(nmleaves)
tot = 0
pref = [0]*(n+1)
for i, l in enumerate(nmleaves):
    tot += l
    pref[i] = full - tot

if n==0:
    print(0)

else:
    if nmleaves[0]!=0:
        print(-1)
        exit()
    
    ## it exists
    ans = 0
    for level, leaves in enumerate(nmleaves):
        if leaves > 2**(level):
            print(-1)
            exit()

        if level == 0:
            ans += 1
            validnom = 1
        else:
            maxup = 2*validnom
            maxnom = maxup - leaves

            if level+1<len(nmleaves):
                validnom = min(maxnom, pref[level], 2**level - leaves)
                ans += (leaves + validnom)
            else:
                ans += leaves
    print(ans)

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

ch  = int( -1 )
ans = int( 0 )
for i in range( n+1 ):
    if i == 0:
        ans += 1
        px = 1
    elif 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:
N = int(input())
As = list(map(int, input().split()))

if As[0] > 0:
    if N == 0 and As[0] == 1:
        print(1)
    else:
        print(-1)
    exit()

flg = True

branch = [1]
for depth in range(1, N+1):
    b = branch[-1] * 2 - As[depth]
    if b >= 0:
        branch.append(b)
    else:
        print(-1)
        exit()

s = 0
b = 0
for i in range(N, 0, -1):
    b += As[i]
    if b > branch[i-1] * 2:
        s += sum(branch[:i+1]) + sum(As[:i+1])
        break
    else:
        s += b

print(s)

Submission status: Wrong Answer

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

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

l = [0] * (n + 1)
x = 1
tot = 0
l[0] = 1
for i in range(1, n + 1):
    tot = 2 * x
    x = tot - a[i]
    l[i] = tot

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

a[n] -= 1
ans = 0
for i in range(n + 1):
    add = min(u[i], l[i], r[i])
    if add <= a[i]:
        print(-1)
        exit()
    ans += add
print(ans)

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

if ok:
    print(sum(v))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from functools import reduce
n = int(input())
aList = list(map(int, input().split()))
sList = []
s = 0
for ra in reversed(aList):
    s += ra
    sList.append(s)
sList.reverse()

def main():
    c = 1
    a = aList.pop(0)
    s = sList.pop(0)
    if a > 0 and n != 0:
        return -1
    su = c
    for i in range(n):
        a = aList.pop(0)
        s = sList.pop(0)
        t = min(c * 2, s)
        su += t
        if (t < a):
            return -1
        else:
            c = t - a
    if c == 0:
        return su
    else:
        return -1

print(main())

Submission status: Wrong Answer

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

if a[0]!=0:
    print(-1)
    exit()
c = 1
for i in range(1,n+1):
    c = c*2
    if a[i]>c:
        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())
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]

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

if flag:
    print(sum(sums))
else:
    print(-1)

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 (i<N)&(root_num==0):
        print(-1)
        break
    if root_num < 0:
        print(-1)
        break
else:
    print(count)

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:
  if l[0]==0:
    print(0)
  elif l[0]==1:
    print(1)
  else:
    print(-1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import math

def find_max_verticies(A, i, verticies, prev_verticies):
	max_leaves = 2**i
	a = A[i]
	if a > max_leaves:
		return -1
	if prev_verticies <= 0:
		return -1
	if i == 0:
		if a != 0:
			return -1
		return verticies + 1
	if i == N:
		return find_max_verticies(A, i-1, a, a)
	else:
		min_nonleaf = math.ceil(prev_verticies/2)
		max_nonleaf = min(prev_verticies, max_leaves - a)
		if min_nonleaf + a > max_leaves:
			return -1
		for j in reversed(range(min_nonleaf, max_nonleaf+1)):
			v = find_max_verticies(A, i-1, verticies + j + a, j + a)			
			if v > 0:
				return v
		return -1


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

print(find_max_verticies(A, N, 0, 0))

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 <= -1:
      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:
N=int(input())
*A,=map(int,input().split())
Ar=A[::-1]
ans=[0]*(N+1)
i=0
count=0
while i<=N:
    count+=Ar[i]
    if count>2**(N-i):
        count=2**(N-i)
    ans[-(i+1)]=count
    i+=1

j=0
while j<N:
    if ans[j+1]>2*(ans[j]-A[j]):
        ans[j+1]=max(2*(ans[j]-A[j]),0)
    j+=1

k=0
while k<=N:
    if A[k]>2**k:
        ans[k]=0
    k+=1

if 0 in ans:
    print(-1)
else:
    print(sum(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))

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[-1] = A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Wrong Answer

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

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

B = [0]*(N+1)
B[0] = 1
C = [0] * N
D = A[:]

for i in range(N):
    B[i+1] = 2*(B[i]-A[i])
    C[i] = B[i] - A[i]
    if max(B[i],A[i+1]) > B[i+1]:
        print(-1)
        exit()
D[N] = B[N]

B.append(0)
for i in range(N,-1,-1):
    #print(A,B,C,D)
    if A[i] < D[i]:
        if A[i] >= D[i]//2:
            B[i] = A[i] + B[i+1]
            break
        else:
            r = D[i] - A[i]
            B[i] = B[i+1] + A[i]
            D[i-1] += max(r-C[i-1],0)
            #D.pop()

print(sum(B))

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    l = list(map(int, input().split()))
    limit = [1-l[0]]
    total = 0
    for i in range(1, n+1):
        total = total*2 + l[i-1]*2
        limit.append(pow(2, i) - total)

    for i in limit:
        if i <= 0:
            print(-1)
            break
    else:
        res = []
        temp = 0
        for i in range(n, -1, -1):
            temp = min(limit[i], temp+l[i])
            res.append(temp)
        print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
n = int(stdin.readline())
nmleaves = list(map(int, stdin.readline().strip().split()))

# pref[i]: sum of all elements in nmleaves after i, i.e. sum(nmleaves[i+1:])
full = sum(nmleaves)
tot = 0
pref = [0]*(n+1)
for i, l in enumerate(nmleaves):
    tot += l
    pref[i] = full - tot

if n==0:
    print(0)

else:
    if nmleaves[0]!=0:
        print(-1)
        exit()
    
    ## it exists
    ans = 0
    for level, leaves in enumerate(nmleaves):
        if leaves > 2**(level):
            print(-1)
            exit()

        if level == 0:
            ans += 1
            validnom = 1
        else:
            maxup = 2*validnom
            maxnom = maxup - leaves

            if level+1<len(nmleaves):
                validnom = min(maxnom, pref[level], 2**level)
                ans += (leaves + validnom)
            else:
                ans += leaves
    print(ans)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    # for i in range(N+1):
    #     if A[i] > 2**i:
    #         print(-1)
    #         return
    #     elif A[i] == 2**i and i != N:
    #         print(-1)
    #         return
    #     else:
    #         continue

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


    safe_line = [0]*(N+1)
    safe_line[N] = A[N]

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

    prev = 1
    answer = 1
    
    for i in range(1,N+1):
        if prev*2 > safe_line[i]:
            cur = safe_line[i]
        else:
            cur = prev*2
        answer += cur
        prev = cur - A[i]
        
        if prev <= 0 and i < N:
            print(-1)
            return
    
    print(answer)
    return

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:
n = int(input())
a = list(map(int, input().split()))
if a[0] != 0:
    if n == 0:
        print(1)
    else:
        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
#print(acc)
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()))

ans = 1
now = 1

s = sum(a)
if a[0] == 1 and n != 0:
    ans = -1
elif n == 0:
    if a[0] == 1:
        ans = 1
    else:
        ans = -1
if n == 1 and a[1] >= 3:
    ans = -1
else:
    for i in range(n):
        s -= a[i]
        if a[i] > now:
            ans = -1
            break
        elif s <= (now-a[i])*2:
            now = s
            ans += now
        else:
            now = (now-a[i])*2
            ans += now
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
judge = 0
k = 1
ans = 0
a = list(map(int,input().split()))
for i in range(n+1):
  k = k -a[i]
  if(k<0):
    judge = 1
    print(-1)
    break
  ans += k
  k+=2
if(judge==0):
  print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
p = list(map(int, input().split()))
if (p[0]!=0):
    print(-1)
    exit()
#t = [1,1,0] #最大頂点数、最下段の空いている頂点数、閉じてない頂点数
sum_p = sum(p)
eda = 1
ans = 1
for i in range(1,n+1):
    eda *= 2
    ans += eda
    eda -= p[i]
    sum_p -= p[i]
    #print(i,eda,ans,sum_p)
    if (i!=n and eda<=0):
        print(-1)
        exit()
    if (eda>=sum_p): #広げ切った
        ans -= (eda-sum_p)
        #print(ans)
        for j in range(i+1,n+1):
            ans += sum_p
            sum_p -= p[j]
        print(ans)
        exit()
print(ans)

Submission status: Wrong Answer

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline
mod = 10**9+7

N = Int()
A = IntList()

tmp = 0

for i in range(N+1):
    tmp += A[i]*2**(N-i)
    
if tmp > 2**N:
    print(-1)
    sys.exit()
    
ans = (pow(2,N+1,mod) - 1)%mod
par = 1

B = A[::-1]
ans = 1
par = 1
C = []
MAXpar = B[0]

for i in range(N):
    leaf = B[i]
    if len(C)>=1:
        MINP = C[-1][0]
        MAXP = C[-1][1]
        C.append([(MINP+leaf+1)//2,MAXP+leaf])
    else:
        C.append([(leaf+1)//2,leaf])
        

D = C[::-1]
#print(D)
for i in range(1,N):
    minp,maxp = D[i]
    
    if i<=30:
        ans += A[i]+min(maxp,2*par-A[i])
        #print(A[i],min(maxp,2*par-A[i]))
        par = min(maxp,2*par-A[i])
    else:
        ans += A[i]+min(maxp,2*par)
        #print(A[i],min(maxp,2*par))
        par = min(maxp,2*par)
    
ans += A[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

n = INT()
a = LIST()
if a[0]>0:
    print(1)
    sys.exit()
c = [1]*(n+1)
for i in range(1, n+1):
    c[i] = (c[i-1]-a[i-1])*2
if a[n]>c[n]:
    print(-1)
    sys.exit()
b = [0]*(n+1)
res = [0]*(n+1)
b[n] = a[n]
res[n] = a[n]
for i in range(n-1, -1, -1):
    if (c[i]-a[i])*2 <res[i+1]:
        print(-1)
        sys.exit()
    b[i] = min(c[i]-a[i], res[i+1])
    res[i] = a[i] + b[i]
print(sum(res))

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()
for i in range(min(n - 1, 30)):
    if a[i] > (1 << i) - 1:
        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:
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] == 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:
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 N == 0:
        print(1)
        exit()
    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:
N=int(input())
A=list(map(int,input().split()))
saidai=[0]*(N+1)
back=[0]*(N+1)
if N!=0:
    ans=0
    saidai[0]=1
    for n in range(1,N+1):
        saidai[n]=(saidai[n-1]-A[n-1])*2
        if saidai[n]<=0:
            ans=-1
    for n in range(N+1):
        a=N-n
        if a==N:
            back[a]=A[a]
        else:
            back[a]=back[a+1]+A[a]
    if ans!=-1:
        for n in range(N+1):
            a=N-n
            if saidai[a]>back[a]:
                ans+=back[a]
            else:
                ans+=saidai[a]
    print(ans)

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

Submission status: Wrong Answer

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

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

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

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

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


if judge:
    print(-1)
else:
    print(sum(depth_sum))

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
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())
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 <= -1:
      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:
import sys

def intersection(I1, I2):
    left = max(I1[0], I2[0])
    right = min(I1[1], I2[1])
    return [left, right]


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

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

P = []

P.append([1,1])

for i in range(n):
    left = P[i][0]-A[i+1]
    right = 2*P[i][1]-A[i+1]
    P.append([left, right])

#print("Forward check")
#print(P)

if 0 < P[n][0] or P[n][1] < 0:
    print(-1)
    sys.exit()

P[n] = [0,0]
for i in reversed(range(n)):
    left = A[i+1]+P[i+1][0]
    left = -(-left//2)
    right = A[i+1]+P[i+1][1]
    P[i] = intersection(P[i], [left, right])
#print("Backward check")
#print(P)

ans = 0
for i in range(n+1):
    ans += P[i][1] + A[i]

print(ans)

Submission status: Wrong Answer

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

MAX = [1]
for i in range(N):
  #print(MAX[-1],A[i+1])
  MAX.append((MAX[-1]-A[i])*2)
#print(MAX)

ans = A[-1]
mae = A[-1]
for i in range(N):
  #print(mae)
  if mae%2 == 0:
    tmin = mae//2
  else:
    tmin = mae//2+1
  if tmin + A[-i-2] > MAX[-i-2]:
    print("-1")
    sys.exit()
  tmax = mae+A[-i-2]
  #print(tmax,MAX[-i-2])
  mae = min(tmax,MAX[-i-2])
  ans += mae
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
r = [1]
for i in range(N):
    r.append(r[i]*2)
if N != 0 and A[0] != 0:
    print(-1)
    exit()
if N == 0 and A[0] != 1:
    exit()

p = 0
for i in range(N):
    if A[i] != 0:
        p += A[i]
    p = p * 2 
    r[i+1] -= p
    if r[i] < A[i]:
        print(-1)
        exit()
    if i == N-1 and r[i+1] < A[i+1]:
        print(-1)
        exit()


for i in range(N):
    r[i] -= A[i]


q = A[N]
ans = q

for i in range(N):
    q = min(q,r[N-1-i]) + A[N-1-i]
    ans += q
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(reversed(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.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],(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())
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]
print(-1)
# -1 ではないケースで落ちてる

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())
a = list(map(int,input().split()))

if a[0]!=0:
    print(-1)
    exit()
for i in range(n+1):
    if a[i]>2**i:
        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:
import sys 
n=int(input())
l=list(map(int,input().split()))
w=[1-l[0]]*(n+1)
for i in range(1,n+1):
    w[i]=w[i-1]*2-l[i]
if min(w)<0:
    print(-1)
    sys.exit()
for i in range(1,n+1):
    w[i]+=l[i]
w1=[0]*(n+1)
w1[-1]=l[-1]
for i in range(n-1,-1,-1):
    w1[i]+=w1[i+1]+l[i]
ans=0 
for i in range(n+1):
    ans+=min(w1[i],w[i])
#print(w,w1)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
if n==0:
    if a[0]==0:
        print(0)
    else:
        print(1)
    quit()
if a[0]==1:
    if n!=0:
        print(-1)
        quit()

if a[0]>1:
    print(-1)
    quit()

maxnode=[1]
for i in range(1,n):
    maxnode.append(maxnode[i-1]*2-a[i])
    if maxnode[i-1]*2-a[i]<=0:
        print(-1)
        quit()
# print(maxnode)


ans=1
for i in range(1,n+1)[::-1]: 
    # now=pow(2,i)
    # print(now)

    if i==n:
        if a[i]>maxnode[-1]*2:
            print(-1)
            quit()
        else:
            maxnode[-1]=min(a[i],maxnode[-1])
            ans+=a[i]
    else:
        if maxnode[i]+a[i]>maxnode[i-1]*2:
            print(-1)
            quit()
        else:
            maxnode[i-1]=min(maxnode[i]+a[i],maxnode[i-1])
            ans+=maxnode[i]+a[i]
    
print(ans)

Submission status: Wrong Answer

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


def req_node(i,belowmin,belowmax):

    thismax = belowmax+arr[i]
    thismin = (belowmin+arr[i])//2+(belowmin+arr[i])%2

    return req_node(i-1,thismin,thismax)

bmin = [arr[-1]]
bmax = [arr[-1]]


belowmin = arr[-1]
belowmax = arr[-1]
for i in range(2,n+2):
    thismax = belowmax+arr[-i]
    thismin = (belowmin)//2+(belowmin)%2+arr[-i]
    bmin.append(thismin)
    bmax.append(thismax)
    belowmax = thismax
    belowmin = thismin



bmin.reverse()
bmax.reverse()

# print(bmin)
# print(bmax)

nodes =  1
ans = 0
flag =True
for i in range(n):
    ans += nodes
    # print(nodes,ans)
    nextmax = 2*(nodes-arr[i])
    nextmin = nodes-arr[i]

    nodes = min(bmax[i+1],nextmax)
    if nextmax < bmin[i+1] or nextmin > bmax[i+1]:
        flag = False
        # print("break")
        break

if flag:
    print(ans+arr[-1])
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:
        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()