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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ####################
    import sys
    class Lazysegtree():
        """RAQ
        外から使うのは，query，add,updateくらいか
        
        """
        def __init__(self, A, intv, initialize = True, segf = min):
            """
            Aが初期配列，intvが単位元,segfが評価関数
            """
            
            #区間は 1-indexed で管理
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.intv = intv
            self.segf = segf
            self.lazy = [0]*(2*self.N0)
            if initialize:
                self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [intv]*(2*self.N0)

        def _ascend(self, k):
            k = k >> 1
            c = k.bit_length()
            for j in range(c):
                idx = k >> j
                self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1]) \
                + self.lazy[idx]
                
        def _descend(self, k):
            k = k >> 1
            idx = 1
            c = k.bit_length()
            for j in range(1, c+1):
                idx = k >> (c - j)
                ax = self.lazy[idx]
                if not ax:
                    continue
                self.lazy[idx] = 0
                self.data[2*idx] += ax
                self.data[2*idx+1] += ax
                self.lazy[2*idx] += ax
                self.lazy[2*idx+1] += ax
        
        def update(self, k, x):
            #データの変更
            k = k + self.N0
            self.data[k] = x
            self._ascend(k)
        
        def query(self, l, r):
            #クエリ，[l,r)かな
            L = l+self.N0
            R = r+self.N0
            Li = L//(L & -L)
            Ri = R//(R & -R)
            self._descend(Li)
            self._descend(Ri - 1)
            
            s = self.intv                                                              
            while L < R:
                if R & 1:
                    R -= 1
                    s = self.segf(s, self.data[R])
                if L & 1:
                    s = self.segf(s, self.data[L])
                    L += 1
                L >>= 1
                R >>= 1
            return s
        
        def add(self, l, r, x):
            #区間加算，[l,r)かな
            L = l+self.N0
            R = r+self.N0

            Li = L//(L & -L)
            Ri = R//(R & -R)
            
            while L < R :
                if R & 1:
                    R -= 1
                    self.data[R] += x
                    self.lazy[R] += x
                if L & 1:
                    self.data[L] += x
                    self.lazy[L] += x
                    L += 1
                L >>= 1
                R >>= 1
            
            self._ascend(Li)
            self._ascend(Ri-1)

            
    ##########
    
    mod=10**9+7
    N=I()
    A=LI()
    A[-1]-=1
    if A[0]!=0:
        ans=-1
            
    else:
        ans=N+1
        now=0#キャパがある最上位
        seg=Lazysegtree([1]*(N+1), 10**10, True, min)
        for i in range(1,N+1):
            a=A[i]
            if ans==-1:
                break
            while a>0:
                if now==i:
                    ans=-1
                    break
                
                cap=seg.query(now,now+1)
                #print("i:",i,",a:",a,",now:",now,",cap:",cap,",ans",ans)
                if a>=cap:
                    a-=cap
                    #seg.add(now,now+1,-cap)，now+=1するのでいらない
                    seg.add(now+1,i,cap)
                    ans+=(i-now)*cap
                    now+=1
                    #print(now,cap)
                else:
                    #print(now,cap,"--")
                    
                    seg.add(now,now+1,-a)
                    seg.add(now+1,i,a)
                    ans+=(i-now)*a
                    a=0
                    


                
            
            
    print(ans)
        

main()

Submission status: Accepted

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

n = 1
result = 0
S = sum(A)

for i in range(N+1):
    result += n

    if n < A[i]:
        print(-1)
        break
    n -= A[i]
    S -= A[i]

    if n < S:
        if n*2 < S:
            n *= 2
        else:
            n = S
else:
    print(result)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n = gete(int)
    a = tuple(geta(int))
    s = sum(a)

    cur = 1
    ans = 0

    for ai in a:
        if cur < ai:
            print(-1)
            exit()
        else:
            ans += min(cur, s)
            cur = 2 * (min(cur, s) - ai)
            s -= ai

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a = list(map(int,input().split()))
i=0
b=0
while i<=n:
    b+=a[i]
    i+=1
i=0
x=1
ans=0
while i<=n:
    if a[i] <=x:
        if x<=b:
            ans+=x
            x=(x-a[i])*2
        else:
            ans+=b
            x = b
        b-=a[i]
    else:
        ans=-1
        break
    i+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
ans=0
m=sum(a)
leaf=1
for i in range(n+1):
    ans+=leaf
    leaf=leaf-a[i]
    m-=a[i]

    if leaf<0 or (leaf==0 and m>0):
        print(-1)
        sys.exit()

    tmp=leaf
    for j in range(min(n-i,60)):
        tmp*=2
        if tmp>=m: break
    if tmp<m:
        print(-1)
        sys.exit()        

    if leaf*2>=m: leaf=m
    else: leaf*=2

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  anums=list(map(int,input().split()))
  mx_nonleaves=[0 for _ in range(n+1)]
  if n==0:
    if anums[0]==1:
      return 1
    return -1
  for i,anum in enumerate(anums):
    if i==0:
      if anum>0:
        return -1
      mx_nonleaves[i]=1
      continue
    mx_nonleaves[i]=mx_nonleaves[i-1]*2-anums[i]
    if mx_nonleaves[i]<0:
      return -1
  mx_nonleaves[-1]=0
  #print(mx_nonleaves)
  for idx in range(n,1,-1):
    mx_nonleaves[idx-1]=min(mx_nonleaves[idx-1],mx_nonleaves[idx]+anums[idx])
  #print(anums)
  #print(mx_nonleaves)
  return sum(anums)+sum(mx_nonleaves)

print(main())

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()

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

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


ans = 0

if n == 0:
	if a[0] == 1:
		print(1)
	else:
		print(-1)
else:
	if a[0] != 0:
		print(-1)
		exit()
	ans = 0
	co = 0
	for i in range(n,0,-1):
		if i == n:
			if tw[i] < a[i]:
				print(-1)
				exit()
			else:
				co = a[i]
				ans += a[i]
		else:
			if a[i] + co <= tw[i]:
				ans += a[i] + co
				co = a[i] + co
			else:
				if -(-co//2) + a[i] <= tw[i]:
					ans += tw[i]
					co = tw[i]
				else:
					print(-1)
					exit()

	print(ans+1)

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] != 0:
    print(-1)
    exit()

s = sum(a)
ans = 1
m = 1
flag = True
for i in range(1, n+1):
    if flag:
        m *= 2
        if m > s:
            m = s
            flag = False
    ans += m
    if a[i] > m:
        print(-1)
        exit()
    m -= a[i]
    s -= a[i]

print(ans)

Submission status: Accepted

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
    if N == 0 and A[0] >= 2:
        print(-1)
        return

    for i in range(1,N + 1):
        can_root[i] = 2*can_root[i - 1] - A[i]
        if i < N:
            if can_root[i] <= 0:
                print(-1)
                return 
        if i == N:
            if can_root[i] < 0:
                print(-1)
                return
    
    ans = A[-1]
    now = A[-1]
    for i in range(N - 1,-1,-1):
        if now <= can_root[i]:
            now += A[i]
        else:
            now = can_root[i] + A[i]
        ans += now
    print(ans)
if __name__ == '__main__':
    main()

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]>0:
  print(-1)
  exit()

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

ans=1
x=1
for i in range(1, N+1):
  if x*2<A[i]:
    print(-1)
    exit()
  elif x*2==A[i] and i!=N:
    print(-1)
    exit()
    
  if x*2<=B[i]:
    x*=2
    ans+=x
  elif x>B[i]:
    print(-1)
    exit()
  else:
    x=B[i]
    ans+=x
  x-=A[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
p = list(map(int, input().split()))
sum_p = sum(p)-1
ans = 1
tmp = 1 - p[0]
if n==0 and p[0]==1:
    print(1)
    sys.exit()
elif n == 0:
    print(-1)
    sys.exit()

for i in range(n):
    if sum_p:
        if sum_p < tmp:
            tmp += sum_p
            sum_p = 0
        else:
            sum_p -= tmp
            tmp *= 2    
    ans += tmp
    tmp -= p[i+1]
    if tmp < 0 or (tmp==0 and i<n-1):
        print(-1)
        sys.exit()
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()
ma = [None]*n
ma[0] = 1
for i in range(n-1):
    ma[i+1] = (ma[i]-a[i])*2
node = a[-1]
ans = node
for i in range(n-1, -1, -1):
    mi = (node+1)//2
    if ma[i]-a[i]<mi:
        print(-1)
        exit()
    node = min(ma[i]-a[i], node) + a[i]
    ans += node
print(ans)

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    from itertools import islice
    cap = [1]
    for a in A:
        cap.append(2*(cap[-1]-a))
    ans = 0
    p = 0
    for a, c in zip(A[N::-1], cap[N::-1]):
        c -= a
        if 2 * c < p:
            return -1
        p = min(c, p) + a
        ans += p
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    cur = 1
    ret = 0
    t = []
    for i in range(N):
        v = A[i]
        if v >= cur:
            print(-1)
            return
        t.append(cur)
        ret += cur
        #print(i, cur, ret)
        cur = (cur - v) * 2
    if A[-1] > cur:
        print(-1)
        return
    ret += A[-1]
    #print(ret)

    mx = A[-1]
    for i in range(1, N)[::-1]:
        tmp = min(mx + A[i], 2 ** i)
        if t[i] > tmp:
            ret -= t[i] - tmp
        #ret += tmp
        mx = min(tmp, 2 ** (i - 1))
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
node=[1 for _ in range(N+1)]
Sn=sum(A)
S=[Sn]
for s in range(N):
    S.append(S[s]-A[s+1])

ans=1
for i in range(1,N+1):
    if node[i-1]*2<=S[i-1]:
        ans+=node[i-1]*2
        node[i]=node[i-1]*2
    elif node[i-1]<=S[i-1]<node[i-1]*2:
        node[i]=S[i-1]
        ans+=S[i-1]
    node[i]-=A[i]
    if node[i]<0:
        ans=-1
        break

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
alist = list(map(int, input().split()))
gokei=sum(alist)
nokori=gokei

if alist[0]!=0:
    if n==0 and alist[0]==1:
        print(1)
    else:
        print(-1)
else:
    oya=1
    answer=1
    ng=0
    for i in range(n-1):
        #print("choice", oya*2-alist[i+1], nokori-alist[i+1])
        if alist[i+1]>oya*2:
            ng=1
        oya=min(oya*2-alist[i+1], nokori-alist[i+1])
        answer+=oya
        answer+=alist[i+1]
        nokori-=alist[i+1]
        #print(nokori, answer, alist[i+2])
    
    if alist[-1]>oya*2:
        ng=1
        #print(alist[-1], oya)
    answer+=alist[-1]
    
    if ng==1:
        print(-1)
    else:
        print(answer)

Submission status: Accepted

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

ok = True

for i in range(n + 1):
    if r <= 0 or a[i] > r:
        ok = False
        break
    maxi[i] = r
    r = 2 * (r - a[i])

branches = a[n]
ans = a[n]
for i in range(n - 1, -1, -1):
    branches = min(branches + a[i], maxi[i])
    ans += branches

if not ok:
    ans = -1

print(ans)

Submission status: Accepted

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

next_max_node = 1

for leaf in a:
    if leaf > next_max_node:
        print(-1)
        exit()
    next_max_node = (next_max_node - leaf) * 2

num_sum = 0

for i in range(1, n+2):
    tmp = a[-i]
    b[-i] = a[-i] + num_sum
    num_sum += a[-i]

ret = 0
next_max_node = 1

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

print(ret)

Submission status: Accepted

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

#例外処理
if A[0] == 1:
  if N == 0:
    print("1")
  else:
    print("-1")
  quit()
elif A[0] > 1:
  print("-1")
  quit()
  
answer = 0
ans = [0] * (N + 1)
ans2 = [0] * (N + 1)
now = 1
ans[0] = 1
ans2[N] = A[-1]

for i in range(N):
  if now >= A[i]:
    now = 2 * (now - A[i])
    ans[i + 1] += now
  else:
    print("-1")
    quit()

if now < A[-1]:
  print("-1")
  quit()
  
for i in range(1, N + 1):
  ans2[N - i] = ans2[N - i + 1] + A[N - i]

for i in range(N + 1):
  answer += min(ans[i], ans2[i])
  
#print(ans)
#print(ans2)
print(answer)

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


leaf = []
miki = []
under = 1

for i, a in enumerate(A):
    if a > under:
        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: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
AA=[0]
for a in A[1:]:
    AA.append(AA[-1]+a)
f=1 if A[0]==0 or N==0 and A[0]==1 else 0
r=1
b=1
for i,a in enumerate(A[1:]):
    x=min(b*2,AA[-1]-AA[i])
    if i<N-1 and x>a or i==N-1 and x==a:
        b=x-a
        r+=x
    else:
        f=0
print(r if f else -1)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
flag = True
pos = [[1,1] for _ in range(n+2)]
for i in range(n+1):
    if pos[i][1] < a[i]:
        flag = False
    pos[i+1][0] = max(0,pos[i][0]-a[i])
    pos[i+1][1] = (pos[i][1]-a[i])*2
ans = a[n]
cur = a[n]
for i in range(n)[::-1]:
    cur = min(cur+a[i],pos[i][1])
    ans += cur
if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    av = list(map(int, input().split(' ')))
    cur = 1
    ans = 0
    s = sum(av)
    for i in range(n+1):
        if cur < av[i]: return -1
        ans += cur
        s -= av[i]
        cur -= av[i]
        if (s <= cur * 2):
            j = 1
            while i + j < n + 1:
                ans += j * av[i + j]
                j += 1
            break
        cur *= 2
    return ans

print(solve())

Submission status: Accepted

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))



N=int(input())
A=nl()

Hsum=sum(A)
Ntop=1
topnow=1

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

if(A[0]==1):
    if(N==0):
        print(1)
        sys.exit(0)
    else:
        print(-1)
        sys.exit(0)
    
for i in range(1,len(A)):
    if(topnow*2<=Hsum):
        topnow=topnow*2-A[i]
        if(topnow<0):
            print(-1)
            sys.exit(0)
        Hsum-=A[i]
        Ntop+=topnow+A[i]
    else:
        topnow=Hsum
        Ntop+=Hsum
        Hsum-=A[i]

print(Ntop)

Submission status: Accepted

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

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

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

for i in range(N+1):
    if A[i]>B[i]:
        check += 1
    D[i] = min(B[i],C[i])
    
if N==0:
    if A[0]!=1:
        check += 1

if check == 0:
    print(sum(D))
else:
    print("-1")

Submission status: Accepted

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


# whether we can make wood
m = [1]

flag = True

for i in range(n+1):
    if m[i] < a[i]:
        flag = False
        break
    elif i < n:
        m.append((m[i] - a[i]) * 2)

# count nodes

s = 0

if not flag:
    s = -1

else:
    u = 0

    for i in reversed(range(n+1)):
        s += min(a[i] + u, m[i])
        u += a[i]

print(s)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    x = 2 ** N
    c = 1

    past = [0]
    for i, a in enumerate(A):
        if a > c:
            print(-1)
            return
        elif a == 0:
            past.append(c)
            c *= 2
        else:
            past.append(c)
            c = (c - a) * 2

    ans = 0
    c = 0
    # print(*past)
    for i, p in enumerate(past[::-1]):
        if i == N + 1:
            continue
        ans += min(c + A[-1 -i], p)
        c += A[-i - 1]


    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    a = LI()
    ma = [None] * (n + 1)
    tmp = 0
    for i in range(n, -1, -1):
        x = pow(2, i)
        tmp += a[i]
        if tmp <= x:
            tmp = (tmp - 1) // 2 + 1
            continue
        else:
            print(-1)
            return
    ma[n] = a[-1]
    for i in range(n - 1, -1, -1):
        ma[i] = min(pow(2, i), ma[i + 1] + a[i])
    tmp = 1
    ans = 1
    for i in range(1, n + 1):
        tmp = tmp * 2
        ans += min(tmp, ma[i])
        tmp = min(tmp, ma[i])
        tmp -= a[i]
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

gen=0
for i in range(n):
    m=n-i-1
    gen+=a[m]
    nokori[m]=gen

kazu=[0]*n
kazu[0]=1
kano=True

for i in range(1,n):
    active=kazu[i-1]-a[i-1]
    if(active<=0):
        kano=False
        #print("だめ")
        break
    kazu[i]=min(active*2,nokori[i])

if(kazu[n-1]!=a[n-1]):
    kano=False

if(kano):
    print(sum(kazu))
else:
    print(-1)

Submission status: Accepted

Solution code:
def f(N, A):
    B = [0]*(N+1)
    b = 0
    for i in range(N, -1, -1):
        b += A[i]
        B[i] = b


    x = 1
    s = 0

    for i in range(N+1):
        x = min(x, B[i])
        s += x
        
        x = (x - A[i])*2
        if x < 0:
            return -1
        
    if x != 0:
        return -1

    return s


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
from itertools import accumulate

cAs = list(accumulate(As[::-1]))[::-1][1:] + [0]

ans = 0
now_nodes = 1
for i, (cum, a) in enumerate(zip(cAs, As)):
    if i==N:
        if now_nodes==a:
            print(ans+a)
        else:
            print(-1)
    if now_nodes<=a and i!=N:
        print(-1)
        break
    num = min(cum, (now_nodes-a)*2)
    ans += now_nodes
    now_nodes = num

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()

M = [tuple() for _ in range(N + 1)]
for i, a in enumerate(reversed(A)):
    i = N - i
    if i == N:
        M[i] = (a, a)
    else:
        n, m = M[i + 1]
        M[i] = (-(-n // 2) + a, m + a)

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

ans = 1
par = 1
for i in range(1, N + 1):
    least, most = par, par * 2
    minv, maxv = M[i]
    v = min(maxv, most)
    ans += v
    par = v - A[i]
print(ans)

Submission status: Accepted

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

    tot = sum(A)

    ans = 1
    tot -= 1
    v = 1
    for x in A:
        v -= x
        if v < 0:
            print(-1)
            return
        make_v = min(v, tot)
        tot -= make_v
        v += make_v
        ans += v

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().rstrip().split(" ")))
yuyo = [0] * (N + 1)
nokori = [0] * (N + 2)
A.append(0)
nokori[N + 1] = 0
ans = 0
for i in range(N,-1,-1):
    nokori[i] = nokori[i + 1] + A[i + 1]
ans = 0
if A[0] != 0:
    if A[0] == 1 and N == 0:
        ans = 1
    else:
        ans = -1
else:
    yuyo[0] = 1
    for i in range(1,N + 1):
        yuyo[i] = min(yuyo[i - 1] * 2 - A[i],nokori[i])
        if yuyo[i] < 0:
            ans = -1
            break
if ans == -1:
    print(-1)
else:
    for i in range(N):
        ans += yuyo[i]
    ans += nokori[0]
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0]+list(map(int, input().split()))
ans = 0
tree = []
presum = 0
for i, elt in enumerate(A[:0:-1]):
    presum += elt
    tree += presum,
vertices = []
last = .5
for i,elt in enumerate(tree[::-1]):
    last = min(2*(last-A[i]), elt)
    ans += int(last)
    if last <= 0:
        break
if last > 0 and last == A[-1]:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

count = 1
vertexCount = 0
rem = sum(num)
for m in num:
    vertexCount += count
    count -= m
    rem -= m
    if count < 0:
        vertexCount = -1
        break
    count = min(count*2, rem)

print(vertexCount)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations, accumulate
from bisect import bisect_left, bisect_right  # , insort_left, insort_right


# 根からなるべく早く分岐していたほうが有利 (だけど作りすぎるとダメ)
# 分岐できる最大値まで分岐させるのが良いのでは？
# 分岐できる最大値は？
#
# 累積和じゃね？

# 数は求められそうになった→存在しない場合はどういうとき？
# →その場で作ることのできる葉の数を越したとき

# 二倍二倍でシミュレーション化(必要な数を超えては行けない)


N = read_a_int()
A = read_ints()

# i番目以下に必要な葉の数
n_leaves_under = list(reversed(list(accumulate(reversed(A))))) + [0]

# 頂点数をシミュレーションしていく
# 頂点数はn_leaves_underを超えては行けない
# なるべく葉の数を引いてからなるべく2倍にするほうが良い
# A[i]が現在作れる葉の数よりも大きかったら強制終了

now = 1  # 頂点の数
ans = 0
for i in range(N + 1):
    # print(now, n_leaves_under[i + 1])
    if A[i] > now:
        print(-1)
        exit()
    ans += now
    now -= A[i]
    now = min(now * 2, n_leaves_under[i + 1])

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
def pow2(a):
    return 1<<min(a, 63)
ans = 0
Cap = []
c = 1
for d, a in enumerate(A):
    Cap.append(c)
    c -= a
    if c < 0:
        print(-1)
        exit()
    c *= 2
    if c >= 1<<63:
        c = 1<<63
siz = 0
#print(Cap)
for d, a, cap in zip(range(N, -1, -1), A[::-1], Cap[::-1]):
    #print(d, a, cap)
    siz = min(siz+a, cap)
    ans += siz
    #print(siz)
print(ans)