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 sys
input = sys.stdin.readline


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A):
    max_leaves = sum(A)
    if A[0] > 0:
        return -1
    ans = 1
    n_nodes = 1
    for i in range(1, N+1):
        n_nodes = min(n_nodes * 2, max_leaves)
        ans += n_nodes
        if i < N and A[i] > n_nodes - 1:
            return -1
        max_leaves -= A[i]
        n_nodes -= A[i]
    if n_nodes != 0:
        return -1
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()

    if n>0 and aa[0]>0:
        print(-1)
        exit()

    node=[0]*(n+1)
    node[0]=1
    node[n]=aa[n]

    for i in range(n-1,0,-1):
        a=aa[i]
        if a>(1<<i):
            print(-1)
            exit()

        node[i]=min(1<<i,node[i+1]+aa[i],((1<<(i-1))-aa[i-1])*2)

    for i in range(1,n):
        node[i]=min((node[i-1]-aa[i-1])*2,node[i])

    #print(node)
    print(sum(node))

main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    A = list(map(int,input().split()))
    can_root = [0] * (N + 1)
    can_root[0] = 1
    if N > 0 and A[0] == 1:
        print(-1)
        return 
    if N == 0 and A[0] == 1:
        print(1)
        return 
    for i in range(1,N + 1):
        can_root[i] = 2*can_root[i - 1] - A[i]
        if can_root[i] < 0:
            print(-1)
            return 
    
    ans = A[-1]
    now = A[-1]
    for i in range(N - 1,-1,-1):
        if now + A[i] <= can_root[i]:
            now += A[i]
        else:
            now = can_root[i] + A[i]
        ans += now
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
flag = True
if A[0] != 0:
    flag = False

ans = 0
cur = 1

nodes = [0] * (N + 1)
nodes[0] = 1
for i in range(1, N + 1):
    cur *= 2
    nodes[i] = cur
    cur -= A[i]
    if cur < 0:
        flag = False

L = 0
for i in range(N, -1, -1):
    L += A[i]
    L = min(L, nodes[i])
    ans += L

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

Submission status: Wrong Answer

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

if not (N == 1 and A == [1, 1]):
    exit()

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

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

ans = 1
prev = 1
P = []
for a in A[1:]:
    P.append(prev)
    mx = prev * 2

    if mx < a:
        print(-1)
        exit()

    ans += mx
    prev = mx - a

while prev and P:
    ans -= prev
    pr = P.pop()
    prev = max(0, prev - pr)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=tuple(map(int,input().split()))
ans=1
tmp=0
M=[1]

for i,x in enumerate(A[1:],1):
    if i>=30:
        n=2*10**8
    else:
        n=2**i
    M.append(min(10**8,n-x,M[i-1]*2-x))
for i,(x,y) in enumerate(zip(A[1:][::-1],M[1:][::-1])):
    fukasa=N-i
    if fukasa>=30:
        n=10**8
    else:
        n=2**fukasa
    n=min(10**8,n)
    tmp+=x
    tmp=min(tmp,n,y+x)
    ans+=tmp
print(ans)

Submission status: Wrong Answer

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

if N == 1 and A == [1, 1]:
    exit()

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

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

ans = 1
prev = 1
P = []
for a in A[1:]:
    P.append(prev)
    mx = prev * 2

    if mx < a:
        print(-1)
        exit()

    ans += mx
    prev = mx - a

while prev and P:
    ans -= prev
    pr = P.pop()
    prev = max(0, prev - pr)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
A = na()

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

dp = [1]*(n+1)
pd = [1]*(n+1)

m = 1
for i in range(1,n+1):
    m = m*2
    dp[i] = m
    m -= A[i]
    if m < 0:
        print(-1)
        exit()

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

ans = []
for i in range(n+1):
    ans.append(min(dp[i],pd[i]))
    
print(sum(ans))

Submission status: Wrong Answer

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

leaf = []
miki = []
under = 1

for i, a in enumerate(A):
    can = 2 ** i
    if a > can or under == 0:
        print(-1)
        exit()
    miki.append(under - a)
    under = miki[-1] * 2


ans = 0
child = 0
for i in reversed(range(N + 1)):
    child = min(child, miki[i]) + A[i]
    ans += child

print(ans)

Submission status: Wrong Answer

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


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

ans = ans[::-1]

ans = ans[1::]
a = a[1::]

res = 1

prev_cnt = 1
for i in range(n):
    cnt = min(prev_cnt * 2, ans[i] + a[i])
    if cnt < a[i]:
        print(-1)
        exit()
    res += cnt
    prev_cnt = cnt - a[i]
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    # QUERYS = [input().split() for _ in range(Q)]
    # H1, M1, H2, M2, K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]

    if N == 0:
        print(1)
        return

    s = []
    t = 0
    for a in reversed(A):
        s.append(t)
        t += a
    s = list(reversed(s))

    res = 1
    nodes = 1

    for i in range(1, N + 1):
        max_nodes = nodes * 2
        nokori = s[i]
        leafs = A[i]
        if leafs > max_nodes:
            print(-1)
            return
        not_leafs = min(max_nodes - leafs, nokori)
        res += not_leafs + leafs
        nodes = not_leafs
    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=tuple(map(int,input().split()))
ans=1
tmp=0
M=[1]

for i,x in enumerate(A[1:],1):
    if i>=30:
        n=2*10**8
    else:
        n=2**i
    M.append(min(10**8,n-x,M[i-1]*2-x))
    if M[i]<0:
        print(-1)
        exit()
for i,(x,y) in enumerate(zip(A[1:][::-1],M[1:][::-1])):
    fukasa=N-i
    if fukasa>=30:
        n=10**8
    else:
        n=2**fukasa
    n=min(10**8,n)
    tmp+=x
    if y+x>n:
        print(-1)
        exit()
    tmp=min(tmp,n,y+x)
    ans+=tmp
if A[0]+M[0]>1:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

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


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

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())

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

ans = 0
v = 1

maxv = []

for i in range(N+1):

    if v <= 0:
        print (-1)
        sys.exit()
    
    maxv.append(v)

    v -= A[i]
    v *= 2

#print (maxv)

now = 0
for i in range(N,-1,-1):

    now = min(now + A[i] , maxv[i])
    #print (now)
    ans += now

print (ans)

Submission status: Wrong Answer

Solution code:
def solve(n, aaa):
    if n == 0:
        if aaa[0] == 0:
            return 1
        else:
            return -1
    if aaa[0] != 0:
        return -1

    hi = 1
    hi_enable = [1]
    for a in aaa[1:]:
        if hi * 2 < a:
            return -1
        hi = hi * 2 - a
        hi_enable.append(hi)
    # print(hi_enable)
    vn = aaa[n]
    ans = vn
    for i in range(n - 1, -1, -1):
        hi = hi_enable[i]
        a = aaa[i]
        vn = min(vn, hi) + a
        ans += vn
        # print(vn, ans)
    return ans


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

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


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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=list(map(int,input().split()))
    ans=1
    flag=True
    if A[0]==1:
        c=0
    else:
        c=1
    for i in range(n):
        a=A[i+1]
        c*=2
        ans+=c
        if c<a:
            flag=False
            break
        else:
            c-=a
    if flag:
        while c:
            ans-=c
            c//=2
        print(ans)
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def div_cnt(n):
    res = 0
    while(n):
        n/=2
        res += 1
    return res
def ok(D):
    for i,d in enumerate(D):
        if(div_cnt(d) > i+1):
            return False
    return True
def main():
    N=I()
    D=LI()
    D_rev = D[::-1]
    up = 10**10
    B = [1]*(N+1) #その深さに存在出来る点の数
    for i in range(N):
        B[i + 1] = min(up, (B[i]-D[i]) * 2) 
    # print(B)
    B_rev = B[::-1]

    ans = 0
    now = 0
    for i,a in enumerate(D_rev):
        if(a>B_rev[i]):
            print(-1)
            return 
        now += a
        now = min(now, B_rev[i])
        ans += now
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

B = [0] * N
for i in reversed(range(N)):
    if i == N - 1:
        B[i] = A[i]
    else:
        B[i] = B[i + 1] + A[i]

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

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

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
if N == 1 and A[0] == 1:
    print(1)
    exit()
if A[0] != 0:
    print(-1)
    exit()
cum = [0] * (N+2)
for i in range(N+1)[::-1]:
    cum[i] = cum[i+1] + A[i]
ans = 1
cur = 1
for i in range(1, N+1):
    cur = min(cur * 2, cum[i+1] + A[i])
    ans += cur
    cur -= A[i]
    if cur < 0:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = []
i = 0
for j in reversed(a):
    i += j
    b.append(i)
b.reverse()
ans = 1
if a[0] != 0:
    print(-1)
    exit()
i = 1
for j, k in zip(a[1:], b[1:]):
    if j > i*2:
        print(-1)
        exit()
    i = min(k, i * 2) - j
    ans += i + j
    if i < 0:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

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

B = [0] * N
for i in reversed(range(N)):
    if i == N - 1:
        B[i] = A[i]
    else:
        B[i] = B[i + 1] + A[i]

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0]
for i in range(n+1):
  b.append(b[-1]+a[-1-i])
b.reverse()
b.pop()
#print(b)
now = 1
ans = 0
for i in range(n):
  if now > b[i]:
    now = b[i]
  ans += now
  now -= a[i]
  if now <= 0:
    print(-1)
    exit()
  now *= 2
  #print(i,now,ans)
ans += a[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

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

    left_leaves = sum(aa)
    ans = 0
    now = 1
    for i in range(n):
        ans += now
        num_of_node = now - aa[i]
        if num_of_node <= 0:
            print(-1)
            exit()
        max_next_node = num_of_node*2
        left_leaves -= aa[i]
        if max_next_node > left_leaves:
            now = left_leaves
        else:
            now = max_next_node
    ans += now
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = LI()

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

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

ans = 0
for i in range(N+1):
    if d[i] < 0 or u[i] < 0:
        print('-1')
        exit() 
    ans += min(d[i],u[i])

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=list(map(int,input().split()))
    ans=1
    flag=True
    if A[0]==1:
        c=0
    else:
        c=1
    for i in range(n):
        a=A[i+1]
        c*=2
        ans+=c
        if c<a:
            flag="False"
            break
        else:
            c-=a
    if flag:
        while c:
            ans-=c
            c//=2
        print(ans)
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A = map(int, read().split())

INF = 1 << 60

bound = [0] * (N + 1)
bound[0] = 1
ok = True
for n in range(1, N + 1):
    bound[n] = min(INF, (bound[n - 1] - A[n - 1]) * 2)
    if bound[n] < A[n]:
        ok = False

if not ok:
    print(-1)
    exit()

B = [0] * (N + 2)
for n in range(N, -1, -1):
    x = min(bound[n], B[n + 1] + A[n])
    B[n] = x

print(sum(B))

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A = map(int, read().split())

INF = 1 << 30

bound = [0] * (N + 1)
bound[0] = 1
ok = True
for n in range(1, N + 1):
    bound[n] = min(INF, (bound[n - 1] - A[n - 1]) * 2)
    if bound[n] < A[n]:
        ok = False

if not ok:
    print(-1)
    exit()

B = [0] * (N + 2)
for n in range(N, -1, -1):
    x = min(bound[n], B[n + 1] + A[n])
    B[n] = x

print(sum(B))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
number = int(input())
lists = list(map(int, input().split()))
prev = 0
leafs = 0
for i in lists:
  if i > (2 * prev):
    print('-1')
    sys.exit()
  else:
    leafs = leafs + (2 * prev - i)
    prev = i
print(str(leafs))

Submission status: Wrong Answer

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

if a[0] == 1:
    if n == 0:
        print(1)
    else:
        print(-1)
else:
    lefts = [sum(a)]
    for i in range(1, len(a)):
        lefts.append(lefts[-1] - a[i])

    b = [0] * (n + 1)
    b[0] = 1

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

    if min(b) < 0:
        print(-1)
    else:
        print(sum(b) + sum(a))

Submission status: Wrong Answer

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)


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

def dfs(n,x,t):
    if n+1==N:
        if x-A[n]<=A[N]<=2*(x-A[n]):
            print(t+A[N])
            exit()
    else:
        for i in range(2*(x-A[n]),x-A[n]-1,-1):
            dfs(n+1,i,t+i)
if N==0 and A[0]==1:
    print(1)
    exit()

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

dfs(0,1,1)
print(-1)

Submission status: Time Limit Exceeded

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

  # 貪欲: まず一直線に下まで一本作り、次に「空き」がある一番上の頂点から、
  # 一番上のまだ処理していない葉に順に枝を伸ばしていく。

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

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

  if N==1:
    print(A[1]+1)
    exit()

  if sumA==1:
    print(N+1)
    exit()

  n_leaf = 1
  n_free = [1]*(N+1)
  idx1=0 #Aを順になめていくポインタ
  idx2=0 #新たに枝を出すスロットがある一番上の深さ
  ans = N+1
  while n_leaf != sumA:
    for i in range(idx1,N+1):
      if A[i] != 0:
        idx1 = i
        while not n_free[idx2]:
          idx2 += 1
        n_free[idx2] -= 1
        if idx2>=i:
          print(-1)
          exit()
        if sumA-n_leaf>1: 
          for j in range(idx2,i+1):
            if idx2<j and j<i:
              n_free[j] += 1
        A[i] -= 1
        n_leaf += 1
        ans += i - idx2
        break

  print(ans)
  
main()

Submission status: Time Limit Exceeded

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

# 貪欲: まず一直線に下まで一本作り、次に「空き」がある一番上の頂点から、
# 一番上のまだ処理していない葉に順に枝を伸ばしていく。

if N==0:
  if A[0] == 1:
    print(1)
  else:
    print(-1)
  exit()
    
if N>=1 and A[0]!=0:
  print(-1)
  exit()
  
if N==1:
  print(A[1]+1)
  exit()
  
if sumA==1:
  print(N+1)
  exit()
  
n_leaf = 1
n_free = [1]*(N+1)
idx1=0 #Aを順になめていくポインタ
idx2=0 #新たに枝を出すスロットがある一番上の深さ
ans = N+1
while n_leaf != sumA:
  for i in range(idx1,N+1):
    if A[i] != 0:
      idx1 = i
      while not n_free[idx2]:
        idx2 += 1
      n_free[idx2] -= 1
      if idx2>=i:
        print(-1)
        exit()
      for j in range(idx2,i+1):
        if idx2<j and j<i:
          n_free[j] += 1
      A[i] -= 1
      n_leaf += 1
      ans += i - idx2
      break
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

cons = [0] * (N + 1)
cur = 0
mn, mx = 0, 0
for j in range(N + 1):
    i = N - j
    mn = ((mn + 1) // 2) + A[i]
    mx = mx + A[i]
    if mn > 2 ** i:
        print(-1)
        exit()
    cons[i] = (mn, mx)

ans = 0
cnt_node = 1
for i in range(N + 1):
    mn, mx = cons[i]
    now = min(mx, cnt_node)
    ans += now
    cnt_node = (now - A[i]) * 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

cons = [0] * (N + 1)
cur = 0
mn, mx = 0, 0
for i in range(N, -1, -1):
    mn = ((mn + 1) // 2) + A[i]
    mx = mx + A[i]
    if mn > 2 ** i:
        print(-1)
        exit()
    cons[i] = (mn, mx)

ans = 0
cnt_node = 1
for i in range(N + 1):
    mn, mx = cons[i]
    now = min(mx, cnt_node)
    ans += now
    cnt_node = (now - A[i]) * 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

cons = []
cur = 0
mn, mx = 0, 0
for i in range(N, -1, -1):
    mn = ((mn + 1) // 2) + A[i]
    mx = mx + A[i]
    if mn > 2 ** i:
        print(-1)
        exit()
    cons.append((mn, mx))
cons = list(reversed(cons))
ans = 0
cnt_node = 1
for i in range(N + 1):
    mn, mx = cons[i]
    now = min(mx, cnt_node)
    ans += now
    cnt_node = (now - A[i]) * 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 1:
            print(1)
            exit()
        else:
            end()
    elif a[0]!=0:
        end()

    b = [0]*(n+1)
    for i in range(n,-1,-1):
        if i == n:
            b[i] = a[i]
        else:
            b[i] = min(b[i+1]+a[i],2**i)

    for i in range(n+1):
        if i!=0:
            b[i] = min(2*(b[i-1]-a[i-1]),b[i])
        if b[i]<a[i]:
            end()
    print(sum(b))
    return
 
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
A[N]-=1
ans=N+1
H=[1]*(N)+[0]
z=0
if A[0]!=0:
  print(-1)
  sys.exit()
def get(t):
  global N
  global H
  global ans
  global z
  for k in range(z,t+1):
    if H[k]>=1:
      z=k
      H[k]-=1
      # for l in range(k+1,t):
      #   H[l]+=1
      H[k+1:t]=list(map(lambda c:c+1,H[k+1:t]))
      ans+=(t-k)
      break
  if k==t:
    if H[N]==0:
      print(-1)
      sys.exit()


for i in range(N+1):
  for j in range(A[i]):
    get(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
A[N]-=1
ans=N+1
H=[1]*(N)+[0]
z=0
def a(n):
  return n+1
if A[0]!=0:
  print(-1)
  sys.exit()
def get(t):
  global N
  global H
  global ans
  global z
  for k in range(z,t+1):
    if H[k]>=1:
      z=k
      H[k]-=1
      # for l in range(k+1,t):
      #   H[l]+=1
      H[k+1:t]=list(map(a,H[k+1:t]))
      ans+=(t-k)
      break
  if k==t:
    if H[N]==0:
      print(-1)
      sys.exit()


for i in range(N+1):
  for j in range(A[i]):
    get(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
A[N]-=1
ans=N+1
H=[1]*(N)+[0]
z=0
if A[0]!=0:
  print(-1)
  sys.exit()
def get(t):
  global N
  global H
  global ans
  global z
  for k in range(z,t+1):
    if H[k]>=1:
      z=k
      H[k]-=1
      for l in range(k+1,t):
        H[l]+=1
      ans+=(t-k)
      break
  if k==t:
    if H[N]==0:
      print(-1)
      sys.exit()


for i in range(N+1):
  for j in range(A[i]):
    get(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

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

# = [list(map(int,input().split())) for _ in range(XXXX)]

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


    que = deque()
    que.appendleft([0,1,0])

    while que:
        x = que.popleft()
        d = x[0]
        point = x[1]
        counter = x[2]
        counter += point
        ad = a[d]

        if d == n:
            if point == ad:
                print(counter)
                exit()
            else:
                continue

        #if point-ad <= 0:
        #    #すべて葉 or 葉の数がadに足りない。
        #    continue

        for nextp in range(point-ad,(point-ad)*2+1):
            if nextp-a[d+1] >= 0:
                que.appendleft([d+1,nextp,counter])

    print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from math import ceil

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

bottom_n_list = [(0, 0) for _ in range(n + 1)]
bottom_n_list[n] = (a[n], a[n])
for i in range(n-1, -1, -1):
    leaf_num = a[i]
    min_a_node_num = ceil(bottom_n_list[i + 1][0] / 2)
    max_a_node_num = min(bottom_n_list[i + 1][1], 2 ** i - leaf_num)
    if max_a_node_num < min_a_node_num:
        print(-1)
        exit()
    bottom_n_list[i] = (min_a_node_num + leaf_num, max_a_node_num + leaf_num)

top_n_list = [0]*(n+1)
if 1 < bottom_n_list[0][0] or bottom_n_list[0][1] < 1:
    print(-1)
    exit()
top_n_list[0] = 1
for i in range(1, n+1):
    top_n_list[i] = min(bottom_n_list[i][1], (top_n_list[i-1]-a[i-1])*2)


ans = reduce(lambda a, b: a+b, top_n_list)
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if n == 0:
    if As[0] == 1: print(1)
    else: print(-1)
    exit()
    
# 下から見る
As_r = As[::-1]
p = As_r[0]
# とりうる最大値
a_pre = p
qs = [p]
# とりうる最小値
mn = As_r[0]

# 深さ n-1から0まで
for i,a in enumerate(As_r[1:]):
    d = n - i - 1
    p = min(2**d, p + a)
    mn = (mn+1)//2 + a
    a_pre = a
    qs.append(p)

if mn != 1:
    print(-1)
    exit()

qs.reverse()
# print(qs,As)
ans = qs[0]
cnt = qs[0]
# 上から見る
for i in range(1,n+1):
    qs[i] = min(2**i, 2*(qs[i-1]-As[i-1]),qs[i])
print(sum(qs))