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

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul

mod = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

n = I()
A = LI()
max_ret = 0
min_ret = 0
max_arr = [0] * (n + 1)
min_arr = [0] * (n + 1)
for i in range(n, -1, -1):
    max_ret = max_ret + A[i]
    min_ret = (min_ret + 1) // 2 + A[i]
    max_arr[i] = max_ret
    min_arr[i] = min_ret

if max_ret >= 1 >= min_ret:
    ans = 1
    ret = 1 - A[0]
    for j in range(1, n + 1):
        ret = min(ret * 2, max_arr[j])
        ans += ret
        ret -= A[j]
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    lim = [None]*(n+1)
    f = True
    lim[0] = 1 - a[0]
    for i in range(1, n+1):
        lim[i] = lim[i-1]*2
        lim[i] -= a[i]
    ans = 0
    pre = 0
    for i in reversed(range(n+1)):
        if (pre+1)//2 > lim[i]:
            f = False
            break
        x = a[i] + min(lim[i], pre)
        ans += x
        pre = x
    if f:
        print(ans)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

INF=10**18

pr=[0]*(n+2)

pr[0]=1

for i in xrange(n+1):
	pr[i+1]=min(INF,(pr[i]-a[i])*2)

if pr[n+1]<0:
	print "-1"
	exit(0)

s=0
ans=0

for i in xrange(n,-1,-1):
	s=min(s+a[i],pr[i])
	ans+=s

print ans

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
section = [[A[-1], A[-1]]]
for i in range(1, N+1):
    min_section = math.ceil(section[i-1][0] / 2) + A[-i-1]
    max_section = section[i-1][1] + A[-i-1]
    section.append([min_section, max_section])
section = section[::-1]

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

node = [1]

for i in range(1, N+1):
    node.append(min((node[i-1] - A[i-1]) * 2, section[i][1]))

print(sum(node))

Submission status: Accepted

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

L = [0] * N + [A[N]]    # 下限
U = [0] * N + [A[N]]    # 上限
for i in range(N - 1, -1, -1):
    L[i] = (L[i + 1] + 1) // 2 + A[i]
    U[i] = U[i + 1] + A[i]

if 1 < L[0]:
    print(-1)
    sys.exit()

U[0] = 1
for i in range(1, N + 1):
    U[i] = min(2 * (U[i - 1] - A[i - 1]), U[i])   # 深さiの頂点数

print(sum(U))

Submission status: Accepted

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import math

N = INT()
A = LIST()


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


node_min, node_max = [0]*(N+1), [0]*(N+1)
node_min[-1] = A[-1]
node_max[-1] = A[-1]
for i in reversed(range(N)):
    node_min[i] = math.ceil(node_min[i+1]/2) + A[i]
    node_max[i] = node_max[i+1] + A[i]


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

ans = 1
node = 1
for i in range(1, N+1):
    node = min(node_max[i], 2*node)
    ans += node
    node = node - A[i]


print(ans)

Submission status: Accepted

Solution code:
import math

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

    max_node = [0 for i in range(n+1)]
    min_node = [0 for i in range(n+1)]
    res = 0

    for i in range(n, -1, -1):
        if i == n:
            max_node[i] = A[i]
            min_node[i] = A[i]
        elif i == 0:
            max_node[i] = 1
            min_node[i] = 1
        elif i == 1 and n != 1:
            max_node[i] = 2
            min_node[i] = math.ceil(min_node[i+1] /2) + A[i]
        else:
            max_node[i] = max_node[i+1] + A[i]
            min_node[i] = math.ceil(min_node[i+1] / 2) + A[i]

    for i in range(n):
        if i == 0:
            if n != 0 and A[i] != 0:
                res = -1
                break
        else:
            if max_node[i] > 2 * (max_node[i-1] - A[i-1]):
                max_node[i] = 2 * (max_node[i-1] - A[i-1])
            if max_node[i] < min_node[i]:
                res = -1
                break
    
    if res == -1:
        print(res)
    else:
        if n == 0 and A[i] != 1:
            print(-1)
        else:
            print(sum(max_node))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def solve():
    cur = 1
    res = 0
    for i in range(n+1):
        if cur < a[i]: return -1
        res += cur
        cur -= a[i]
        if cur > s[i+1]: return -1
        cur = min(cur*2, s[i+1])
    return res

print(solve())

Submission status: Accepted

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

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

INF = 10 ** 13 + 100

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

Solution code:

from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"
n = int(input())
a= list(map(int , input().split()))
s = sum(a)
f = 1
if n == 0:
  if a[0] != 1:
    print(-1)
    exit()
  else:
    print(1)
    exit()
elif a[0]!=0:
  print(-1)
  exit()
ans = 1
node = 1
for i in range(1,n+1):
  node=min(2*node, s)
  ans+=node
  node-=a[i]
  s-=a[i]
  if node < 0:
    print(-1)	
    exit()
if f: print(ans)

Submission status: Accepted

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

ar = list(reversed(a))
#print(ar)
com = [ar[0]]
for i in range(n):
    com.append(com[i] + ar[i+1])
#print(com)
com.reverse()
ans = 0
val = 1
for i in range(n+1):

    ans += min(val,com[i])
    val -= a[i]
    if (i < n and val <= 0) or (i == n and val < 0) or (i == n and a[i] == 0):
        print(-1)
        exit()
    val *= 2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] == 0:
    print(-1)
    exit()
if n != 0 and a[0] >= 1:
    print(-1)
    exit()
if n == 0 and a[0] >= 2:
    print(-1)
    exit()
ar = list(reversed(a))
#print(ar)
com = [ar[0]]
for i in range(n):
    com.append(com[i] + ar[i+1])
#print(com)
com.reverse()
ans = 1
val = 1
for i in range(1,n+1):
    val *= 2
    ans += min(val,com[i])
    val -= a[i]
    if (i < n and val <= 0) or (i == n and val < 0):
        print(-1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

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

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

if min(cond1) <= 0:
    print(-1)
    exit()

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

if min(cond2) <= 0:
    print(-1)
    exit()

if cond2[N] < A[N]:
    print(-1)
    exit()

ans = sum(cond2)
print(ans)

Submission status: Accepted

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

print(sum(b)+s)

Submission status: Accepted

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
S = [0]
for a in reversed(A):
    S.append(S[-1] + a)
S.reverse()

lst = [0] * (N + 2)
lst[0] = 1
for i, a in enumerate(A):
    if lst[i] < a:
        print(-1)
        break
    lst[i + 1] = min((lst[i] - a) * 2, S[i + 1])
else:
    print(sum(lst))

Submission status: Accepted

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

# nowは今見てる深さに存在しうる最大の頂点数
# max[i] := 深さiに存在しうる最大の頂点数
# maxが2*10^18超えたら無視してる
now, max = 1, [None] * (n + 1)
for i in range(n + 1):
  if a[i] > now:
    print(-1)
    exit(0)
  max[i] = now
  now = min((now - a[i]) * 2, 2000000000000000000)

# 次にボトムアップ
# upは今見ている深さに対して登ってくる辺数
# 当然だけど、up + a[i]がその深さに存在しうる最大の頂点数
# だから、min(max[i], up + a[i])が深さiに存在しうる最大の頂点数になる
# あとはその和を取る
ans, up = 0, 0
for i in range(n, -1, -1):
  count = min(max[i], up + a[i])
  ans += count
  up = count
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
res=0
m=1

for i in a:
    b=m-i
    if b<0:
        print(-1)
        exit(0)
    res+=i
    res+=b
    s-=i
    m=min(b*2,s)
print(res)

Submission status: Accepted

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

now, max = 1, [None] * (n + 1)
for i in range(n + 1):
  if a[i] > now:
    print(-1)
    exit(0)
  max[i] = now
  now = min((now - a[i]) * 2, 2000000000000000000)

ans, up = 0, 0
for i in range(n, -1, -1):
  count = min(max[i], up + a[i])
  ans += count
  up = count
print(ans)

Submission status: Accepted

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

node_max = [1]
for i in range(1, n+1):
    node_max.append(min(10**18, node_max[i-1]*2-a[i]))

a.reverse()
node_max.reverse()

node_max2 = [a[0]]
node_min2 = [a[0]]

for i in range(n):
    node_max2.append(node_max2[-1]+a[i+1])
    node_min2.append((node_min2[-1]+1)//2+a[i+1])

if node_min2[-1] != 1:
    print(-1)
else:
    ans = 0
    for i in range(n+1):
        ans += min(node_max[i]+a[i], node_max2[i])

    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.reverse()
min_max = [[] for _ in range(N+1)]

def main():
    min_max[0] = [A[0], A[0]]
    for i in range(1, N+1):
        a = A[i]
        pre_min, pre_max = min_max[i-1]
        min_max[i] = [(1+pre_min)//2 +a, pre_max +a]
    min_max.reverse()
    if min_max[0][0] != 1:
        print(-1)
        return
    A.reverse()
    ans = 1
    pre = 1
    for i in range(1, N+1):
        a = A[i-1]
        pre = min(2*(pre -a), min_max[i][1])
        ans += pre
    print(ans)

main()

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
low = [0]*(N+1)
high = [0]*(N+1)
low[N] = A[N]
high[N] = A[N]

for i in range(N-1, -1, -1):
    low[i] = (low[i+1]+1)//2+A[i]
    high[i] = high[i+1]+A[i]

if not low[0]<=1<=high[0]:
    print(-1)
    exit()

ans = 1
now = 1

for i in range(N):
    now = min(2*(now-A[i]), high[i+1])
    ans += now

print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())
a = [int(x) for x in input().split()[::-1]]

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

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

limit = [[a[0], a[0]]]
for i in range(0, n):
    low = -(-limit[i][0] // 2) + a[i + 1]
    high = limit[i][1] + a[i + 1]
    
    limit.append([low, high])
    
limit = limit[::-1]
a = a[::-1]

if 1 < limit[0][0]:
    print(-1)
    sys.exit()

ans, leaf = 1, 2
for i in range(1, n):
    ans += min(limit[i][1], leaf)
    leaf = 2 * (leaf - a[i])
    
ans += a[n]
print(ans)

Submission status: Accepted

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

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

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

v, ans = 1, 1
for i in range(N):
    v = min((v-A[i])*2, R[i+1])
    ans += v

print(ans)

Submission status: Accepted

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

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


# 成り立つ木が作れるか判定してみる
en = [0]
en[0] = 1

for a in A_list:
    tmp = en[-1] - a
    if tmp < 0:
        print(-1)
        exit()
    en.append(tmp * 2)

en = en[:-1]

branch = A_list[-1]
res = A_list[-1]
nodes = en[-1]
for a, ena in zip(A_list[-2::-1], en[-2::-1]):
    branch = min(branch+a, ena)
    res += branch

print(res)

Submission status: Accepted

Solution code:
DEBUG = False

N = int(input())
LEAVES = [int(i) for i in input().split()]

ranges_num_nodes = [[0 for _ in range(2)] for _ in range(N + 1)]
ranges_num_nodes[N][0] = LEAVES[N]
ranges_num_nodes[N][1] = LEAVES[N]

if DEBUG:
    print("ranges_num_nodes: {}".format(ranges_num_nodes))

for depth in range(N, 0, -1):
    ranges_num_nodes[depth-1][0] = LEAVES[depth-1] + (ranges_num_nodes[depth][0] + 1) // 2
    ranges_num_nodes[depth-1][1] = LEAVES[depth-1] + ranges_num_nodes[depth][1]

if DEBUG:
    print("ranges_num_nodes: {}".format(ranges_num_nodes))

num_nodes = [0] * (N + 1)
num_nodes[0] = 1

if DEBUG:
    print("num_nodes: {}".format(num_nodes))

for depth in range(N):
    num_nodes[depth+1] = min((num_nodes[depth] - LEAVES[depth]) * 2, ranges_num_nodes[depth+1][1])

if DEBUG:
    print("num_nodes: {}".format(num_nodes))

for depth in range(N+1):
    if num_nodes[depth] < ranges_num_nodes[depth][0]:
        print(-1)
        break
else:
    print(sum(num_nodes))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0]*(n+1)
if n == 0:  # ねっこだけ
    x = a[0]
    if x == 1:
        print(1)
    else:
        print(-1)
    exit()

nows = sum(a)
s = nows
for i in range(n+1):
    if i == 0:
        b[i] = 1 - a[i]
    else:
        nows -= a[i]
        b[i] = min(nows, 2*b[i-1]-a[i])
        if b[i] < 0:  # だめ
            print(-1)
            exit()
print(sum(b) + s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
cap = [[0, 0] for _ in range(N+1)]
cap[-1] = [A[-1], A[-1]]
for i in range(N-1,-1,-1):
    cap[i][0] = (cap[i+1][0] + 2 - 1)//2
    cap[i][1] = cap[i+1][1] + A[i]
ans = 1
nodes = 1
failed = nodes < cap[0][0]
for i in range(N):
    nodes = min((nodes - A[i])*2, cap[i+1][1])
    if nodes < cap[i+1][0]:
        failed = True
        break
    ans += nodes
print(-1 if failed else ans)

Submission status: Accepted

Solution code:
from math import log2

N = int(input())
A = [int(i) for i in input().split()]

def solve() :
  m, M = A[-1], A[-1]
  max1 = [0] * (N + 1)
  max1[-1] = M
  for i in range(N - 1, -1, -1) :
    m = (m + 1) // 2 + A[i]
    M = M + A[i]
    max1[i] = M
  if not m <= 1 <= M :
    return -1
  
  ne = 1 - A[0]
  max2 = [0] * (N + 1)
  max2[0] = 1
  for i in range(1, N + 1) :
    ne = ne * 2 - A[i]
    max2[i] = ne + A[i]
    
  return sum(min(max1[i], max2[i])for i in range(N + 1))
  
print(solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int, input().split()))
    node_count = [0] * (N+1)
    for i, a in enumerate(A[::-1]):
        if i == 0:
            node_count[N] = a
            continue
        node_count[N-i] = node_count[N-i+1] + a
    can_build = True
    for i, a in enumerate(A):
        if i == 0:
            if N > 0 and a > 0:
                can_build = False
                break
            if N == 0 and a > 1:
                can_build = False
                break
            node_count[0] = min(node_count[0], 1)
            continue
        if (i < N and a >= node_count[i-1]*2) or (i == N and a > node_count[i-1]*2):
            can_build = False
            break
        node_count[i] = min(node_count[i], node_count[i-1]*2-A[i-1]*2)
    if can_build:
        ans = sum(node_count)
    else:
        ans = -1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

sum_leaves = [0]*(n+1)
sum_leaves[0] = leaves[0]
for depth in range(n):
    sum_leaves[depth+1] = sum_leaves[depth] + leaves[depth+1]

ans = 0

root = [None] * (n + 1)
if n == 0:
    root[0] = 0
else:
    root[0] = 1
if root[0] + leaves[0] != 1:
    print(-1)
else:
    for depth in range(n):
        root[depth+1] = min(2*root[depth]-leaves[depth+1],
                            sum_leaves[n]-sum_leaves[depth+1])
        if root[depth + 1] < root[depth] - leaves[depth + 1] or root[depth+1] < 0:
            print(-1)
            break
    else:
        print(sum(root)+sum(leaves))

Submission status: Accepted

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N = iRaw()
    As = isRaw()
    Vs = [1]
    sumA = sum(As)
    for d in range(N+1):
        if As[d] > Vs[d]:
            print(-1)
            return -1
        sumA-=As[d]
        Vs+=[min((Vs[d]-As[d])*2,sumA)]
    print(sum(Vs[:N+1]))

main()

Submission status: Accepted

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

ans = 0
nodes_min = [0] * (n + 1)
nodes_max = [0] * (n + 1)
nodes_min[n] = leaves[n]
nodes_max[n] = leaves[n]

for depth in range(n, 0, -1):
    root_min = nodes_min[depth] // 2 + nodes_min[depth] % 2
    nodes_min[depth - 1] = leaves[depth - 1] + root_min
    root_max = nodes_max[depth]
    nodes_max[depth - 1] = leaves[depth - 1] + root_max
nodes = [0] * (n + 1)
nodes[0] = 1
if nodes[0] < nodes_min[0]:
    print(-1)
else:
    for depth in range(n):
        roots = nodes[depth]-leaves[depth]
        nodes[depth + 1] = min(roots * 2, nodes_max[depth + 1])
        if nodes[depth+1] < nodes_min[depth+1]:
            print(-1)
            break
    else:
        print(sum(nodes))

Submission status: Accepted

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

ans = 1
if l[0][0] == 1:
    num = [1]
    for i in range(n):
        num.append(
            min(
                l[i+1][-1], 
                (num[i]-a[i])*2
                
                )
            )
        ans += num[i+1]

    print(ans)
else:
    print(-1)

Submission status: Accepted

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

from_deeper_bind = [[0,0] for i in range(N+1)]
from_deeper_bind[N][0] = from_deeper_bind[N][1] = A[N]
node_num = [1]*(N+1)
node_num[N] = A[N]
from_shallower_bind = [1]*(N+1)

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


if not from_deeper_bind[0][0] <= 1 <= from_deeper_bind[0][1]:
    print(-1)
    exit()


for i in range(1,N):
    from_shallower_bind[i] = (node_num[i-1]-A[i-1])*2
    node_num[i] = min(from_shallower_bind[i],from_deeper_bind[i][1])

print(sum(node_num))

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
nodes_min = [0] * (n + 1)
nodes_max = [0] * (n + 1)
nodes_min[n] = leaves[n]
nodes_max[n] = leaves[n]

for depth in range(n, 0, -1):
    root_min = nodes_min[depth] // 2 + nodes_min[depth] % 2
    nodes_min[depth - 1] = leaves[depth - 1] + root_min
    root_max = nodes_max[depth]
    nodes_max[depth - 1] = leaves[depth - 1] + root_max
nodes = [0] * (n + 1)
nodes[0] = 1
for depth in range(n):
    roots = nodes[depth]-leaves[depth]
    nodes[depth + 1] = min(roots * 2, nodes_max[depth + 1])
for depth in range(n+1):
    if nodes[depth] < nodes_min[depth]:
        print(-1)
        break
else:
    print(sum(nodes))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * (n+1)
    if n == 0:
        x = A[0]
        if x == 1:
            print(1)
        else:
            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: Accepted

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

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)
else:
    if A[0] !=0:
        print(-1)
        exit()
    else:
        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: Accepted

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

node = [[] for i in range(N + 1)]
idx = list(range(N+1))  # 0 ~ N
idx = idx[1:]  # 1 ~ N

# Depth = N
node[0].append(A[N])
node[0].append(A[N])

for i in idx:
    # min
    node[i].append(- (- node[i - 1][0] // 2) + A[- i - 1])
    # max
    node[i].append(node[i - 1][1] + A[- i - 1])

if 1 not in node[-1]:
    print(-1)
    exit()

node.reverse()
idx = list(range(N + 1))
idx = idx[1:]
maximum = []
maximum.append(1)

for i in idx:
    val = min(node[i][1], (maximum[i - 1] - A[i - 1]) * 2)
    maximum.append(val)

print(sum(maximum))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
  
def solve(N, A):
  
  if N == 0 and A[0] > 1 or N > 0 and A[0] > 0:
    print(-1)
    return

  total = sum(A[1:])
  #t = A[-1] + A[-2]
  par = 1 - A[0]
  rt = 1
  for i, a in enumerate(A[1:]):
    total -= a
    max_node = par * 2
    cur = max_node - a
    if cur < 0:
      print(-1)
      return
    cur = min(total, cur)
    #print(i+1, a, cur)
    rt += a
    if i + 1 < N:
      rt += cur
    par = cur  
   
  print(rt)
  
solve(N, A)

Submission status: Accepted

Solution code:
from math import ceil

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

a.reverse()

max_tree = [0] * (n+1)
min_tree = [0] * (n+1)

max_tree[0] = a[0]
min_tree[0] = a[0]
for i in range(1, n+1):
    max_tree[i] = max_tree[i-1] + a[i]
    min_tree[i] = ceil(min_tree[i-1]/2) + a[i]

max_tree.reverse()
min_tree.reverse()

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

a.reverse()
possible = [0] * (n+1)
possible[0] = 1

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

print(sum(possible))

Submission status: Accepted

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

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
tree=1
node=sum(A)
flag=0
for i in A:
    ans+=i
    node-=i
    if i>tree:
        ans=-1
        break
    tree-=i
    if tree<node:
        ans+=tree
    else:
        ans+=node
    tree=2*tree
print(ans)

Submission status: Accepted

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 n == 0:
    if a[0] == 1:
        print(1)
    else:
        print(-1)
    exit()    

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)