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

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

sum_leaf = sum(A)
ans = 1
before_top = 1
for i in range(1, len(A)):
    if A[i] <= before_top*2:
        ans += min(sum_leaf, before_top*2)
        before_top = min(sum_leaf, before_top*2) - A[i]
        sum_leaf -= A[i]
    else:
        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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
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 TUPLE(): return tuple(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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()

LR = [[A[-1], A[-1]]]
for i, b in enumerate(A[::-1][1:], 1):
	if i < 30:
		LR.append([-(-LR[-1][0]//2)+b, min(LR[-1][1]+b, pow(2, i))])
	else:
		LR.append([-(-LR[-1][0]//2)+b, LR[-1][1]+b])


LR = LR[::-1]
if LR[0][0] <= 1 <= LR[0][1]:
	pass
else:
	print(-1)
	exit()

ans = 1
tmp = 1
for i, (L, R) in enumerate(LR[1:], 1):
	tmp = min(2*tmp-A[i], R-A[i])
	ans += tmp+A[i]

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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
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 TUPLE(): return tuple(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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()

LR = [[A[-1], A[-1]]]
for i, b in enumerate(A[::-1][1:], 1):
	LR.append([-(-LR[-1][0]//2)+b, min(LR[-1][1]+b, pow(2, i))])

LR = LR[::-1]
if LR[0][0] <= 1 <= LR[0][1]:
	pass
else:
	print(-1)
	exit()

ans = 1
tmp = 1
for i, (L, R) in enumerate(LR[1:], 1):
	tmp = min(2*tmp-A[i], R-A[i])
	ans += tmp+A[i]

print(ans)

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

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

rcA = [0] * (N)
rcA[-1] = A[-1]
for i in range(1, N):
    rcA[-i - 1] = rcA[-i] + A[-i - 1]
# print(rcA)

cnt = 1
node = 1
for a, rca in zip(A, rcA):
    min_node = node - a
    max_node = 2 * (node - a)
    if rca < min_node or min_node < 0:
        print(-1)
        exit()
    node = min(max_node, rca)
    # print(node)
    cnt += node
if node != A[-1]:
    print(-1)
    exit()
print(cnt)

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

if N == 0:
    print(-1)
    exit()

rcA = [0] * (N)
rcA[-1] = A[-1]
for i in range(1, N):
    rcA[-i - 1] = rcA[-i] + A[-i - 1]
# print(rcA)

cnt = 1
node = 1
for a, rca in zip(A, rcA):
    min_node = node - a
    max_node = 2 * (node - a)
    if rca < min_node or min_node < 0:
        print(-1)
        exit()
    node = min(max_node, rca)
    # print(node)
    cnt += node
if node != A[-1]:
    print(-1)
    exit()
print(cnt)

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

if N == 0:
    print(-1)
    exit()

rcA = [0] * (N)
rcA[-1] = A[-1]
for i in range(1, N):
    rcA[-i - 1] = rcA[-i] + A[-i - 1]
# print(rcA)

cnt = 1
node = 1
for a, rca in zip(A, rcA):
    min_node = node - a
    max_node = 2 * (node - a)
    if rca < min_node:
        print(-1)
        exit()
    node = min(max_node, rca)
    # print(node)
    cnt += node
if node != A[-1]:
    print(-1)
    exit()
print(cnt)

Submission status: Wrong Answer

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

mx.append(1)
f=True
d=0
c=0
for i in range(n,-1,-1):
  d+=a[i]
  c+=d
  t=(d+1)//2
  if t>mx[i-1]:
    f=False
    break
  d=min(d,mx[i-1])
print(c if f else -1)

Submission status: Wrong Answer

Solution code:
def solve():
    if N == 0:
        if A[0] == 0:
            return -1
        else:
            return 1

    if A[0] != 0:
        return -1

    tot = sum(A)
    cur = 1
    ans = 1
    for i in range(1, N + 1):
        cur *= 2
        if cur < A[i]:
            return -1
        tmp = min(cur, tot)
        ans += tmp
        cur = tmp - A[i]
        tot -= A[i]
    return ans


N, *A = map(int, open(0).read().split())
print(solve())

Submission status: Wrong Answer

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int();
    A = read_ints();
    B = [0]*(N+1)
    B[N] = A[N]
    for i in range(N-1, -1, -1):
        B[i] = B[i+1]+A[i]
    nodes, answer = 1, 0
    for i in range(N+1):
        if nodes < A[i]:
            print(-1)
            return
        answer += nodes
        nodes -= A[i]
        if i<N:
            nodes = min(2*nodes, B[i+1])
    return answer


if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if a[0] >= 1 or n == 0:
    print(1 if a[0] == 1 and n == 0 else -1)
    exit()
b = [0] * (n + 1)
for i in range(1, n + 1):
    b[i] = a[i] + b[i - 1]
v = 1
ans = 1
for i in range(n):
    if v < 2 * a[i + 1]:
        print(-1)
        exit()
    v = min(b[n] - b[i], 2 * (v - a[i]))
    if v <= 0:
        print(-1)
        exit()
    ans += v
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if a[0] >= 1 or n == 0:
    print(1 if a[0] == 1 and n == 0 else -1)
    exit()
b = [0] * (n + 1)
for i in range(1, n + 1):
    b[i] = a[i] + b[i - 1]
v = 1
ans = 1
for i in range(n):
    if v < a[i + 1]:
        print(-1)
        exit()
    v = min(b[n] - b[i], 2 * (v - a[i]))
    if v <= 0:
        print(-1)
        exit()
    ans += v
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if a[0] >= 1 or n == 0:
    print(1 if a[0] == 1 and n == 0 else -1)
    exit()
b = [0] * (n + 1)
for i in range(1, n + 1):
    b[i] = a[i] + b[i - 1]
v = min(b[n], 2)
ans = 1 + v
for i in range(1, n):
    if v < a[i + 1]:
        print(-1)
        exit()
    v = min(b[n] - b[i], 2 * (v - a[i]))
    if v <= 0:
        print(-1)
        exit()
    ans += v
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    ki = [0 for i in range(n+1)]
    ki[0] = 1   
    for i in range(1,n+1):
        ki[i] = 2*(ki[i-1] - a[i-1])
        if ki[i]<0:
            print(-1)
            return
    if ki[-1] == 0:
        print(-1)
        return
    ki[-1] = min(a[-1],ki[-1])
    for i in range(n):
        ki[n-1-i] = min(ki[n-1-i],ki[n-i]+a[n-1-i])
    print(sum(ki))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    ki = [0 for i in range(n+1)]
    ki[0] = 1   
    for i in range(1,n+1):
        ki[i] = 2*(ki[i-1] - a[i-1])
        if ki[i]<0:
            print(-1)
            return
    if ki[-1] == 0:
        print(-1)
        return
    ki[-1] = a[-1]
    for i in range(n):
        ki[n-1-i] = min(ki[n-1-i],ki[n-i]+a[n-1-i])
    print(sum(ki))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))

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

limit=[1]

for a in A[1:]:
    limit.append(limit[-1]*2-a)

A=A[::-1]
limit=limit[::-1]

ans=A[0]
temp=A[0]


for i in range(len(limit)-1):
    a=limit[i+1]
    b=temp
    x=b-a
    y=a-x
    
    if x<0:
        x=0
        y=temp
    elif y<0:
        print(-1)
        exit()
    
    temp=x+y+A[i+1]
    ans+=temp
        

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))

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

limit=[1]

for a in A[1:]:
    limit.append(limit[-1]*2-a)

A=A[::-1]
limit=limit[::-1]

ans=A[0]
temp=A[0]


for i in range(len(limit)-1):
    a=limit[i+1]
    b=temp
    x=b-a
    y=a-x
    
    if x<0:
        x=0
        y=temp
    elif y<0:
        print(-1)
        exit()
    
    temp=x+y+A[i+1]
    ans+=temp
        

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    all_v = sum(a)
    ans = 0
    if n == 0:
        if a[0] == 0:
            ans = -1
        elif a[0] == 1:
            ans = 1
    elif a[0] != 0:
        ans = -1
    else:
        ans = 1
        max_vertex = 1
        for i in range(1, n + 1):
            max_vertex *= 2
            if max_vertex < a[i]:
                ans = -1
                break
            ans += min(max_vertex, all_v)
            max_vertex = min(max_vertex, all_v) - a[i]
            all_v -= a[i]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[a[0]==0]
for i in a[1:]:
  b+=[2*b[-1]-i]
  if b[-1]<0:
    print(-1)
    exit()
b.pop()
ans=root=a[-1]
a=a[::-1]
b=b[::-1]
for i,j in zip(a[1:],b):
  root=min(root,j)+i
  ans+=root
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input()) ; n+=1
A=list(map(int,input().split()))
if n==0:
    if A[0]==1: print(1);exit()
    print(-1);exit()
if A[0]!=0:print(-1);exit()
ANS=[0]*n ;ANS[0]=1
R=[0]*n
for i in range(n-2,-1,-1):
    R[i]=R[i+1]+A[i+1]
#print(R)
for i in range(1,n):
    ANS[i]=min(ANS[i-1]*2-A[i], R[i])
    if ANS[i]<0:print(-1);exit()
print(sum(A)+sum(ANS))

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
# R=[pow(2,i) for i in range(30)]
ANS=[0]*(n+1) ; ANS[0]=1
TOME=[0]*(n+1)

if n!=0 and A[0]!=0:print(-1);exit()
if n==0:
    if A[0]==1:print(1);exit()
    else: print(-1);exit()
# if n==1:
#     if A[0]==0 and A[1]==1 : print(2);exit()
#     elif A[0]==0 and A[1]==2: print(3);exit()
#     else:print(-1);exit()
    
TOME[n]=A[n]

for i in range(n+1):
    TOME[i]=A[i]
    if i!=0:
        ANS[i]=ANS[i-1]*2-TOME[i]
ANS[n]=0
for i in range(n-1,-1,-1):
    if TOME[i+1]+ANS[i+1]< ANS[i]:
        ANS[i]= TOME[i+1]+ANS[i+1] 

for i in range(n+1):
    if ANS[i]<0: print(-1);exit()
print(sum(ANS)+sum(TOME))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
# R=[pow(2,i) for i in range(30)]
ANS=[0]*(n+1) ; ANS[0]=1
TOME=[0]*(n+1)

if n!=0 and A[0]!=0:print(-1);exit()
if n==0:
    if A[0]==1:print(1);exit()
    else: print(-1);exit()
if n==1:
    if A[0]==0 and A[1]==1 : print(2);exit()
    elif A[0]==0 and A[1]==2: print(3);exit()
    else:print(-1);exit()
    
TOME[n]=A[n]

for i in range(n+1):
    TOME[i]=A[i]
    if i!=0:
        ANS[i]=ANS[i-1]*2-TOME[i]
ANS[n]=0
for i in range(n-1,-1,-1):
    if TOME[i+1]+ANS[i+1]< ANS[i]:
        ANS[i]= TOME[i+1]+ANS[i+1] 
    else:
        break

for i in range(n+1):
    if ANS[i]<0: print(-1);exit()
print(sum(ANS)+sum(TOME))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
R=[pow(2,i) for i in range(30)]
ANS=[0]*(n+1) ; ANS[0]=1
TOME=[0]*(n+1)

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

for i in range(n+1):
    TOME[i]=A[i]
    if i!=0:
        ANS[i]=ANS[i-1]*2-TOME[i]
ANS[n]=0
for i in range(n-1,-1,-1):
    if TOME[i+1]+ANS[i+1]< ANS[i]:
        ANS[i]= TOME[i+1]+ANS[i+1] 
    else:
        break

for i in range(n+1):
    if ANS[i]<0: print(-1);exit()
print(sum(ANS)+sum(TOME))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
R=[pow(2,i) for i in range(30)]
ANS=[0]*(n+1) ; ANS[0]=1
TOME=[0]*(n+1)

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

for i in range(n+1):
    TOME[i]=A[i]
    if i!=0:
        ANS[i]=ANS[i-1]*2-TOME[i]
ANS[n]=0
for i in range(n-1,-1,-1):
    if ANS[i]<0: print(-1);exit()
    if TOME[i+1]+ANS[i+1]< ANS[i]:
        ANS[i]= TOME[i+1]+ANS[i+1] 
    else:
        break

    
print(sum(ANS)+sum(TOME))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
R=[pow(2,i) for i in range(30)]
ANS=[0]*(n+1) ; ANS[0]=1
TOME=[0]*(n+1)

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

for i in range(n+1):
    TOME[i]=A[i]
    if i!=0:
        ANS[i]=ANS[i-1]*2-TOME[i]
ANS[n]=0
for i in range(n-1,-1,-1):
    if TOME[i+1]+ANS[i+1]< ANS[i]:
        ANS[i]= TOME[i+1]+ANS[i+1] 
    else:
        break

    
print(sum(ANS)+sum(TOME))

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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


#for i in range(N+1):
#    tmp = A[i]
#   for j in range(i+1,N+1):
#        maxP[j]=maxP[j]-tmp*pow(2,j-i)
lostP = [0]*(N+1)
for i in range(1,N+1):
    lostP[i] = lostP[i-1]*2+A[i-1]*2




point = [0]*(N+1)
point[-1]=A[-1]
for i in range(N-1,-1,-1):
    
    if pow(2,i) - lostP[i] <= A[i]:
        print(-1)
        exit()
    point[i] = min( pow(2,i) - lostP[i] , point[i+1]+A[i])
print(sum(point))

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

maxP = [pow(2,i) for i in range(N+1)]
#for i in range(N+1):
#    tmp = A[i]
#   for j in range(i+1,N+1):
#        maxP[j]=maxP[j]-tmp*pow(2,j-i)
lostP = [0]*(N+1)
for i in range(1,N+1):
    lostP[i] = lostP[i-1]*2+A[i-1]*2
    maxP[i] = maxP[i] - lostP[i]



point = [0]*(N+1)
point[-1]=A[-1]
for i in range(N-1,-1,-1):
    
    if maxP[i] <= A[i]:
        print(-1)
        exit()
    point[i] = min( maxP[i] , point[i+1]+A[i])
print(sum(point))

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

maxP = [pow(2,i) for i in range(N+1)]
for i in range(N+1):
    tmp = A[i]
    for j in range(i+1,N+1):
        maxP[j]=maxP[j]-tmp*pow(2,j-i)



point = [0]*(N+1)
point[-1]=A[-1]
for i in range(N-1,-1,-1):
    
    if maxP[i] <= A[i]:
        print(-1)
        exit()
    point[i] = min( maxP[i] , point[i+1]+A[i])
print(sum(point))

Submission status: Wrong Answer

Solution code:

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

cnt = [0] * (N + 1)
cnt[0] = 1
for i in range(N):
    cnt[i + 1] = (cnt[i] - X[i]) * 2

ans = 0
cur = 0
for i in reversed(range(N + 1)):
    cur += X[i]
    ans += min(cnt[i], cur)

if all(cnt[i] >= X[i] for i in range(N)):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

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

ans=1
p=1
for i in range(1,N):
    p=min(p*2,sumA)
    ans+=p
    p=p-A[i]
    sumA-=A[i]
    if p<=0:
        print(-1)
        exit()


if p<=A[N]<=p*2:
    print(ans+A[N])
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()

ans=1
p=1
for i in range(1,N+1):
    p=min(p*2,sum(A[i:]))
    ans+=p
    p=p-A[i]
    if p<=0:
        print(-1)
        exit()


print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)


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

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

def rec(x,y,ans,N):
    if y==N-1:
        n=x-A[y]
        if n>0:
            for i in range(n+1):
                cnt=i+2*(n-i)

                if cnt==A[N]:
                    print(ans+cnt)
                    exit()
    else:
        n=x-A[y]
        cnt=min(n*2,sum(A[y+1:]))
        rec(cnt,y+1,ans+cnt,N)

rec(1,0,1,N)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)


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

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

def rec(x,y,ans,N):
    if y==N-1:
        n=x-A[y]
        if n>0:
            for i in range(n+1):
                cnt=i+2*(n-i)

                if cnt==A[N]:
                    print(ans+cnt)
                    exit()
    else:
        n=x-A[y]
        for i in range(n+1):
            cnt=i+2*(n-i)
            if cnt<=sum(A[y:]):
                rec(cnt,y+1,ans+cnt,N)

rec(1,0,1,N)
print(-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N==0:
    if A[0]==1:
        print(1)
    else:
        print(-1)
else:
    B = [0 for _ in range(N+1)]
    B[0]=1
    flag = 0
    for i in range(1,N):
        if A[i]>2*B[i-1]:
            flag = 1
            break
        B[i]=2*B[i-1]-A[i]
    if A[N]>2*B[N-1]:
        flag = 1
    else:
        n = (A[N]+1)//2
        i = N-1
        k = B[i]-n
        while k>0:
            B[i] -= k
            k = k//2
            i -= 1
    tot = 0
    for i in range(N+1):
        tot += B[i]+A[i]
    if flag==0:
        print(tot)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
#解きかけ202007252057
n = int(input())
a = list(map(int, input().split()))

l = []
x = 0
for i in a[::-1]:
    #print(i)  #
    l.append(i + x)
    x = 1

#print(l)
print(sum(l))

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
def pow_k(x, n):

    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    accum = sum(a)
    ans = 1
    b = [0] * (n + 1)
    b[0] = 1
    for i in range(1, n + 1):
        accum -= a[i]
        b[i] = min(2 * b[i - 1] - a[i], accum)
        if b[i] < 0:
            ans = -1
            break
        ans += b[i] + a[i]
        
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
def pow_k(x, n):

    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    accum = sum(a)
    ans = 0
    b = [0] * (n + 1)
    for i in range(1, n + 1):
        accum -= a[i]
        b[i] = min(2 * b[i - 1] - a[i], accum)
        if b[i] < 0:
            ans = -1
            break
        ans += b[i] + a[i]
        
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = list(map(int, input().split()))
    leaf = sum(A)
    M = [0]*(N+1)
    if N==0:
        if A[0]==1:
            print(1)
            exit()
        else:
            print(-1)
            exit()
    if A[0]==1:
        print(-1)
        exit()
    M[0] = 1
    for i in range(1,N+1):
        M[i] = 2*M[i-1] - A[i]
        leaf -= A[i]
        M[i] = min(M[i],leaf)
        if M[i] < 0:
            print(-1)
            exit()
    print(sum(M)+sum(A))
    print(M,A)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = list(map(int, input().split()))
    M = [0] * (N+1)
    B = [0] * (N+1)
    if N==0:
        if A[0]==1:
            print(1)
            exit()
        else:
            print(-1)
            exit()
    M[0] = 1
    for i in range(1,N):
        M[i] = 2*(M[i-1] - A[i-1])
        if M[i] <= 0:
            print(-1)
            exit()
    A = A[::-1]
    M = M[::-1]
    for i in range(1,N+1):
        B[i] = min(M[i]-A[i], A[i-1]+B[i-1])
        if B[i]<=0:
            print(-1)
            exit()
    if B[-1]!=1:
        print(-1)
        exit()
    print(sum(B)+sum(A))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = list(map(int, input().split()))
    M = [0] * (N+1)
    B = [0] * (N+1)
    if N==0:
        if A[0]==1:
            print(1)
            exit()
        else:
            print(-1)
            exit()
    M[0] = 1
    for i in range(1,N):
        M[i] = 2*(M[i-1] - A[i-1])
        if M[i] <= 0:
            print(-1)
            exit()
    A = A[::-1]
    M = M[::-1]
    for i in range(1,N+1):
        B[i] = min(M[i]-A[i], A[i-1]+B[i-1])
        if B[i]<0:
            print(-1)
            exit()
    if B[-1]!=1:
        print(-1)
        exit()
    print(sum(B)+sum(A))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = list(map(int, input().split()))
    M = [0] * (N+1)
    B = [0] * (N+1)
    M[0] = 1
    for i in range(1,N):
        M[i] = 2*(M[i-1] - A[i-1])
        if M[i] <= 0:
            print(-1)
            exit()
    A = A[::-1]
    M = M[::-1]
    for i in range(1,N+1):
        B[i] = min(M[i]-A[i], A[i-1]+B[i-1])
        if B[i]<0:
            print(-1)
            exit()
    if B[-1]!=1 and N>0:
        print(-1)
        exit()
    print(sum(B)+sum(A))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = list(map(int, input().split()))
    M = [0] * (N+1)
    B = [0] * (N+1)
    M[0] = 1
    for i in range(1,N):
        M[i] = 2*(M[i-1] - A[i-1])
        if M[i] <= 0:
            print(-1)
            exit()
    A = A[::-1]
    M = M[::-1]
    for i in range(1,N+1):
        B[i] = min(M[i]-A[i], A[i-1]+B[i-1])
        if B[i]<0:
            print(-1)
            exit()
    if B[-1]!=1:
        print(-1)
        exit()
    print(sum(B)+sum(A))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A= list(map(int, input().split()))
S = sum(A)
ans = 0
leaf = 1
S_now = 0

if A[0] == 1:
  if N==0:
    print(1)
  else:
    print(-1)
elif A[0] != 0:
  print(-1)
else:
  for i in range(N):
    ans += leaf
    leaf -= A[i]
    S_now += A[i] 
    leaf = min(leaf*2,S-S_now)

print(ans+A[-1])

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
a=list(map(int,input().split()))
b_d=[[0,0] for _ in range(n+1)]
b_u=[[0,0] for _ in range(n+1)]
b_d[n]=[a[n],a[n]]
b_u[0]=[1,1]
for i in range(1,n+1):
    l=(1+b_d[n+1-i][0])//2+a[n-i]
    r=min(pow(2,n-i),b_d[n+1-i][1])+a[n-i]
    if l>r:
        print("###",-1)
        exit()
        break
    b_d[n-i]=[l,r]
    l=max(0,b_u[i-1][0]-a[i-1])
    r=2*(b_u[i-1][1]-a[i-1])
    if l>r:
        print(">>>",-1)
        exit()
        break
    b_u[i]=[l,r]
ans=0

for i in range(n+1):
    if b_d[i][0]>b_u[i][1] or b_u[i][0]>b_d[i][1]:
        print(-1)
        exit()
    else:
        ans+=min(b_u[i][1],b_d[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

# Aの累積和 (残っている葉の数) の逆
cA = list(accumulate(A[::-1]))[::-1]

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

# 頭から計算
total = 1
in_n = 1
# print(N)
# print(A)
# print(cA)
for depth in range(1, N):
    max_nodes = in_n * 2 - A[depth]
    in_n = min(max_nodes, cA[depth] - A[depth])
    total += in_n + A[depth]
    # print(depth, max_nodes, in_n, total)
total += A[N]
print(total)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
flg = True
n_leaf = 0.5
for a in A:
    if a > 2*n_leaf:
        flg = False
        break
    n_leaf = a
print(sum(A) if flg else -1)