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:
import math
from collections import deque
import copy

n = int(input())
ad1 = deque([int(i) for i in input().split()])
ad2 = copy.deepcopy(ad1)
total = 0
mi = 0
ma = 0
l_mami = deque()
f = True



for i in reversed(range(n+1)):
  a = ad1.pop()
  mi = math.ceil(mi / 2) + a
  if mi > 2**i:
    print(-1)
    f = False
    break
  ma = ma + a
  l_mami.append((mi, ma))  
  
if f:
  ma = 1
  total = 1
  l_mami.pop()
  for i in range(1,n):
    ma = min((ma - ad2.popleft())*2, l_mami.pop()[1])
    total += ma
  total += ad2.pop()
  print(total)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if a[0]!=0:
    print(-1)
    exit()
l=[[] for _ in range(n+1)]
l[0]=[1,1]
l[n]=[a[n],a[n]]
for i in reversed(range(1,n)):
    if l[i+1][0]%2==1:
        l[i]=[l[i+1][0]//2+a[i]+1,l[i+1][1]+a[i]]
    else:
        l[i]=[l[i+1][0]//2+a[i],l[i+1][1]+a[i]]
ans=[0]*(n+1)
ans[0]=1
for i in range(1,n+1):
    if ans[i-1]*2>=l[i][0]:
        ans[i]=min((ans[i-1]-a[i-1])*2,l[i][1])
    else:
        print(-1)
        exit()
print(sum(ans))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * (n+1)
    if n == 1 and A[0] != 0:
        print(-1)
        exit()
        
    # Adが葉の個数、Bdが葉でないものの個数
    # A0 + B0 = 1
    # Bd ≤ Ad+1 + Bd+1 ≤ 2Bd --> B[d-1] - A[d] ≤ B[d] ≤ 2B[d-1] - A[d]
    # Bd ≤ Ad+1 + Ad+2 + · · · + AN = s - (A1 + ... + Ad)

    # now_s :葉の数
    now_s = sum(A)
    s = now_s
    for i in range(n+1):
        if i == 0:
            B[i] = 1 - A[i]
        else:
            now_s -= A[i]
            B[i] = min(now_s, 2 * B[i - 1] - A[i])
            #print(A,B,now_s)
            if B[i] < 0:
                print(-1)
                exit()

    print(sum(B) + s)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * (n+1)
    if n == 1 and A[0] == 0:
        print(-1)
        exit()
        
    # Adが葉の個数、Bdが葉でないものの個数
    # A0 + B0 = 1
    # Bd ≤ Ad+1 + Bd+1 ≤ 2Bd --> B[d-1] - A[d] ≤ B[d] ≤ 2B[d-1] - A[d]
    # Bd ≤ Ad+1 + Ad+2 + · · · + AN = s - (A1 + ... + Ad)

    # now_s :葉の数
    now_s = sum(A)
    s = now_s
    for i in range(n+1):
        if i == 0:
            B[i] = 1 - A[i]
        else:
            now_s -= A[i]
            B[i] = min(now_s, 2 * B[i - 1] - A[i])
            #print(A,B,now_s)
            if B[i] < 0:
                print(-1)
                exit()

    print(sum(B) + s)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 初期入力
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
child =[0]*(N+1)
child[0] =2

#根→葉に向かって、子の最大値
if N ==0 :
    if A[0] ==1:
        child[0] =0
    else:
        print(-1)
        exit()

#A[0] ==0はエラー＝根は頂点１つ（N=0の時はOK)
if A[0] !=0:
    print(-1)
    exit()

for i in range(1,N):
    child[i] =2*(child[i-1] -A[i])
    if child[i]<0: #子がマイナスはありえない
        print(-1)
        exit()

#葉→根に向かって子と葉の関係を見る
if child[N-1] *2 <A[N]:
    print(-1)
    exit()
else:
    child[N-1] =min(A[N],child[N-1])
for i in range(N-2,-1,-1):
    child[i] =min(child[i],child[i+1] +A[i+1] )

print(sum(child) +1) #根も頂点、＋１

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * (n+1)
    # Adが葉の個数、Bdが葉でないものの個数
    # A0 + B0 = 1
    # Bd ≤ Ad+1 + Bd+1 ≤ 2Bd --> B[d-1] - A[d] ≤ B[d] ≤ 2B[d-1] - A[d]
    # Bd ≤ Ad+1 + Ad+2 + · · · + AN = s - (A1 + ... + Ad)

    # now_s :葉の数
    now_s = sum(A)
    s = now_s
    for i in range(n+1):
        if i == 0:
            B[i] = 1 - A[i]
        else:
            now_s -= A[i]
            B[i] = min(now_s, 2 * B[i - 1] - A[i])
            #print(A,B,now_s)
            if now_s < 0:
                print(-1)
                exit()

    print(sum(B) + s)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * (n+1)
    # Adが葉の個数、Bdが葉でないものの個数
    # A0 + B0 = 1
    # Bd ≤ Ad+1 + Bd+1 ≤ 2Bd --> B[d-1] - A[d] ≤ B[d] ≤ 2B[d-1] - A[d]
    # Bd ≤ Ad+1 + Ad+2 + · · · + AN = s - (A1 + ... + Ad)

    # now_s :葉の数
    now_s = sum(A)
    s = now_s
    for i in range(n+1):
        if i == 0:
            B[i] = 1 - A[i]
        else:
            now_s -= A[i]
            B[i] = min(now_s, 2 * B[i - 1] - A[i])
            #print(A,B,now_s)
            if B[i] < 0:
                print(-1)
                exit()

    print(sum(B) + s)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
if H[0]>1 and N==0:
    print(-1)
    exit()
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
if H[N]!=0:
    depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
if H[N]==0:
    print(sum(depth)+depth[-1]*2)
else:print(sum(depth))

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
if H[0]>1 and N==0:
    print(-1)
    exit()
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
if H[N]!=0:
    depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
print(sum(depth))

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
if H[0]>1 and N==0 or H[N]==0:
    print(-1)
    exit()
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
print(sum(depth))

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
if H[0]>1 and N==0:
    print(-1)
    exit()
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
print(sum(depth))

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
if H[0]==1 and N==0:
    print(1)
    exit()
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
print(sum(depth))

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
if H[0]==1 and N==1:
    print(1)
    exit()
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
print(sum(depth))

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
if H[0]>0 and N==1:
    print(1)
    exit()
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
print(sum(depth))

Submission status: Wrong Answer

Solution code:
n = int(input())
ai = [int(i) for i in input().split()]

tmp = 0
ans = 0
old = 0

a_mnmx = [[0 for i in range(2)] for j in range(n+1)]
#print(a_max)
old = ai[n]

a_mnmx[n][0] = old
a_mnmx[n][1] = old

for i in range(n):
    a_mnmx[n-i-1][0] = (a_mnmx[n-i][0]+1)//2 + ai[n-i-1]
    a_mnmx[n-i-1][1] = a_mnmx[n-i][1] + ai[n-i-1]
    
#print(a_mnmx)

if a_mnmx[0][1] <= 1 or a_mnmx[0][0] > 1:
    print(-1)
    exit()

old = 1
ans = 1

for i in range(n):
    old = min(a_mnmx[i+1][1],old*2)
    ans += old
    old -= ai[i+1]
    #print(old)
    
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
if sum(depth)<N+1:
    print(-1)
else:
    print(sum(depth))

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
    # if depth[i]<=0:
    #     print(-1)
    #     exit()
print(sum(depth))

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
for i in range(1,N+1):
    depth[i]=(depth[i-1]-H[i-1])*2
    if depth[i]<=0:
        print(-1)
        exit()
depth[N]=H[N]
for i in range(N-1,-1,-1):
    depth[i]=min(depth[i+1]+H[i],depth[i])
    if depth[i]<=0:
        print(-1)
        exit()
print(sum(depth))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from sys import setrecursionlimit
from itertools import accumulate
setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
b = list(accumulate(a[::-1]))
b = b[::-1]
#print(b)

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

ne = [0]*(n+1)

ne[0] = 1
point = 1

for i in range(1,n):
    point_ma = min(ne[i-1]*2,b[i+1]+a[i])
    if a[i] > point_ma:
        print(-1)
        exit()
    ne[i] = point_ma-a[i]
    point += point_ma

if ne[n-1]*2 < a[n]:
    print(-1)
    exit()

point += a[n]
ne[n] = 0

print(point)

Submission status: Wrong Answer

Solution code:
N = int(input())
nums = list(map(int, input().split()))
totalNode = 1
totalLeaf = 1
fail = False
for i in range(N + 1):
	totalLeaf = (totalLeaf-nums[i])*2
	if (totalLeaf < 0):
		fail = True
		break
	totalNode += totalLeaf
  
if (fail):
	print(-1)
else:
	print(totalNode)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split());t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0 and abs(v:=v+w)+1:exit(print(-1))
print(v)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split());t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0 and(v:=v+w)>0:exit(print(-1))
print(v)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split());t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0 and(v:=v+w):exit(print(-1))
print(v)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split());t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0 or(v:=v+w):exit(print(-1))
print(v)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from sys import setrecursionlimit
from itertools import accumulate
setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))

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

ne = [0]*(n+1)
point = [0]*(n+1)

ne[0] = 1
point[0] = 1

for i in range(1,n):
    point_ma = min(ne[i-1]*2,sum(a[i+1:])+a[i])
    if a[i] > point_ma:
        print(-1)
        exit()
    ne[i] = point_ma-a[i]
    point[i] = point_ma

if ne[n-1]*2 < a[n]:
    print(-1)
    exit()

point[n] = a[n]
ne[n] = 0

#print(point)
#print(ne)
print(sum(point))

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res


N=II()
AS=LI()
SM=sum(AS)
B=1
res=1

if AS[0] == 1:
    if N > 0 or SM != 1:
        print(-1)
    else:
        print(1)
    exit(0)

for a in AS[1:]:
    M = min(B*2, SM)
    m = B
    B = M-a
    if B < 0:
        print(-1)
        exit(0)
    res += a
    res += B
    SM -= a
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
  
def solve(N, A):
  
  
  total = sum(A[1:])
  #t = A[-1] + A[-2]
  par = 1 - A[0]
  rt = 1
  for i, a in enumerate(A[1:]):
    total -= a
    t = total
    max_node = par * 2
    cur = max_node - a
    if cur < 0:
      print(-1)
      return
    cur = min(t, cur)
    #print(i+1, a, cur)
    rt += a
    if i + 1 < N:
      rt += cur
    #print('rt', rt)
    par = cur  
   
  print(rt)
  
solve(N, A)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 13:51:17 2020

@author: yuyah
"""
import math

# 2分木
# The number is the depth of the tree
n = int(input())

# the number is the count of leaves
a = input()
a = [int(s) for s in a.split(' ')]

# 可能な範囲を下から見ていく（一番深い葉から見てく)
d = list(range(n + 1))
for i in reversed(range(n + 1)):
    tmp = []
    
    if i == n:
        #min
        tmp.append(a[i])
        #max
        tmp.append(a[i])
    
    else:
        # 葉の数の足し忘れに注意
        #min
        tmp.append(math.ceil(d[i+1][0] / 2) + a[i])
        #max
        tmp.append(d[i+1][1] + a[i])
    
    d[i] = tmp

# その後下に下がっていく
tmp = 0
ans = []
for i in range(n + 1):
    if i == 0:
        if a[i] > 0:
            ans = [-1]
            break
        
        ans.append(1)
    
    else:
        # 葉の分の引き忘れに注意
        tmp = int(ans[i-1] * 2) - a[i-1] - a[i]
        if tmp < 0:
            ans = [-1]
            break
            
        if tmp >= d[i][0] and tmp <= d[i][1]:
            ans.append(tmp)
        elif tmp >= d[i][1]:
            ans.append(d[i][1])
        elif tmp <= d[i][0]:
            ans.append(d[i][0])

print(sum(ans))

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res


N=II()
AS=LI()
SM=sum(AS)
B=1
res=1

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

for a in AS[1:]:
    M = min(B*2, SM)
    m = B
    B = M-a
    if B < 0:
        print(-1)
        exit(0)
    res += a
    res += B
    SM -= a
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
leaf = inpl()
mx = [1]
pre = [1]
x = 1
if leaf[0] != 0:
    print(-1)
    quit()
for i in range(1,n+1):
    if x <= 10**10: x *= 2
    tmp = pre[-1]*2 - leaf[i]
    if (i != n and tmp <= 0) or (i==0 and tmp < 0) or leaf[i] > x:
        print(-1)
        quit()
    pre.append(tmp)
# print(pre)
res = [0] * (n+1)
res[0] = 1
res[-1] = leaf[-1]
for i in range(1,n)[::-1]:
    tmp = res[i+1] + leaf[i]
    if pre[i-1]*2 < tmp:
        tmp = pre[i-1]*2
    res[i] = tmp
print(sum(res))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]


def f():
    ans = 1
    prev = 1
    L = [0]*(N+1)
    L[0] = 1
    M = max(A)
    for i in range(1, N+1):
        if prev*2 > A[i]:
            prev = prev*2-A[i]
        elif prev*2 == A[i] and i == N:
            continue
        else:
            ans = -1
            break
        L[i] = prev
        if prev > M:
            for j in range(i+1, N+1):
                L[j] = M+1
            break

    if A[0] > 0:
        ans = -1
        if A[0] == 1 and N == 0:
            ans = 1

    if ans == 1:
        num = 0
        for i in range(N, 0, -1):
            if L[i] == "inf" or num+A[i] <= 2*L[i-1]:
                num += A[i]
            else:
                num = 2*L[i-1]
            ans += num
    return ans

print(f())

Submission status: Wrong Answer

Solution code:
import sys

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

#n=3
#a="0 1 1 2"

#n=4
#a="0 0 1 0 2"

#n=10
#a="0 0 1 1 2 3 5 8 13 21 34"
#a=list(map(int,a.split()))

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

b=[0]*(n+1)
b[0]=1
yn=""
for i in range(n):
    b[i+1]=b[i]*2-a[i+1]
    if b[i+1]<0:
        yn="no"
        break
    elif b[i+1]==0 and i!=n-1:
        yn="no"
        break
if yn=="no":
    print(-1)
else:    
    b[n]=a[n]
    for i in range(n,0,-1):
#        print("i-1:",i-1,"b[i]:",b[i],"a[i-i]:",a[i-1],"b[i-1]:",b[i-1],"*b[i-1]:",min(b[i]+a[i-1],b[i-1]))
        b[i-1]=min(b[i]+a[i-1],b[i-1]+a[i-1])
#        print("i-1",i-1,"c[i-1]",c[i-1],"a[n]",a[n],"c[i]",c[i],"b[i-1]",b[i-1])
#        print("i-1",i-1,"c[i-1]",c[i-1],"a[i-i]",a[i-1],"b[i]",b[i],"b[i-1]",b[i-1])
    print(sum(b))

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

n = int(rl())

li = list(map(int, rl().split()))
if li[0] == 1:
    print(1)
    exit()

can = [1-li[0]]

a = can[0]
for i in range(1, n+1):
    a = a*2
    can.append(a)
    a -= li[i]
    if a < 0:
        print(-1)
        exit()

ans = 0
can.reverse()
li.reverse()
temp = 0
for i in range(n+1):
    temp += li[i]
    ans += min(can[i], temp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

#n=3
#a="0 1 1 2"

#n=4
#a="0 0 1 0 2"

#n=10
#a="0 0 1 1 2 3 5 8 13 21 34"
#a=list(map(int,a.split()))

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

b=[0]*(n+1)
b[0]=1
yn=""
for i in range(n):
    b[i+1]=b[i]*2-a[i+1]
    if b[i+1]<=0:
        yn="no"
        break
if yn=="no":
    print(-1)
else:    
    b[n]=a[n]
    for i in range(n,0,-1):
#        print("i-1:",i-1,"b[i]:",b[i],"a[i-i]:",a[i-1],"b[i-1]:",b[i-1],"*b[i-1]:",min(b[i]+a[i-1],b[i-1]))
        b[i-1]=min(b[i]+a[i-1],b[i-1]+a[i-1])
#        print("i-1",i-1,"c[i-1]",c[i-1],"a[n]",a[n],"c[i]",c[i],"b[i-1]",b[i-1])
#        print("i-1",i-1,"c[i-1]",c[i-1],"a[i-i]",a[i-1],"b[i]",b[i],"b[i-1]",b[i-1])
    print(sum(b))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
leaf = inpl()
mx = [1]
pre = [1]
x = 1
if leaf[0] != 0:
    print(-1)
    quit()
for i in range(1,n+1):
    tmp = pre[-1]*2 - leaf[i]
    if (i != n and tmp <= 0) or (i==0 and tmp < 0):
        print(-1)
        quit()
    pre.append(tmp)
# print(pre)
res = [0] * (n+1)
res[0] = 1
res[-1] = leaf[-1]
for i in range(1,n)[::-1]:
    tmp = res[i+1] + leaf[i]
    if pre[i-1]*2 < tmp:
        tmp = pre[i-1]*2
    res[i] = tmp
print(sum(res))

Submission status: Wrong Answer

Solution code:
import sys

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

#n=3
#a="0 1 1 2"

#n=4
#a="0 0 1 0 2"

#n=10
#a="0 0 1 1 2 3 5 8 13 21 34"
#a=list(map(int,a.split()))

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

b=[0]*(n+1)
b[0]=1
yn=""
for i in range(n):
    b[i+1]=b[i]*2-a[i+1]
    if b[i+1]<0:
        yn="no"
        break
if yn=="no":
    print(-1)
else:    
    b[n]=a[n]
    for i in range(n,0,-1):
#        print("i-1:",i-1,"b[i]:",b[i],"a[i-i]:",a[i-1],"b[i-1]:",b[i-1],"*b[i-1]:",min(b[i]+a[i-1],b[i-1]))
        b[i-1]=min(b[i]+a[i-1],b[i-1]+a[i-1])
#        print("i-1",i-1,"c[i-1]",c[i-1],"a[n]",a[n],"c[i]",c[i],"b[i-1]",b[i-1])
#        print("i-1",i-1,"c[i-1]",c[i-1],"a[i-i]",a[i-1],"b[i]",b[i],"b[i-1]",b[i-1])
    print(sum(b))

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

n = int(rl())

li = list(map(int, rl().split()))

can = [1-li[0]]

a = can[0]
for i in range(1, n+1):
    a = a*2
    can.append(a)
    a -= li[i]
    if a < 0:
        print(-1)
        exit()

ans = 0
can.reverse()
li.reverse()
temp = 0
for i in range(n+1):
    temp += li[i]
    ans += min(can[i], temp)
print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split());t,v=sum(a),[1]
print(-1 if [v:=v+[min(2*(v[-1]-q),t:=t-q)] for q in a if v[-1]<0] else sum(v))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
capa = 1
for i in range(len(A)):
    if A[i] > capa:
        print(-1)
        exit()
    capa = (capa - A[i]) * 2
tree = [1]
A_max = max(A)
for i in range(1, N):
    if tree[i-1] - A[i] < max(A[i], A_max):
        
        tree.append(min(tree[i-1]*2, A[-1]+A[i]) - A[i])
    else:
        tree.append(tree[i-1] - A[i])

print(sum(tree) + sum(A))

Submission status: Wrong Answer

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

for i in range(1, N):
    if tree[i-1] - A[i] < max(A[i:]):
        
        tree.append(min(tree[i-1]*2, A[-1]+A[i]) - A[i])
    else:
        tree.append(tree[i-1] - A[i])

print(sum(tree) + sum(A))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n=int(input())
a = list(map(int, input().split()))
if (a[0]==1 and n+1>1) or a[0]>1:
    print(-1)
    sys.exit()


su=[0]*(n+1)
for i in range(1,n+1)[::-1]:
    su[i-1]+=su[i]+a[i]
#print(su)
yo_next=min(2-a[0],su[0])
cnt=yo_next+1

for i in range(1,n):
    if yo_next-a[i]<1:
        print(-1)
        sys.exit()
    
    yo_next=min(su[i],(yo_next-a[i])*2)
    cnt+=yo_next
    #print(cnt,su[i+1],(yo_next-a[i])*2)
if yo_next<a[-1]:
    print(-1)
    sys.exit()
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n=int(input())
a = list(map(int, input().split()))
if (a[0]==1 and n+1>1) or a[0]>1:
    print(-1)
    sys.exit()
if a[0]==0 and n==0:
    print(-1)
    sys.exit()    
if n==1 and a[1]==1:
    print(-1)
    sys.exit() 

su=[0]*(n+1)
for i in range(1,n+1)[::-1]:
    su[i-1]+=su[i]+a[i]
#print(su)
yo_next=min(2-a[0],su[0])
cnt=yo_next+1

for i in range(1,n):
    if yo_next-a[i]<1:
        print(-1)
        sys.exit()
    
    yo_next=min(su[i],(yo_next-a[i])*2)
    cnt+=yo_next
    #print(cnt,su[i+1],(yo_next-a[i])*2)
print(cnt)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
t,v=sum(a),[1]
if ~len([print(-1) for q in a if(v:=v+[min(2*(v[-1]-q),t:=t-q)])[-1]<0]):print(sum(v))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n=int(input())
a = list(map(int, input().split()))
if (a[0]==1 and n+1>1) or a[0]>1:
    print(-1)
    sys.exit()

su=[0]*(n+1)
for i in range(1,n+1)[::-1]:
    su[i-1]+=su[i]+a[i]
#print(su)
yo_next=min(2-a[0],su[0])
cnt=yo_next+1

for i in range(1,n):
    if yo_next-a[i]<1:
        print(-1)
        sys.exit()
    
    yo_next=min(su[i],(yo_next-a[i])*2)
    cnt+=yo_next
    #print(cnt,su[i+1],(yo_next-a[i])*2)
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n=int(input())
a = list(map(int, input().split()))
if (a[0]==1 and n+1>1) or a[0]>1:
    print(-1)
    sys.exit()
if a[-1]==0:
    print(-1)
    sys.exit()

su=[0]*(n+1)
for i in range(1,n+1)[::-1]:
    su[i-1]+=su[i]+a[i]
#print(su)
yo_next=2-a[0]
cnt=yo_next+1

for i in range(1,n):
    if yo_next-a[i]<1:
        print(-1)
        sys.exit()
    
    yo_next=min(su[i],(yo_next-a[i])*2)
    cnt+=yo_next
    #print(cnt,su[i+1],(yo_next-a[i])*2)
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n=int(input())
a = list(map(int, input().split()))
if (a[0]==1 and n+1>1) or a[0]>1:
    print(-1)
    sys.exit()

su=[0]*(n+1)
for i in range(1,n+1)[::-1]:
    su[i-1]+=su[i]+a[i]
#print(su)
yo_next=2-a[0]
cnt=yo_next+1

for i in range(1,n):
    if yo_next-a[i]<1:
        print(-1)
        sys.exit()
    
    yo_next=min(su[i],(yo_next-a[i])*2)
    cnt+=yo_next
    #print(cnt,su[i+1],(yo_next-a[i])*2)
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n=int(input())
a = list(map(int, input().split()))
if a[0]==1 and n+1>1:
    print(-1)
    sys.exit()

su=[0]*(n+1)
for i in range(1,n+1)[::-1]:
    su[i-1]+=su[i]+a[i]
#print(su)
yo_next=2-a[0]
cnt=yo_next+1

for i in range(1,n):
    if yo_next-a[i]<1:
        print(-1)
        sys.exit()
    
    yo_next=min(su[i],(yo_next-a[i])*2)
    cnt+=yo_next
    #print(cnt,su[i+1],(yo_next-a[i])*2)
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import collections

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


ans = 0
node_num = 1
pre_node_num = 1
B = [1 - A[0]]
ruisekiA = [0 for i in range(N + 2)]
ruisekiA[N] = A[N]
ruisekiA[N + 1] = 0
for i in range(N - 1, -1, -1):
    ruisekiA[i] = ruisekiA[i + 1] + A[i]


for i in range(1, N + 1):
    tmpB = min(2 * B[i - 1] - A[i], ruisekiA[i + 1])
    #print(tmpB, B[i - 1] - A[i])
    if (tmpB < 0) or (tmpB < B[i - 1] - A[i]):
        ans = -1
        break
    if i == N:
        tmpB = 0
    B.append(tmpB)

if N == 0 and A[0] == 0:
    ans = -1

if ans != -1:
    ans = sum(A) + sum(B)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import collections

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


ans = 0
node_num = 1
pre_node_num = 1
B = [1 - A[0]]
ruisekiA = [0 for i in range(N + 2)]
ruisekiA[N] = A[N]
ruisekiA[N + 1] = 0
for i in range(N - 1, -1, -1):
    ruisekiA[i] = ruisekiA[i + 1] + A[i]


for i in range(1, N + 1):
    tmpB = min(2 * B[i - 1] - A[i], ruisekiA[i + 1])
    if tmpB < max(B[i - 1] - A[i], 0):
        ans = -1
        break
    if i == N:
        tmpB = 0
    B.append(tmpB)


if ans != -1:
    ans = sum(A) + sum(B)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n=int(input())
a=list(map(int,input().split()))
c=list(accumulate(a))
b=[0]*(n+1)
#大きくしすぎてしまう場合がある
#いや上限を考えろや
def f():
    global n,a,b
    for i in range(n+1):
        if i==0:
            b[0]=min(c[n]-c[0],1)
        else:
            b[i]=min(2*(b[i-1]-a[i-1]),c[n]-c[i-1])

    if b[n]!=a[n]:
        print(-1)
    else:
        print(sum(b))
        #print(b)
f()

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import collections

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


ans = 0
node_num = 1
pre_node_num = 1
B = [1 - A[0]]

for i in range(1, N + 1):
    tmpB = min(2 * B[i - 1] - A[i], sum(A[i + 1:]))
    #print(tmpB, B[i - 1] - A[i])
    if tmpB < max(B[i - 1] - A[i], 0):
        ans = -1
        break
    if i == N:
        tmpB = 0
    B.append(tmpB)


if ans != -1:
    ans = sum(A) + sum(B)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()
dbg = lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)

N = ni()
A = nl()
assert len(A) == (N + 1)


def solve():
    ar = list(itertools.accumulate(A[::-1]))
    ar.reverse()
    ar.append(0)
    assert len(ar) == (N + 2)
    if N == 0:
        return 1 if A[0] == 1 else -1
    if A[0] != 0:
        return -1
    inn = ans = 1
    for i in range(1, N):
        b = 2 * inn - A[i]
        if b <= 0:
            return -1
        inn = min(b, ar[i + 1])
        ans += inn + A[i]
    ans += A[N]
    return ans


print(solve())

Submission status: Wrong Answer

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

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

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

    if (m[i] <= 0 and i != n) or (m[i] < 0 and i == n):
        print(-1)
        exit()

a.reverse()
m.reverse()
m[0] = a[0]
for i in range(1, n+1):
    m[i] = min(m[i], m[i-1]) + a[i]

print(sum(m))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import collections

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


ans = 0
node_num = 1
pre_node_num = 1
B = [1 - A[0]]
for i in range(1, N):
    tmpB = min(2 * B[i - 1] - A[i], sum(A[i + 1:]))
    # print(tmpB)
    if tmpB < B[i - 1] - A[i]:
        ans = -1
        break
    B.append(tmpB)


if ans != -1:
    ans = sum(A) + sum(B)
print(ans)