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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve(N, As):
    if N == 0:
        if As[0] == 1:
            return 1
        else:
            return -1

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

    depth = N
    mx = 2 ** depth
    prev_leaf = None

    leaf_sum = sum(As)

    ans = 0
    curr = 0
    Vs = [None] * (N + 1)
    for n in range(N + 1):
        if n == 0:
            curr = 1
            ans += 1
        else:
            # 頂点を増やせるだけ増やす
            curr2 = min(curr * 2, leaf_sum)
            # 矛盾したら終わり
            if curr2 < As[n]:
                return -1
            # 頂点全部足す
            ans += curr2
            # 次に残れる頂点
            curr = curr2 - As[n]
            # 使った葉のぶんを引く
            leaf_sum -= As[n]

    return ans


def main():
    N = int(input())
    As = list(map(int, input().split()))
    print(solve(N, As))

    
main()

Submission status: Accepted

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

    flag = True

    edge = 1
    edges = []
    for i, a in enumerate(A):
        edge -= a
        edges.append(edge)
        if edge <= 0 and i < N - 1 or edge < 0:
            flag = False
            break
        edge *= 2
    
    if not flag:
        print(-1)
        exit()

    leaves = A[-1]
    ans = A[-1]
    for i in range(N-1, -1, -1):
        if leaves > edges[i]:
            leaves = edges[i]

        ans += A[i] + leaves
        leaves += A[i]
    print(ans)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()

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

num = 1
M = [0] * (N+1)
for i in range(N+1):
	M[i] = num
	if A[i] > num:
		print(-1)
		exit()
	num = (num - A[i]) * 2
ans = sum(A)

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
H = [0]*(n+1)
s = sum(A)
flag= True
if n==0:
    if A[0] ==1:
        print(1)
    else:
        print(-1)
else:
    if A[0]>= 1:
        print(-1)
        flag = False
    else:
            H[0] =1
            i = 1
            while i <=n:
                if A[i] > H[i-1]*2:
                    print(-1)
                    flag =False
                    break
                else:
                    if s >=2*(H[i-1]-A[i-1]):
                        H[i] = 2*(H[i-1]-A[i-1])
                    else:
                        H[i] = s
            
                    s -= A[i]
                    i +=1
    if flag:
        print(sum(H))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
inf = 10**18
res = 0
b = [0]*(N+1)
b[0] = 1-a[0]
for i in range(N):
    tmp = min(2*b[i] - a[i+1], inf)
    if tmp < 0:
        res = -1
        break
    b[i+1] = tmp

if res != -1:
    tmp = 0
    for i in range(N,0,-1):
        tmp += a[i]
        if 2*b[i-1] < tmp:
            tmp = 2*b[i-1]
        res += tmp
    res += 1
if N==0 and a[0]>1:
    res = -1
print(res)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
if N==0:
  if A[0]==1:
    print(1)
    exit()
  else:
    print(-1)
    exit()

D=[0]*(N+1)
D[0]=1
goal=sum(A)
goal-=A[0]
D[0]-=A[0]
for i in range(N):
  ma=D[i]*2
  if ma<A[i+1]:
    print(-1)
    exit()
  else:
    if D[i]<=goal<=2*D[i]:
      D[i+1]=goal
    else:
      D[i+1]=D[i]*2
    D[i+1]-=A[i+1]
    if D[i+1]<0:
      print(-1)
      exit()
    goal-=A[i+1]
print(sum(D)+sum(A))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
b=[None for i in range(n)]
if n==0:
    if a[0]==1:
        print(1)
    else:
        print(-1)
else:
    a.reverse()
    for i in range(n):
        b[i]=(a[i]+1)//2
        a[i+1]+=b[i]
    if a[-1]>1:
        print(-1)
    else:
        a.reverse()
        b.reverse()
        b.append(0)
        res=a[n]
        ma=[100000000000000000000 for i in range(n+1)]
        ma[0]=1
        for i in range(1,n+1):
            ma[i]=min((ma[i-1]-a[i-1]+b[i-1])*2,ma[i])
        for i in range(n-1,-1,-1):
            a[i]=min(ma[i],a[i+1]+a[i]-b[i])
            res+=a[i]
        print(res)

Submission status: Accepted

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

if A[0]>=2:
  print(-1)
  
elif A[0]==1:
  if N!=0:
    print(-1)
  else:
    print(1)
    
else:
  SA = sum(A)
  ans = 1
  parent = 1
  judge = True
  for i in range(1, N+1):
    num_leaf = A[i-1]
    num_child = 2*(parent - num_leaf)
    SA -= num_leaf
    if (num_child<A[i])or(num_child<1):
      judge = False
      break
      
    if num_child<=SA:
      parent = num_child
      ans += num_child
      
    else:
      parent = SA
      ans += SA

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

Submission status: Accepted

Solution code:

n=int(input())
A=list(map(int,input().split()))
flag=True
check=True
cnt=sum(A)-1
f=1
ans=1
dis=0
for i in range(n+1):
    if A[i]<=f:
        dis+=A[i]*(n-i)
        if check:
            if cnt==0:
                ans+=n
                check=False
            elif cnt>f-A[i]:
                ans+=(f-A[i])*(n-i)
                cnt=cnt-(f-A[i])
            else:
                ans+=cnt*(n-i)
                cnt=0
        f=2*(f-A[i])
    else :
        flag=False
        break
if not flag:
    print(-1)
else:
    print(ans-dis)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N == 0 and A[0] == 1:
        print(1)
        return
    if N == 0:
        print(-1)
        return
    if A[0] != 0:
        print(-1)
        return
    
    # 下から全く連結なしに子から枝を伸ばしたとして、部分木の個数を確認
    B = [0] * (N + 1)
    B[-1] = A[-1]
    for i in range(N - 1, -1, -1):
        B[i] = B[i + 1] + A[i]
    
    # 次に根から順にみてうまくつなぎ合わせ
    vertex = 1
    root = 1
    for i in range(1, N):
        if root * 2 - 1 < A[i]:
            print(-1)
            return
        if root < A[i]:
            root = min(B[i + 1], root * 2 - A[i])
            vertex += A[i] + root
        else:
            root = min(B[i + 1], root * 2 - A[i])
            vertex += A[i] + root
    
    # 最後N段目でつじつま合うか確認
    if root * 2 < A[-1]:
        print(-1)
        return
    vertex += A[-1]
    print(vertex)
    





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
ans=0
store=1
leaves=sum(a)
for i in range(n+1):
  if a[i]>store:
    ans=-1
    break
  node=min(store,leaves)
  ans+=node
  leaves-=a[i]
  store-=a[i]
  store*=2
print(ans)

Submission status: Accepted

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

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

sum_ue = [1]
sum_shita = [A[N]]

for i in range(N):
    sum_ue.append((sum_ue[i] - A[i]) * 2)
    sum_shita.append(sum_shita[i] + A[N - 1 - i])

sum_shita.reverse()
# print(sum_ue)
# print(sum_shita)

ans = 0

for i in range(N + 1):
    if i == N:
        if sum_ue[i] < A[i]:
            print(-1)
            exit()
    else:
        if sum_ue[i] <= A[i]:
            print(-1)
            exit()

for i in range(N + 1):
    ans += min(sum_ue[i], sum_shita[i])

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l = [int(x) for x in input().split()]
ans = 1
wa = sum(l)
kosuu = 1 - l[0]
flag = 0
if N == 0:
    if l[0] == 1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
for i in range(1,N):
    if  flag == 0:
        kosuu = kosuu * 2
    if kosuu >= wa:
        flag = 1
        kosuu = wa
    ans += kosuu
    kosuu = kosuu - l[i]
    wa = wa-l[i]
    if kosuu <= 0:
        print(-1)
        exit()
if kosuu*2 < l[N]:
    print(-1)
else:
    print(ans+l[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

def main():
    N = int(input())
    A = list(map(int, input().split()))
    accumA = list(accumulate(A[::-1]))[::-1]
    ans = 1
    ne = [0] * (N+1)
    ne[0] = 1

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


    for i in range(1,N+1):
        if i == N:# 最後の深さ
            if ne[i-1] > A[i] or ne[i-1] * 2 < A[i]:
                print(-1)
                exit()
            else:
                ans += A[i]
        else:
            tmp_ne = min(ne[i-1]*2 - A[i], accumA[i+1])
            if tmp_ne < 0:
                print(-1)
                exit()
            else:
                ne[i] = tmp_ne
                ans += tmp_ne + A[i]
    print(ans)
    # print(ne,accumA)


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)
else:
    req = [0] * n
    req[-1] = a[-1]
    for i in range(2, n+1):
        req[-i] = req[-(i-1)] + a[-i]
    l = [0] * (n + 1)
    l[0] = 1
    for i in range(1, n+1):
        M = (l[i-1] - a[i-1]) * 2
        l[i] = min(M, req[i-1])
    if l[-1] < a[-1]:
        print(-1)
    else:
        print(sum(l))

Submission status: Accepted

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

# if a_l[0] != 0:
#     if n == 0:
#         print(1)
#     else:
#         print(-1)
#     exit()

tree = [0]*(n+1)
tree[0] = 1
for i in range(1,n+1):
    tree[i] = (tree[i-1] - a_l[i-1]) * 2
# print(tree)

if tree[-1] < a_l[-1]:
    print(-1)
    exit()

# print(tree)
tree[-1] = a_l[-1]
for i in range(2,n+2):
    # print(i, tree[-i], tree[-(i-1)] + a_l[-i])
    if tree[-i] == tree[-(i-1)] + a_l[-i]:
        break
    else:
        tree[-i] = min(tree[-i], tree[-(i-1)] + a_l[-i])
    # print(tree)
# print(tree)

# while tree[-1] != a_l[-1]:
#     tree[-1] -= 1
#     i = 1
#     while True:
#         i += 1 
#         if tree[-(i-1)] >= (tree[-i] - a_l[-i]):
#             break
#         tree[-i] -= 1
# print(tree)

ans = 0
for val in tree:
    ans += val
print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
a = sum(A)

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

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

B = [0]*(N+1)  #深さiの頂点数のmax
B[0] = 1

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

ans = A[N]

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

print(ans)

Submission status: Accepted

Solution code:
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
N += 1

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

# # TODO: 繰り返しをなくす
# def test():
#     d = 0
#     ok = True
#     for i in range(N):
#         for _ in range(A[i]):
#             # i より前で cap が 0 以上で一番前のところから取る
#             if d > i:
#                 ok = False
#                 break
#             cap[d] -= 1
#             cap[d + 1:i] += 1
#             counts[d + 1: i + 1] += 1
#             while d < len(cap) and d < 70 and cap[d] <= 0:
#                 d += 1
#         print(counts, cap, d, ok)
#     print(counts.sum())
#     return counts.sum()


# cap = np.ones(N, dtype=int)
# cap[-1] = 0
# # counts = [1] * N
# counts = np.ones(N, dtype=int)


bit = BinaryIndexedTree(size=N + 10)
bit.add(0, 1)
bit.add(N - 1, -1)
A[-1] -= 1

d = 0
ok = True
ans = N
for i in range(N):
    while A[i] > 0:
        # i より前で cap が 0 以上で一番前のところから取る
        if d >= i:
            ok = False
            break
        # a = min(A[i], cap[d])
        a = min(A[i], bit.sum(d + 1))
        A[i] -= a

        # cap[d] -= a
        bit.add(d, -a)
        bit.add(d + 1, a)
        # cap[d + 1:i] += a
        bit.add(d + 1, a)
        bit.add(i, -a)

        # counts[d + 1: i + 1] += a
        ans += a * (i - d)
        while d < N and bit.sum(d + 1) <= 0:
            d += 1

    if not ok:
        break
    # for i in range(len(bit)):
    #     print(bit.sum(i + 1), end=' ')
    # print()
    # print(counts, cap, d, ok)
    # print()
if ok:
    print(ans)
else:
    print(-1)
exit()
# print(counts.sum(), ans)
# test()

Submission status: Accepted

Solution code:
n=int(input())
a=[int(j)for j in input().split()]
ans=0
s=sum(a)
p=1
b=True
for i,j in enumerate(a):
    if p<j:
        print(-1)
        exit()
    ans+=p
    p-=j
    s-=j
    if i==n:
        continue
    if p<s and b:
        if p*2<s:
            p*=2
        else:
            p=s
    if p==s:
        b=False
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a2 = [0] * (n + 1)
d = [1] * (n + 1)
ans = 1
a2[0] = sum(a)
for i in range(n):
    a2[i + 1] = a2[i] - a[i + 1]
for i in range(n):
    if d[i] - a[i] <= 0:
        ans = -1000000000000
    if (d[i] - a[i]) * 2 >= a2[i]:
        d[i + 1] = a2[i]
    else:
        d[i + 1] = (d[i] - a[i]) * 2

if ans < 0:
    ans = -1
elif d[n] != a[n]:
    ans = -1
else:
    ans = sum(d)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(j)for j in input().split()]
ans=0
s=sum(a)
p=1
b=True
for i,j in enumerate(a):
    if p<j:
        print(-1)
        exit()
    ans+=p
    p-=j
    s-=j
    if i==n:
        continue
    if p<s and b:
        if p*2<s:
            p*=2
        else:
            p=s
    if p==s:
        b=False

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
v = list(map(int, input().split()))
u = [1]*(n+1)
a = 0
b = False
tmp = 0
tt = 0
for i in range(n+1):
  if u[i] < v[i]:
    b = True
    break
  if i < n:
    u[i+1] = (u[i] - v[i])*2
for i in range(n, -1, -1):
  tt += v[i]
  tmp = min(tt, u[i])
  a += tmp
  tt = tmp
if n == 0:
  a = v[0]
if b:
  a = -1
print(a)

Submission status: Accepted

Solution code:
def main(N, A):
    num = 1
    ans = 1
    for i in range(N+1):
        num -= A[i]
        if i < N:
            num *= 2
            ans += num
        if num == 0 and i < N:
            return -1
        if num < 0:
            return -1
    eda = 0
    for i in range(N+1):
        ans -= num
        eda += A[N-i]
        num -= eda
        num = num//2
        if num <= 0:
            break
    return ans


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

print(main(N, A))

Submission status: Accepted

Solution code:
def main():
    N = int( input())
    A = list( map( int, input().split()))
    root = 1
    if A[0] == 1:
        if N == 0:
            print(1)
        else:
            print(-1)
        return
    B = A[::-1]
    low = high = B[0]
    # Low = []
    Hight = [high]
    Low = [low]
    for b in B[1:]:
        low = max(1, (low+1)//2) + b
        high = high + b
        Hight.append(high)
        Low.append(low)
    if low > 1:
        print(-1)
        return
    ans = 1
    now = 1
    BHight = Hight[::-1]
    BLow = Low[::-1]
    for i in range(1,N+1):
        high = BHight[i]
        low = BLow[i]
        if high < now or now*2 < low:
            print(-1)
            return
        leaf = A[i]
        now = min(high, now*2)
        ans += now
        now -= leaf
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())+1
ali = list(map(int,input().split()))
nli = [0]*N

maxn = 2**(N-1)
nli[-1] = ali[-1]

for i in range(1,N+1):
  nli[-i] = min(maxn,nli[-i+1] + ali[-i])
  maxn //= 2
  

ulim = 1
for i in range(N):
  nli[i] = min(nli[i],ulim)
  ulim = (ulim - ali[i])*2
  if ulim < 0:
    print(-1)
    exit()
  
print(sum(nli))

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    if n == 0 and a[0] == 0:
        print(-1)
        exit()
    elif n == 0 and a[0] == 1:
        print(1)
        exit()
    elif n == 0 and a[0] > 1:
        print(-1)
        exit()
    suma = sum(a)
    ans = a[0]
    can = 1
    for i,ai in enumerate(a):
        if ai > can:
            print(-1)
            exit()
        suma -= ai
        ans += can
        if (can-ai)*2 >= suma:
            can = suma
        else:
            can = (can-ai)*2

    print(ans)




    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

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

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

for i in range(n):
    here = a[1+i]
    possible = num[i][0]*2
    num[i+1] = [possible-here,here]
    
#print(num)

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

num[-1][0] = 0

for i in range(n-1,-1,-1):
    if(num[i+1][0]+num[i+1][1]<num[i][0]):
        num[i][0] = num[i+1][0]+num[i+1][1]

#print(num)

if(num[n][0]>=1):
    print(-1)
    exit()

for i in range(n):
    if(num[i][0]<=0):
        print(-1)
        exit()

s = sum([sum(num[i]) for i in range(n+1)])
print(s)

Submission status: Accepted

Solution code:
from collections import deque
import sys


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


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

ans, nd = 0, 0
lim = [1 for _ in range(N + 2)]
for i in range(N):
    lim[i+1] = (lim[i] - v[i]) * 2

for i in range(N, -1, -1):
    if v[i] + nd > lim[i] * 2 or lim[i] - v[i] < 0:
        print(-1)
        sys.exit(0)
    if v[i] + nd > lim[i]:
        nd = lim[i] - v[i]

    nd += v[i]
    ans += nd

print(ans)

Submission status: Accepted

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:

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

s=0
cap=[]
flag=False
ans=2**(n+1)-1
for i,a in enumerate(A):
    s*=2
    s+=a
    cap.append(2**i-s)
    #if i!=n:
    #    ans-=a*(2**(n+1-i)-2)
    if s>2**i:
        flag=True
        break

if flag:
    print(-1)
else:
    remain=2**n-s
    ans=0
    node=0
    for i in range(n,-1,-1):
        a=A[i]
        c=cap[i]
        node=min(c,node)+a
        ans+=node
    print(ans)

Submission status: Accepted

Solution code:
import sys
msg = sys.stdin.readlines()
n = int(msg[0])
a = list(map(int,msg[1].split()))
tot = 0
b = [0 for i in range(n+1)]
for i in range(n+1):
  b[i] = (1<<i)-2*tot;
  tot = 2*tot+a[i];
  if tot > (1<<i):
    print(-1)
    exit(0)
nb = 0
crt = 0;
for i in range(n,-1,-1):
  crt = min(crt+a[i],b[i])
  nb += crt;
print(nb)

Submission status: Accepted

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

if N==0:
    A0 = A[0]
    if A0 == 1:
        print(1)
    else:
        print(-1)
else:
    max_forward = [1]
    now = 1
    flag = 0
    for i in range(N):
        now = (now - A[i])*2
        if now <= 0:
            flag = -1
            break
        max_forward.append(now)
    
    max_backward = [A[-1]]
    now = A[-1]
    for i in range(N):
        ind = N-i-1
        now = now + A[ind]
        max_backward.append(now)
    
    if flag == -1:
        print(-1)
    else:
        if max_forward[-1] < A[-1]:
            print(-1)
        else:
            ans = 0
            for i in range(N+1):
                temp = min(max_forward[i], max_backward[N-i])
                #print(temp)
                ans += temp
            print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))
n=n_in()
A=l_in()

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[0] = 1

upper = max(A)

S=[0]*(n+1)
S[0] = A[0]

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



for i in range(1, n):
    B[i] = min(B[i-1]*2-A[i], S[n]-S[i])
    if B[i] <= 0:
        print(-1)
        exit()

if A[n] > B[n-1]*2:
    print(-1)
    exit()
        
print(sum(A)+sum(B))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = 10**9


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

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

    # 利用可能頂点をメモ
    available = [0]*(N+1)
    available[0] = 1
    for i in range(1, N+1):
        available[i] = available[i-1]*2-A[i]
    # print(available)

    ans = 0
    # 後ろから見ていく
    for i in range(N, 0, -1):
        # print(A[i])
        if A[i] <= available[i-1]:
            # 独立型
            ans += A[i]
            A[i-1] += A[i]
        elif A[i] <= 2*available[i-1]:
            ans += A[i]
            A[i-1] += available[i-1]
        else:
            print(-1)
            return
    print(ans+1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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


imsi=0   
for i in range(n+1):
    imsi+=l[i]*power[n-i]


if(imsi<=power[n]):
    sum=0
    for i in range(n+1):
        sum+=l[i]
    yuksum=[sum]
    for i in range(n+1):
        yuksum.append(yuksum[-1]-l[i])

    x=1
    parent=1
    for i in range(n+1):
        if i==0:
            pass
        else:
            if (2*parent-l[i])>yuksum[i+1]:
                x+=yuksum[i+1]+l[i]
                parent=yuksum[i+1]
            else:
                x+=2*parent
                parent=2*parent-l[i]
    print(x)
else:
    print("-1")

Submission status: Accepted

Solution code:
n,*a = map(int,open(0).read().split())
pm = sum(a)
e = 1
te = 1
for i in a:
  pm -= i
  e = min((e-i)*2,pm)
  te += e
  if e < 0:
    break
if e < 0:
  print(-1)
else:
  print(te)

Submission status: Accepted

Solution code:

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


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


dsum = 0
d = 0
ok = True
for i in range(len(A) - 1, -1, -1):
    min_d = ((d + 1) // 2 if d % 2 else d // 2) + A[i]
    max_d = d + A[i]
    if min_d > M[i]:
        ok = False
        break
    d = min(M[i], max_d)
    dsum += d

print(dsum if ok else -1)

Submission status: Accepted

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

flag=True
dp = [[0,0] for _ in range(n+1)]
if a[0]==0:
    dp[0]=[0,1]
    if n==0:
        flag=False
elif a[0]==1:
    dp[0]=[1,0]
else:
    flag=False
for i in range(1,n+1):
    free = dp[i-1][1]*2
    occu = a[i]
    if free-occu<0:
        flag=False
        break
    else:
        free-=occu
    dp[i]=[occu,free]
dp[n][1]=0
ans=0
ch=1001001001
for i in reversed(range(n+1)):
    free=min(ch,dp[i][1])
    ch=dp[i][0]+free
    ans+=dp[i][0]+free

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

Submission status: Accepted

Solution code:
import os
from collections import defaultdict

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

pow2 = defaultdict(int)

ret = 0
lim = [0] * (N + 1)
# for i in range(N + 1):
#     pow2[i] = 2 ** i

for i in range(N + 1):
    if i == 0:
        r = 1 - A[i]
    else:
        r = 2 * lim[i - 1] - A[i]
    if r < 0:
        print(-1)
        exit(0)
    lim[i] = r

for d in reversed(range(N + 1)):
    # if A[d] > pow2[d]:
    #     print(-1)
    #     exit(0)
    if d == N:
        #n = min(A[d], pow2[d])
        n = A[d]
    else:
        #n = min(A[d] + min(n, lim[d]), pow2[d])
        n = A[d] + min(n, lim[d])
    ret += n

print(ret)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()

if len(A) == 1:
  if A == [1]:
    print(1)
    exit()
  else:
    print(-1)
    exit()
ans = [1]

for a in A[1:]:
  pmax = ans[-1]
  if a > pmax*2:
    print(-1)
    exit()
  else:
    pmax = pmax*2-a
    ans.append(pmax)

final_ans = []
prev = 0
for i in range(N+1):
  pmax = ans[N-i]
  final_ans.append(min(pmax,prev)+A[N-i])
  prev = final_ans[-1]

if final_ans[-1] != 1:
  print(-1)
  exit()
  
print(sum(final_ans))