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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()

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


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

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

print(ans)

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()

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

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

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split())) #深さiの葉の数
    B = [0] * (n + 1)   #深さiの、葉でない頂点の数
    sum_A = sum(A[1:]) # その深さ以上の葉の数の和

    B[0] = 1 - A[0]
    if sum_A == 0:
        if B[0] == 0:
            print(1)
        else:
            print(-1)
        sys.exit()
    ans = 1
    for i in range(1, n + 1):
        sum_A -= A[i]
        max_b = min(2*B[i-1] - A[i], sum_A)
        if max_b + A[i] < B[i-1] or max_b < 0:
            print(-1)
            sys.exit()
        else:
            B[i] = max_b
        ans += A[i] + max_b

    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

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

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


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

Submission status: Accepted

Solution code:


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


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


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


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

Submission status: Accepted

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

if(N == 0):
    if(As[0] == 1):
        print(1)
    else:
        print(-1)
else:
    flag = True
    if(As[0] != 0):
        flag = False
    if(flag):
        D = [[0]*3 for i in range(N+1)]
        D[0] = [1,1,0] # mind maxD Ed
        for i in range(1,N+1):
            if(As[i] > 2*D[i-1][1]):
                flag = False
                break
            else:
                D[i][0] = max(0,D[i-1][0] - As[i])
                D[i][1] = min(2*D[i-1][1] - As[i],1 << i)
                D[i][2] = As[i]
    if(flag):
        D[N][1] = 0
        maxcnt = 0
        for i in range(N,-1,-1):
            depthmax = D[i][1] + D[i][2]
            maxcnt += depthmax
            if(i > 0):
                D[i-1][1] = min(D[i-1][1],depthmax)
        print(maxcnt)
    else:
        print(-1)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = []
    now = 1
    ans = 0
    for i in range(n+1):
        if a[i] > now:
            print(-1)
            return
        else:
            dp.append(now)
            now -= a[i]
            now *= 2
    now = 0
    for i in range(n, -1, -1):
        now += a[i]
        ans += min(now, dp[i])
    print(ans)


main()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

limit=[1]

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

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

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


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

print(ans)

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import operator
from typing import Iterable, Tuple, Union

Shape = Union[int, Tuple[int, ...], Iterable[int]]
RangeShape = Union[slice, Tuple[slice, ...]]
Indices = Union[int, Tuple[int, ...]]

class nd (object):
    getter = (
        lambda a, i: a,
        lambda a, i: a[i[0]],
        lambda a, i: a[i[0]][i[1]],
        lambda a, i: a[i[0]][i[1]][i[2]],
        lambda a, i: a[i[0]][i[1]][i[2]][i[3]],
        lambda a, i: a[i[0]][i[1]][i[2]][i[3]][i[4]],
        lambda a, i: a[i[0]][i[1]][i[2]][i[3]][i[4]][i[5]],
    )

    class _setter (object):
        def __getitem__(self, n: int):
            setter_getter = nd.getter[n - 1]

            def setter(a, i, v):
                setter_getter(a, i[:-1])[i[-1]] = v
            return setter
    setter = _setter()
    initializer = (
        lambda s, v: [v] * s,
        lambda s, v: [v] * s[0],
        lambda s, v: [[v] * s[1] for _ in range(s[0])],
        lambda s, v: [[[v] * s[2] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, v: [[[[v] * s[3] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, v: [[[[[v] * s[4] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, v: [[[[[[v] * s[5] for _ in range(s[4])] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
    )
    func_initializer = (
        lambda s, f: [f() for _ in range(s)],
        lambda s, f: [f() for _ in range(s[0])],
        lambda s, f: [[f() for _ in range(s[1])] for _ in range(s[0])],
        lambda s, f: [[[f() for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, f: [[[[f() for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, f: [[[[[f() for _ in range(s[4])] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, f: [[[[[[f() for _ in range(s[5])] for _ in range(s[4])] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
    )
    shape_getter = (
        lambda a: len(a),
        lambda a: (len(a),),
        lambda a: (len(a), len(a[0])),
        lambda a: (len(a), len(a[0]), len(a[0][0])),
        lambda a: (len(a), len(a[0]), len(a[0][0]), len(a[0][0][0])),
        lambda a: (len(a), len(a[0]), len(a[0][0]), len(a[0][0][0]), len(a[0][0][0][0])),
        lambda a: (len(a), len(a[0]), len(a[0][0]), len(a[0][0][0]), len(a[0][0][0][0]), len(a[0][0][0][0][0])),
    )
    indices_iterator = (
        lambda s: iter(range(s)),
        lambda s: ((i,) for i in range(s[0])),
        lambda s: ((i, j) for j in range(s[1]) for i in range(s[0])),
        lambda s: ((i, j, k) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
        lambda s: ((i, j, k, l) for l in range(s[3]) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
        lambda s: ((i, j, k, l, m) for m in range(s[4]) for l in range(s[3]) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
        lambda s: ((i, j, k, l, m, n) for n in range(s[5]) for m in range(s[4]) for l in range(s[3]) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
    )
    iterable_product = (
        lambda s: iter(s),
        lambda s: ((i,) for i in s[0]),
        lambda s: ((i, j) for j in s[1] for i in s[0]),
        lambda s: ((i, j, k) for k in s[2] for j in s[1] for i in s[0]),
        lambda s: ((i, j, k, l) for l in s[3] for k in s[2] for j in s[1] for i in s[0]),
        lambda s: ((i, j, k, l, m) for m in s[4] for l in s[3] for k in s[2] for j in s[1] for i in s[0]),
        lambda s: ((i, j, k, l, m, n) for n in s[5] for m in s[4] for l in s[3] for k in s[2] for j in s[1] for i in s[0]),
    )
    flattener = (
        lambda a: iter(a),
        lambda a: iter(a),
        lambda a: (y for z in a for y in z),
        lambda a: (x for z in a for y in z for x in y),
        lambda a: (w for z in a for y in z for x in y for w in x),
        lambda a: (v for z in a for y in z for x in y for w in x for v in w),
        lambda a: (u for z in a for y in z for x in y for w in x for v in w for u in v),
    )

    @classmethod
    def full(cls, fill_value, shape: Shape):
        if isinstance(shape, int):
            return cls.initializer[0](shape, fill_value)
        elif not isinstance(shape, tuple):
            shape = tuple(shape)
        return cls.initializer[len(shape)](shape, fill_value)

    @classmethod
    def nones(cls, shape: Shape):
        return cls.full(None, shape)

    @classmethod
    def zeros(cls, shape: Shape, type=int):
        return cls.full(type(0), shape)

    @classmethod
    def ones(cls, shape: Shape, type=int):
        return cls.full(type(1), shape)

    @classmethod
    def fromiter(cls, iterable: Iterable, ndim=1):
        if ndim == 1:
            return list(iterable)
        else:
            return list(map(cls.fromiter, iterable))

    class _range (object):
        def __getitem__(self, shape: RangeShape):
            if isinstance(shape, slice):
                return iter(range(shape.stop)[shape.start:][::shape.step])
            else:
                shape = tuple(range(s.stop)[s.start:][::s.step] for s in shape)
                return nd.iterable_product[len(shape)](shape)
    range = _range()

    @classmethod
    def ensure_shape_tuple(cls, shape: Shape):
        if isinstance(shape, int):
            return shape,
        elif not isinstance(shape, tuple):
            return tuple(shape)
        else:
            return shape

    @classmethod
    def ensure_indices_tuple(cls, indices: Indices):
        if isinstance(indices, int):
            return indices,
        else:
            return indices

    @classmethod
    def join_shapes(cls, *shapes: Shape):
        return tuple(map(cls.ensure_shape_tuple, shapes))

def bytes_to_str(x: bytes):
    return x.decode('utf-8')

def inputs(func=bytes_to_str, sep=None, maxsplit=-1):
    return map(func, sys.stdin.buffer.readline().split(sep=sep, maxsplit=maxsplit))

def inputs_1d(func=bytes_to_str, **kwargs):
    return nd.fromiter(inputs(func, **kwargs))

def inputs_2d(nrows: int, func=bytes_to_str, **kwargs):
    return nd.fromiter(
        (inputs(func, **kwargs) for _ in range(nrows)),
        ndim=2
    )

def inputs_2d_T(nrows: int, func=bytes_to_str, **kwargs):
    return nd.fromiter(
        zip(*(inputs(func, **kwargs) for _ in range(nrows))),
        ndim=2
    )

N, = inputs(int)
A = inputs_1d(int)
cum_A = nd.zeros(N + 1, int)
cum_A[0] = A[0]
for i in nd.range[1:N + 1]:
    cum_A[i] = cum_A[i - 1] + A[i]

B = nd.zeros(N + 1, int)
B[0] = 1

constructable = True

for d in nd.range[:N]:
    if B[d] < A[d]:
        constructable = False
        break
    B[d] = B[d] - A[d]
    B[d + 1] = min(B[d] * 2, cum_A[N] - cum_A[d])

if constructable:
    if A[N] != B[N]:
        constructable = False
        print(-1)
    else:
        B[N] = 0
        print(sum(A) + sum(B))
else:
    print(-1)

Submission status: Accepted

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

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

##ノードの数を増やせるだけ増やす##
non_leaf_node = []
tmp = 1
for i in range(0,N+1):
    tmp = tmp -A[i]
    if tmp < 0:#頂点数が0以下になってはいけない
        print(-1)
        exit()
    non_leaf_node.append(tmp)
    tmp *= 2
non_leaf_node[-1]=0
##後ろ側から頂点の最大数を足し上げる##
##頂点数=node[i] = (non_leaf_node[i+1]+A[i+1] または non_leaf_node[i]+leaf[i])+leaf


ans = A[-1]
for i in range(N-1,-1,-1):
    non_leaf_node[i] = min(non_leaf_node[i],non_leaf_node[i+1]+A[i+1])
    ans += non_leaf_node[i]+A[i]
print(ans)

Submission status: Accepted

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

ans = 0
nonleaf_nodes = []
current = 1

# とりあえず増やせるだけ頂点を増やしていく
for depth in range(0, n+1):
    c = current-a[depth]
    # 目いっぱい頂点を増やしても葉を賄えない場合、木を作れない
    if c < 0:
        print(-1)
        exit()
    nonleaf_nodes.append(c)
    current = c*2
nonleaf_nodes[-1]=0

# 余計な頂点を最深層から削除していく
# 下位層の葉を含む頂点数を超えると上位層で葉が増えるのでNG
ans = a[-1]
for depth in range(n-1, -1, -1):
    nonleaf_nodes[depth] = min(nonleaf_nodes[depth], nonleaf_nodes[depth+1]+a[depth+1])
    ans += nonleaf_nodes[depth] + a[depth]
print(ans)

Submission status: Accepted

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

ans = 0
nonleaf_nodes = []
current = 1

for depth in range(0, n+1):
    c = current-a[depth]
    if c < 0: # 目いっぱい頂点を増やしても葉が足りない
        print(-1)
        exit()
    nonleaf_nodes.append(c)
    current = c*2
nonleaf_nodes[-1]=0

ans = a[-1]
for depth in range(n-1, -1, -1):
    nonleaf_nodes[depth] = min(nonleaf_nodes[depth], nonleaf_nodes[depth+1]+a[depth+1])
    ans += nonleaf_nodes[depth] + a[depth]
print(ans)

Submission status: Accepted

Solution code:

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    n = int(input())
    a = list(map(int, input().split()))
    s = [0]
    for i in range(n+1):
        s.append(s[-1]+a[~i])
    s.reverse()
    max_nodes = 1
    ans = 0
    for i in range(n+1):
        if a[i] > max_nodes:
            print(-1)
            return
        ans += min(max_nodes, s[i])
        max_nodes -= a[i]
        max_nodes *= 2

    print(ans)
        
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    if n == 0:
        return 1

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
leaf = sum(a) - 1
now = 1
ans = 0
for i, num in enumerate(a):
    ans += now
    now -= num
    if leaf >= now:
        leaf -= now
        now *= 2
    elif leaf > 0:
        now += leaf
        leaf = 0
    if now < 0:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''　標準入力
1行のint=====================================
N, K = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
A = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''


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

B = A.copy()
B.reverse()

upper = [0] * (N+1)
upper[0] = B[0]
for i in range(N):
    upper[i + 1] = upper[i] + B[i+1]
upper.reverse()

V = [0] * (N+1)
if A[0] == 1:
    if N >= 1:
        print(-1)
        sys.exit()
    elif N == 0:
        print(1)
        sys.exit()

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

V[0] = 1
for d in range(1, N + 1):
    can = min((V[d-1] - A[d-1]) * 2, upper[d])
    least = V[d-1] - A[d-1]

    if A[d] > can or least > can:
        print(-1)
        sys.exit()

    V[d] = can

V[N] = A[N]

ans = 0
for v in V:
    ans += v

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

L = [0]*(n+2)
R = [0]*(n+2)
L[n] = A[n]
R[n] = A[n]

for i in range(n,-1,-1):
  L[i] = A[i] + (L[i+1]+1)//2
  R[i] = A[i] + R[i+1]
  
if L[0]>1:
  print(-1)
else:
  tmp = 1
  ans = 0
  for i in range(n+1):
    ans += tmp
    tmp -= A[i]
    tmp = min(tmp*2,R[i+1])    
  print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

# 根から頂点数を確定，根は1
B = [1]
P = 1

for i in range(N):
    # 今の頂点数の2倍を超えられない (葉は)
    if B[i] * 2 < A[i + 1]:
        print(-1)
        exit()
    P += min(2 * B[i], cA[i + 1])
    # 今使う個数と，内点の個数
    B.append(min(2 * B[i], cA[i + 1]) - A[i + 1])
    if B[-1] < 0:
        print(-1)
        exit()

print(P)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
flg = True
n_node = 0.5
ans = 0
As = [0]*(N+2)
for i in range(N, -1, -1):
    As[i] = As[i+1] + A[i]
for i in range(N+1):
    if A[i] > n_node*2:
        flg = False
        break
    n_node = min(int(n_node*2)-A[i], As[i+1])
    ans += n_node + A[i]
print(ans if flg else -1)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
if A[0] != 0:
    if N == 0 and A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
ans = 1
n = 1
if A[0] > 1:
    print(-1)
    exit()
cumr = list(itertools.accumulate(A[::-1]))[::-1]
for i in range(1, N + 1):
    minn = n - A[i - 1]
    n = min(2 * minn, cumr[i])
    if n>=minn and n>=A[i]:
        ans += n
    else:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
arr=list(map(int,input().split()))
ans=sum(arr)
if n==0:
  if arr[0]==1:
    print(1)
  else:
    print(-1)
  exit()
for i in range(n):
  if i<=30 and arr[i]>=2**i:
    print(-1)
    exit()
if n<=30 and arr[n]>2**n:
  print(-1)
  exit()
maxs=[0]*(n+1)
maxs[0]=1
for i in range(1,n):
  maxs[i]=2*maxs[i-1]-arr[i]
tmp=arr[n]
for i in range(n-1,-1,-1):
  maxs[i]=min(maxs[i],tmp)
  tmp+=arr[i]
mins=[0]*(n+1)
for i in range(n-1,-1,-1):
  mins[i]=(mins[i+1]+arr[i+1]+1)//2
for i in range(n):
  if maxs[i]<mins[i]:
    print(-1)
    exit()
ans+=sum(maxs)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N==0:
  if A[0]==1:
    print(1)
  else:
    print(-1)
  exit()
if A[0]:
  print(-1)
  exit()
C=[A[N]]
for i in range(N):
  C.append(C[i]+A[-i-2])
C=C[::-1]
B=[1]
P=1
for i in range(N):
  if (B[i]<<1)<A[i+1]:
    print(-1)
    exit()
  P+=min((B[i]<<1),C[i+1])
  B.append(min((B[i]<<1),C[i+1])-A[i+1])
  if B[-1]<0:
    print(-1)
    exit()
print(P)

Submission status: Accepted

Solution code:
print(max(-(b:=(c:=sum(a:=[*map(int,[*open(0)][1].split())]))>0),sum((b:=min(c:=c-a,b-a<<1))for a in a)+1))

Submission status: Accepted

Solution code:
c=sum(a:=[*map(int,[*open(0)][1].split())])
b=1
print(max(-1,sum((b:=min(c:=c-a,b-a<<1))for a in a)+1))