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

node_d = [0 for i in range(n + 1)]

# 深さごとのノードの個数の最大値を求める
node_d[0] = 1
for i in range(n):
    node_d[i + 1] = 2 * (node_d[i] - a[i])
    if a[i + 1] > node_d[i + 1]:
        print(-1)
        exit()

node_d[n] = a[n]

for i in range(n - 1, -1, -1):
    # 1つ下のノードの個数+今回の葉の個数（最大値を超えないように）
    node_d[i] = min(node_d[i], node_d[i + 1] + a[i])

for i in node_d:
    if i == 0:
        print(-1)
        exit()

print(sum(node_d))

Submission status: Wrong Answer

Solution code:
N = int(input()) + 1
A = list(map(int, input().split()))
can_create = True

# max internal node
MI = [0 for _ in range(N)]
MI[0] = 1

for i in range(1, N):
    MI[i] = (MI[i-1] - A[i-1]) * 2
    if MI[i] <= 0:
        can_create = False

results = [0 for _ in range(N)]
results[N-1] = A[N-1]
for i in range(N-2, -1, -1):
    results[i] += min(results[i+1] + A[i], MI[i])
    if results[i] <= 0:
        can_create = False

if can_create:
    print(sum(results))
else:
    print(-1)

# print(MI)
# print(results)

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]

#print(sums)

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

#print(p)
#print(sums)

if flag or (sums[n-1]-p[n-1])*2<sums[n]:
    print(-1)
else:
    print(sum(sums))

Submission status: Wrong Answer

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

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


if n == 0:
    if a[0] == 2:
        print(3)
    elif a[0] == 1:
        print(2)
    exit()

max_num_list = [0]*(n+1)
max_num_list[0] = 1
next_ = 1
for i in range(1, n+1):
    max_num = next_*2
    next_ = max_num-a[i]
    max_num_list[i] = max_num
# print(max_num_list)

list_ = [0]*(n+1)
ans = 0
before = 0
for i in range(n, -1, -1):
    max_num = max_num_list[i]
    if before > (max_num-a[i])*2:
        print(-1)
        exit()
    if max_num-a[i] <= before:
        num = max_num
    else:
        num = before+a[i]
    list_[i] = num
    before = num
    # print(list_)
list_.reverse()
print(sum(list_))

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 if e==k else -1)

Submission status: Wrong Answer

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

apex = [0]*(N+1)
apex[0] = 1
a = 0
listed = [0]*(N+1)
listed[0] = 1
listed[N] = A[N]

if (A[0] != 0)&(N != 0):
    a = 1

for d in reversed(range(1,N)): #N-1から1まで
    listed[d] = listed[d+1] + A[d]

for d in range(1,N+1):
    listed[d] = min(listed[d],apex[d-1]*2)
    apex[d] = listed[d] - A[d]
    if A[d] > listed[d]:
        a = 1
        break


if a == 1:
    print('-1')
else:
    print(sum(listed))

Submission status: Wrong Answer

Solution code:
n= int(input())

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

#print(a)

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

b=1
count=1

for i in range(n-1):
    if a[i+1] > 2*b:
        print(-1)
        exit(0)
    else:
        b= 2*b-a[i+1]
        count += 2*b


print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
least = [0] * (n+2)
good = 1
for i in reversed(range(n+1)):
	least[i] = (least[i+1] + 1) // 2 + a[i]
	if i <= 52 and least[i] > 2**i:
		good = 0
		break
if good == 0:
	print(-1)
	exit(0)

ans = [0] * (n+2)
for i in reversed(range(n+1)):
	if i >= 500:
		ans[i] = ans[i+1] + a[i]
		continue

	lo, hi = 0, ans[i+1]//2
	while lo < hi:
		mid = (lo + hi) // 2
		v = ans[i+1] + a[i] - lo
		good = 1
		if i <= 52 and v > 2**i:
			good = 0
		for j in reversed(range(i)):
			v = (v + 1) // 2 + a[j]
			if j <= 52 and v > 2**j:
				good = 0
				break
		if good == 1:
			hi = mid
		else:
			lo = mid + 1
	ans[i] = ans[i+1] + a[i] - lo
print(sum(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())

nodes=[1]

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

for i in range(n):
    nodes.append(pow(2,i))

nodes = list(reversed(nodes))
a=list(reversed(a))

for i in range(n):
    if i==0:
        nodes[i] = a[i]
    else:
        if (nodes[i-1] + a[i])<=pow(2,n-i):
            nodes[i] = (nodes[i-1] + a[i])
        else:
            nodes[i] = pow(2,n-i)

# print(nodes)

print(sum(nodes))

Submission status: Wrong Answer

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

sum_a = [ sum( a[d:n+1] ) for d in range( n+1 ) ]
d_vertex = [ 0 for d in range( n + 1 ) ]

d_vertex[ 0 ] = 1
num_of_v = d_vertex[ 0 ]
for d in range( 1, n + 1 ):
    d_vertex[ d ] = min( sum_a[d], ( d_vertex[ d - 1 ] - a[ d - 1 ] ) * 2 )
    if d_vertex[ d ] <= 0:
        print( -1 )
        exit()
    num_of_v += d_vertex[ d ]
    # print( d, d_vertex )

print( num_of_v )

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(len(l))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def rec(i, A, ok_v):
    # print(i, A, ok_v)
    if ok_v <= 0:
        return -1, -1
    if i == len(A) - 1:
        return A[-1], A[-1]
    if i > 70:
        child, ans = rec(i + 1, A, -1)
        if child == ans == -1:
            return -1, -1
        else:
            return child + A[i], child + A[i] + ans
    child, ans = rec(i+1, A, (ok_v - A[i]) * 2)
    #print("\t", i, child, ans)
    if child == ans == -1:
        return -1, -1
    num_v = min(ok_v, child + A[i])
    return num_v, ans + num_v


def main() -> None:
    N = int(input())
    A = [int(x) for x in input().split()]
    if N == 0:
        print(1 if A[0] == 1 else -1)
        return
    elif A[0] != 0:
        print(-1)
        return

    _, ans = rec(1, A, 2)
    print(ans + 1 if ans > 0 else -1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
input()
input()
print(1)

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)
            return
    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:
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 ] != 0:
            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 i != n+1 and px <= 0:
            ans = -1
            break
        elif i == n+1 and sump != 0:
            ans = -1
            break

print( ans )

Submission status: Wrong Answer

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N = ri()
A = ri_()
# 限界値
B = [1] * (N + 1)
# 葉でない頂点の数
C = [0] * (N + 1)
if A[0] > 0:
    print(-1)
    exit()
for i in range(1, N + 1):
    B[i] = B[i - 1] * 2 - A[i]
    if B[i] <= 0:
        print(-1)
        exit()
for i in reversed(range(0, N)):
    C[i] = min(A[i + 1] + C[i + 1], B[i])
print(sum(A) + sum(C))
# print('A:', A)
# print('C:', C)
# print('B:', B)

Submission status: Wrong Answer

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

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

A.reverse()
MAX.reverse()

MIN = 0
s = 0
for i,a in enumerate(A):
    s = min(s+a,2**(N-i))
    MIN += s
print(MIN)

Submission status: Wrong Answer

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

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

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

# 根の数
node = 1
root = 0

s = sum(A)

for i in range(len(A) - 1):
    node = min(s, node * 2) - A[i + 1]
    if node < 0:
        print(-1)
        exit()
    
    s -= A[i + 1]
    root += node

print(root + sum(A) + 1)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    line = list(map(int,input().split()))
    if n == 0:
        if line[0] == 0:
            return -1
        else:
            return 1
    if line[0] > 0:
        return -1
    front = [0 for i in range(n+1)]
    back = [0 for i in range(n+1)]
    front[0] = 1
    for i in range(n):
        if front[i] * 2 < line[i+1]:
            return -1
        front[i+1] = min(10**30,front[i]*2-line[i+1])
    back[n] = line[n]
    for i in range(n):
        p = n - i - 1
        back[p] = back[p+1] + line[p]
    ans = 0
    for i in range(n):
        ans += line[i]
        ans += min(front[i],back[i]-line[i])
    ans += line[n]
    return ans


print(main())

Submission status: Wrong Answer

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

import math

Min=[0]*(n+1)
Max=[0]*(n+1)
true=[0]*(n+1)
ans=sum(a)
fault=0

if a[0]==0:
  Min[0]=1
  Max[0]=1
elif n!=0:
  #print('koko')
  fault=1

for i in range(1,n):
  m=Min[i-1]-a[i]
  M=Max[i-1]*2-a[i]
  if M<0:
    fault=1
    #print('i')
    break
  Min[i]=max(m,0)
  Max[i]=M

#print(Min)
#print(Max)

if a[n]<Min[n-1] or 2*Max[n-1]<a[n]:
  fault=1
#else:
  #Min[n]=a[n]
  #Max[n]=a[n]
  #true[n]=a[n]

for i in reversed(range(1,n)): 
  true[i]=min(Max[i],true[i+1]+a[i+1])
  ans+=true[i]

if fault==1:
  print(-1)
else:
  print(ans+1)

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

balls = [0] * (n + 1)

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

for i in range(n+1):
  balls[i] += A[i]

box = [0] * (n + 1)
box[-1] = A[-1]

for i in range(n-1, -1, -1):
  box[i] = box[i + 1] + A[i]

ans = 0
for i, j in zip(balls, box):
  ans += min(i, j)

# print(balls)
# print(box)

print(ans)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    # if N == 0:
    #     if A[0] > 1:
    #         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):
        cur = min(prev*2,safe_line[i])
        answer += cur
        prev = cur - A[i]
        
        # if prev <= 0 and i < N:
        #     print(-1)
        #     return
        # elif 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()))
r = [1]
for i in range(N):
    r.append(r[i]*2)
    if N != 0 and A[i] >= pow(2,i):
        print(-1)
        exit()

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

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

C = [0]*(N+2)
for i in range(N,-1,-1):
    C[i] = C[i+1] + A[i]
C = C[:-1]

D = [min(b,c) for b,c in zip(B,C)]
print(sum(D))

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    low, high = A[N], A[N]
    maxN = [0] * (N + 1)
    lowN = [0] * (N + 1)
    maxN[N] = A[N]
    lowN[N] = A[N]

    for i in reversed(range(N)):
        leaf = A[i]
        maxNode = 2 * 10 ** 8
        if i <= 30: maxNode = pow(2, i)
        low = (low + 1) // 2 + leaf
        high += leaf
        divLow = low
        count = 0
        while divLow > 0:
            divLow //= 2
            count += 1
        if count > i + 1:
            print(-1)
            break
        else: 
            lowN[i] = low
            maxN[i] = min(high, maxNode)
    else:
        #print(maxN)
        for i in range(N - 1):
            if (maxN[i] - A[i]) * 2 <= maxN[i+1]: maxN[i + 1] = (maxN[i] - A[i]) * 2
        if maxN[N-1] - A[N-1] <= A[N] <= 2 * (maxN[N-1] - A[N-1]): print(sum(maxN))
        else: print(-1)
        #print(maxN)
        #print(lowN)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

ans=0
bef=0

tmp=[]

for i in range(N+1):
    if i==0:
        if A[0]==1:
            bef=0
        else:
            bef=1
        tmp.append(1)
        continue
    elif (bef*2-A[i])>=0:
        bef=bef*2-A[i]
        tmp.append(bef)
    else:
        print("-1")
        exit()

for i in range(N+1):
    current=A[-(i+1)]
    if i==0:
        bef=current
        ans+=current
        continue
    else:
        tmpp = tmp[-(i+1)]
        if current+bef > tmpp:
            ans+=tmpp+current
            bef=tmpp+current
        else:
            ans+=current+bef
            bef=current+bef

print(ans)

Submission status: Wrong Answer

Solution code:
# 深さdの上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))
for i in range(N):
    if A[i] > 2**i:
        print(-1)
        exit()

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

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

# 最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]

print(sum(ans))

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]
for i in range(n-1,-1,-1):
    l[i]+=l[i+1]
ans=0 
for i in range(n+1):
    ans+=min(l[i],w[i])
#print(w,w1)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
a = a
count = 0
c = 0
b = a[-1]
for i in range(len(a)):
    if a[-i] > 2 ** (N- i):
        c = 1
        break
    else:
        count += a[-i]
        count += b

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

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
        element += feuille + racine
    else:
        element = -7
        exit()
    
    i += 1
print(element)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())))
l = 0
n = 1
b = 0
g = np.zeros(N+1)
for i in range(N+1):
    if a[i] > n * 2:
        l = -1
        break
    if a[i] > 2**i:
        l = -1
        break
    g[i] = n
    l += n
    n = (n-a[i])*2
g[N] = a[N]
print(g[N])
for i in range(1, N+1):
    if l<0:
        break
    b = N-i
    if g[b] > g[b+1]+a[b]:
        g[b] = g[b+1]+a[b]
    print(g[b])
if a[0] != 0 or l == -1:
    print(-1)
else:
    print(int(sum(g)))

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
for i in range(min(n+1,40)):
  if a[i]>2**i:
    print(-1)
    sys.exit()
if a[0]!=0 and n!=0:
  print(-1)
  sys.exit()
A=[0]
for i in range(n+1):
  A.append(A[-1]+a[i])
s=sum(a)
ans=1
x=1
for i in range(1,n+1):
  S=s-A[i]
  if i<=50:
    if x*2<S:
      ans+=x*2
      x*=2
      x-=a[i]
    else:
      x=S
      ans+=x
  else:
    ans+=S
print(ans)

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

if x[-1]<a[-1]:
    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:
from itertools import *
n,*a=map(int,open(0).read().split())
b=list(accumulate(a[::-1]))
b=b[::-1][1::]
c=[1]*n
# if a[0]!=0:
#     print(-1)
#     exit()
for i in range(1,n):
    c[i]=min(c[i-1]*2-a[i],b[i])
    if c[i-1]*2-a[i]<1:
        print(-1)
        exit()
print(sum(a)+sum(c))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
cir = 0
sum = 0
hantei=0

lis = [1]
for i in range(n):
    cc = lis[-1] - a[i]
    cc *=2
    if cc<=0:
        hantei=1
    lis.append(cc)

#print(lis)



for i in range(n+1):
    tmp = a[-1-i]+cir
    sum += tmp
    #print(tmp,cir)
    if i==n:
        break
    if tmp <= lis[-1-i] and tmp+a[-2-i]>lis[-2-i]:
        if tmp%2==0:
            cir = tmp//2
        else:
            cir = tmp//2+1
    else:
        cir = tmp
if hantei==1:
    print(-1)
else:
    print(sum)

Submission status: Wrong Answer

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


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

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

Submission status: Wrong Answer

Solution code:
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==0:
    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()))
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))
else:
    print(-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#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 A[0]>0:
        print(-1)
        break
    if (i<N)&(root_num==0):
        print(-1)
        break
    if root_num < 0:
        print(-1)
        break
else:
    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)

b[0] = 1
for i in range(n):
    b[i+1] = 2*(b[i] - a[i])
#根から計算した深さごとの要素数の最大値

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]
#葉から計算した最小値

#print(b)
#print(c)

d = [0]*(n+1)
flag = 0
for k in range(n+1):
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1

print(sum(d) if flag == 0 else -1)

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]==1:
    print(1)
  else:
    print(-1)
else:
  print(-1)

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

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

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

Submission status: Wrong Answer

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

balls = [0] * (n + 1)

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

for i in range(n+1):
  balls[i] += A[i]

box = [0] * (n + 1)
box[-1] = A[-1]

for i in range(n-1, -1, -1):
  box[i] = min(box[i + 1] + A[i], 2 ** i)

ans = 0
for i, j in zip(balls, box):
  ans += min(i, j)

# print(balls)
# print(box)

print(ans)

Submission status: Wrong Answer

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