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: Time Limit Exceeded

Solution code:
from math import ceil

def a():
    N = int(input())
    A = list(map(int,input().split()))
    INF = 10**13
    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    BMAX = [INF] * (N+1)
    BMIN = [1] * (N+1)

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

    for i in range(N-1,-1,-1):
        BMAX[i] = min(BMAX[i],BMAX[i+1]+A[i+1])
        BMIN[i] = max(BMIN[i],ceil((BMIN[i+1]+A[i+1])/2))

    for i in range(1,N+1):
        BMAX[i] = min(BMAX[i],BMAX[i-1]*2-A[i])
        BMIN[i] = max(BMIN[i],BMIN[i-1]-A[i])

    ans = 0
    for i in range(0,N+1):
        if BMIN[i] > BMAX[i]:
            return -1
        ans += (BMAX[i] + A[i])
    return ans

print(a())

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

def a():
    N = int(input())
    A = list(map(int,input().split()))
    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    BMAX = [10**13] * (N+1)
    BMIN = [1] * (N+1)

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

    for i in range(N-1,-1,-1):
        BMAX[i] = min(BMAX[i],BMAX[i+1]+A[i+1])
        BMIN[i] = max(BMIN[i],ceil((BMIN[i+1]+A[i+1])/2))

    for i in range(1,N+1):
        BMAX[i] = min(BMAX[i],BMAX[i-1]*2-A[i])
        BMIN[i] = max(BMIN[i],BMIN[i-1]-A[i])

    ans = 0
    for i in range(0,N+1):
        if BMIN[i] > BMAX[i]:
            return -1
        ans += (BMAX[i] + A[i])
    return ans

print(a())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
leafNodesPerLevel = [int(s) for s in input().split()]


def checkBinaryTree(N, leafNodesPerLevel):
    maxNodePerLevel = [0 for _ in range(N+1)]
    remainingNode = 1
    for depth in range(N+1):
        if remainingNode < leafNodesPerLevel[depth]:
            print(-1)
            return
        maxNodePerLevel[depth] = remainingNode
        remainingNode = 2 * (remainingNode - leafNodesPerLevel[depth])

    lastLevelNode = leafNodesPerLevel[-1]
    total_node = lastLevelNode
    for depth in range(N, 0, -1):
        num = min(maxNodePerLevel[depth] // 2, lastLevelNode) + leafNodesPerLevel[depth-1]
        total_node += num
        lastLevelNode = num
    print(total_node)


checkBinaryTree(N, leafNodesPerLevel)

Submission status: Time Limit Exceeded

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


N = INT()
A = LIST()

init_nodes = [0]*(N+1)
stems = [0]*(N+1)
init_nodes[0] = 1
stems[0] = 1


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

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


    for i in range(N+1):
        if A[i] > 2**i:
            return -1


    for i in range(1, N+1):
        init_nodes[i] = 2 * stems[i-1]
        stems[i] = init_nodes[i] - A[i]
        if stems[i] < 0: return -1

    ans = sum(init_nodes)

    dif = init_nodes[-1] - A[-1]
    ans -= dif
    for i in reversed(range(N+1)):
        if init_nodes[i] - dif < 0: return -1
        dif = (dif-(init_nodes[i] - dif))//2
        if dif <= 0: break
        ans -= dif
    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

N = int(input())
A = list(input().split())
A = [int(A[i]) for i in range(N+1)]
MAX = [2**i for i in range(N+1)]
A_inter = list(reversed(list(itertools.accumulate(reversed(A)))))

for i in range(N+1):
    if A[i] > MAX[i]:
        print(-1)
        sys.exit()
    elif i != N:
        MAX[i+1] = (MAX[i] - A[i]) * 2
        
for i in reversed(range(N+1)):
    MAX[i] = min(MAX[i], A_inter[i])

print(sum(MAX))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import bisect
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
limit = [0] * (n + 1)
total = 0
for i in range(n, -1, -1):
    total += A[i]
    limit[i] = total
#print(limit)

for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    #print("mov_dic", mov_dic)

    dp = dd(int)
    mov_dic_keys = set(mov_dic.keys())
    for now_num, total in mov_dic.items():
        mov_dic_keys.remove(now_num)
        for next_num in range(now_num, min(now_num*2 + 1, limit[depth] + 1)):
            if now_num in mov_dic_keys:
                break
            dp[next_num] = max(total + next_num, dp[next_num])
    #print(limit[depth], "dp", dp)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

pos = [pow(2, i) - a[i] for i in range(n+1)]
for i in range(n):
    pos[i+1] = pos[i] * 2 - a[i+1]

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

cnt = a[-1]
memo = 0
for i in range(n-1, -1, -1):
    cnt += min(pos[i], memo + a[i+1]) + a[i]
    memo = min(pos[i], memo + a[i+1])


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
limit = [0] * (n + 1)
total = 0
for i in range(n, -1, -1):
    total += A[i]
    limit[i] = total
#print(limit)

for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    #print("mov_dic", mov_dic)

    dp = dd(int)
    for now_num, total in mov_dic.items():
        for next_num in range(now_num, min(now_num*2 + 1, limit[depth] + 1)):
            dp[next_num] = max(total + next_num, dp[next_num])
    #print(limit[depth], "dp", dp)

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

Submission status: Time Limit Exceeded

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

pos = [pow(2, i) - a[i] for i in range(n+1)]
for i in range(n):
    pos[i+1] = pos[i] * 2 - a[i+1]

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

cnt = a[-1]
memo = 0
for i in range(n-1, -1, -1):
    cnt += min(pos[i], memo + a[i+1]) + a[i]
    memo = min(pos[i], memo + a[i+1])


print(cnt)

Submission status: Time Limit Exceeded

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

ans = N + 1
B = [1] * (N + 1)
B[N] = 0
A[N] -= 1


zero = -1

for i in range(0, N + 1):
    if A[i] > 0:
        C = [0] * (N + 1)
        for j in range(zero + 1, i):
            B[j] += C[j]
            if B[j] > 0:
                h = min(A[i], B[j])
                B[j] -= h
                A[i] -= h
                C[j] += h
                ans += h * (i - j)
                if B[j] == 0:
                    zero = j
            C[j + 1] += C[j]
        if A[i] > 0:
            print(-1)
            exit()
print(ans)

Submission status: Time Limit Exceeded

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


def solve(N: int, A: "List[int]"):
    if N==0:
        if A[0] == 1:
            print(1)
        else:
            print(-1) 
        return 
    
    prev = 0
    leafs = 0
    ans = 0
    for i, a in enumerate(A):
        leafs = leafs*2 + a
        rem = pow(2,i) - leafs
        k = min(rem,sum(A[i+1:]))
        # print(A[i+1:])
        # print(k)
        ans+=k
    # print(leafs)

    rem = pow(2,N) - leafs
    
    if rem<0:
        print(-1)
        return
    print(ans+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

Solution code:
from math import ceil

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ns = [(a[-1], n, 0)]
    nd = set()
    while ns:
        v, i, c = ns.pop()
        if (v, i) in nd:
            continue
        if i == 0:
            if v == 1:
                print(c + v)
                break
            else:
                continue
        nd.add((v, i))
        ns += [(vi + a[i - 1], i - 1, c + v) for vi in range(ceil(v / 2), min(v, 2**(i - 1) - a[i - 1]) + 1)]
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    #print("mov_dic", mov_dic)

    dp = dd(int)
    for now_num, total in mov_dic.items():
        for next_num in range(now_num, now_num*2 + 1):
            dp[next_num] = max(total + next_num, dp[next_num])
    #print("dp", dp)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ns = [(a[-1], n, 0)]
    nd = set()
    while ns:
        v, i, c = ns.pop()
        if (v, i) in nd:
            continue
        if i == 0:
            if v == 1:
                print(c + v)
                break
            else:
                continue
        nd.add((v, i))
        for vi in range(ceil(v / 2), min(v, 2**(i - 1)) + 1):
            ns.append((vi + a[i - 1], i - 1, c + v))
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 d < 70 and bit.sum(d + 1) <= 0:
            d += 1

    # 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: Time Limit Exceeded

Solution code:
import os
from collections import defaultdict
N = int(input())
A = list(map(int, input().split(" ")))

pow2 = defaultdict(int)

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


for i in range(N+1):
    if i == 0:
        r = 2**i - A[i]
    else:
        r = 2*lim[i-1] - A[i]
    if r < 0:
        print(-1)
        exit(0)
    lim.append(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])
    else:
        n = min(A[d] + min(n, lim[d]), pow2[d])
    ret +=n

print(ret)

Submission status: Time Limit Exceeded

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

is_possible = True
for i in range(n):
    if a[i] > 2**i - 1:
        is_possible = False
        break
if a[n] > 2**n:
    is_possible = False

s = 0
for i in range(n + 1):
    s += a[i] * (2**(n - i))
if s > 2**n:
    is_possible = False

b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = (a[i] + b[i]) * 2

c = [0] * (n + 1)
c[n] = a[n]
ans = a[n]
for i in reversed(range(n)):
    if (c[i + 1] + 1) // 2 + a[i] + b[i] > 2**i:
        is_possible = False
        break
    c[i] = min(c[i + 1], 2**i - a[i] - b[i]) + a[i]
    ans += c[i]

# print(a)
# print(b)
# print(c)

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

Submission status: Time Limit Exceeded

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

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

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


print(ret)

Submission status: Time Limit Exceeded

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

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

if not_in[N] > 2 ** N:
  print(-1)
else:
  in_num = 0
  up = A[N]
  for i in range(N-1,-1,-1):
    in_temp = min(2 ** i - not_in[i], up)
    in_num += in_temp
    up = in_temp + A[i]
  print( in_num + sum(A) )

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    if n == 0:
        if a[0] == 1:
            print(1)
        else:
            print(-1)
        return
    if a[0] == 1:
        print(-1)
        return
    k = [(1<<i)-a[i] for i in range(n+1)]
    M = [1<<i for i in range(n+1)]
    for i in range(n):
        if k[i] <= 0:
            print(-1)
            return
        M[i+1] = min(M[i+1],k[i] << 1)
        k[i+1] = M[i+1] - a[i+1]
    if k[n] < 0:
        print(-1)
        return
    s = a[-1]
    ans = s
    for i in range(n)[::-1]:
        s = min(M[i],s+a[i])
        ans += s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

ans = 0
can = 1
for a in A:
    if can < a:
        print(-1)
        exit(0)
    else:
        can -= a
        can *= 2
can //= 2
can += A[-1]
real = A[-1]
for i in range(n-1,-1,-1):
    ans += real
    real = min(real,can//2)
    real += A[i]
    can //= 2
    can += A[i]
print(ans + 1)

Submission status: Memory Limit Exceeded

Solution code:
# 深さdの上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))

# 深さdのノード数の上限
limit = [1]
for i in range(1, N+1):
    if i == N:  # 一番深いところの上限はA[N]
        limit.append(A[i])
    else:
        limit.append((limit[-1]-A[i-1])*2)

# Nが0の時の処理
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()

# 一番深いところから構築して最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]  # 一番深いところから構築しており，今現在の葉の数
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]
# 構築したものに対してジャッジする, 葉を確保できているかどうか
for i in range(N):
    # ans[N-i]とすることで，今は一番浅いところから見ている
    if (ans[N-i]-A[i])*2 < A[i+1]:  # 葉が確保できているか
        print(-1)
        exit()
print(sum(ans))

Submission status: Memory Limit Exceeded

Solution code:
# 深さdの上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))
 
# 深さdのノード数の上限
limit = [1]
for i in range(1, N+1):
    if i == N:  # 一番深いところの上限はA[N]
        limit.append(A[i])
    else:
        limit.append((limit[-1]-A[i-1])*2)
 
# Nが0の時の処理
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()
 
# 一番深いところから構築して最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]  # 一番深いところから構築しており，今現在の葉の数
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]
# 構築したものに対してジャッジする, 葉を確保できているかどうか
for i in range(N):
    # ans[N-i]とすることで，今は一番浅いところから見ている
    if (ans[N-i]-A[i])*2 < A[i+1]:  # 葉が確保できているか
        print(-1)
        exit()
print(sum(ans))

Submission status: Memory Limit Exceeded

Solution code:
import sys

n = int(input())
a = list(map(int, input().split()))
if n == 0:
    if a[0] == 1:
        print(1)
    else:
        print(-1)
    sys.exit(0)

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

ans = 0
chi = a[n]
for i in reversed(range(n)):
    if pa[i]*2 < chi:
        print(-1)
        sys.exit(0)
    ans += chi
    chi = min(chi + a[i], pa[i] + a[i])
print(ans + 1)

Submission status: Memory Limit Exceeded

Solution code:
# 深さdの上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))

# 深さdのノード数の上限
limit = [1]
for i in range(1, N+1):
    if i == N:
        limit.append(A[i])
    else:
        limit.append((limit[-1]-A[i-1])*2)

# Nが0の時の処理
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()

# 一番深いところから構築して最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]  # 一番深いところから構築しており，今現在の葉の数
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]
# 構築したものに対してジャッジする, 葉を確保できているかどうか
for i in range(N):
    # ans[N-i]とすることで，今は一番浅いところから見ている
    if (ans[N-i]-A[i])*2 < A[i+1]:  # 葉が確保できているか
        print(-1)
        exit()
print(sum(ans))

Submission status: Memory Limit Exceeded

Solution code:
# 深さdの上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))

# 例外の処理をもうちょい詰める
limit = [1]
for i in range(1, N+1):

    if i == N:
        limit.append(A[i])
    else:
        limit.append((limit[-1]-A[i-1])*2)
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()
    # if A[0] == 0:
    #     print(3-A[-1])
    #     exit()
    # else:
    #     print(-1)
    #     exit()

# 最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]
# 構築したものに対してジャッジする, 葉を確保できているかどうか
# del limit
# gc.collect()
# ans.reverse()

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

print(sum(ans))

Submission status: Memory Limit Exceeded

Solution code:
import gc
# 深さdの上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))

# 例外の処理をもうちょい詰める
limit = [1]
for i in range(1, N+1):

    if i == N:
        limit.append(A[i])
    else:
        limit.append((limit[-1]-A[i-1])*2)
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()
    # if A[0] == 0:
    #     print(3-A[-1])
    #     exit()
    # else:
    #     print(-1)
    #     exit()

# 最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]
# 構築したものに対してジャッジする, 葉を確保できているかどうか
del limit
gc.collect()
ans.reverse()

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

print(sum(ans))

Submission status: Memory Limit Exceeded

Solution code:
# 深さdの上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))
# 例外の処理をもうちょい詰める
limit = [1]
for i in range(1, N+1):

    if i == N:
        limit.append(A[i])
    else:
        limit.append((limit[-1]-A[i-1])*2)
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()
    # if A[0] == 0:
    #     print(3-A[-1])
    #     exit()
    # else:
    #     print(-1)
    #     exit()

# 最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]
# 構築したものに対してジャッジする, 葉を確保できているかどうか
ans.reverse()

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

print(sum(ans))

Submission status: Memory Limit Exceeded

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


N = INT()
A = LIST()

init_nodes = [0]*(N+1)
stems = [0]*(N+1)
init_nodes[0] = 1
stems[0] = 1


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

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


    # for i in range(N+1):
    #     if A[i] > 2**i:
    #         return -1

    ans = init_nodes[0]
    for i in range(1, N+1):
        init_nodes[i] = 2 * stems[i-1]
        stems[i] = init_nodes[i] - A[i]
        if stems[i] < 0: return -1
        ans += init_nodes[i]

    dif = init_nodes[-1] - A[-1]
    ans -= dif
    for i in reversed(range(N+1)):
        if init_nodes[i] - dif < 0: return -1
        dif = (dif-(init_nodes[i] - dif))//2
        if dif <= 0: break
        ans -= dif
    return ans

ans = solve()
if ans <= 0:
    print(-1)
else:
    print(ans)

Submission status: Memory Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
A = LI()
ANS = [0]*(n+1)
ANS[0] = 1
CONTINUE = [0]*(n+1)
if A[0] == 0:
    CONTINUE[0] = 1
elif A[0] == 1:
    CONTINUE[0] = 0
else:
    print(-1)
    exit()

tmp = 0
for i in range(1, n+1):
    if A[i] > CONTINUE[i-1]*2:
        print(-1)
        exit()
    else:
        CONTINUE[i] = CONTINUE[i-1]*2 - A[i]
        ANS[i] = CONTINUE[i] + A[i]

for i in reversed(range(n+1)):
    tmp += A[i]
    ANS[i] = min(ANS[i], tmp)

print(sum(ANS))

Submission status: Memory Limit Exceeded

Solution code:
import sys
from math import ceil
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()

INF = 2 ** 50
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] == 0:
    print(-1)
    exit()
# その層で作ることができるノードの最大値
max_i = defaultdict(lambda: INF)
max_i[0] = 1

for i in range(1, n+1):
    if max_i[i-1] * 2 - a[i] < INF:
        max_i[i] = max_i[i-1] * 2 - a[i]
    else:
        break
for i in max_i.keys():
    if i == 0:
        continue
    max_i[i] += a[i]

a = a[::-1]
cnt = 0
# 下の層の頂点の数
pre_cnt = 0
for i, v in enumerate(a):
    idx = n - i
    # print(idx, list(max_i.items()))
    if idx in max_i.keys():
        if v + ceil((pre_cnt) / 2) > max_i[idx]:
            print(-1)
            exit()
        # 上の頂点数
        pre_cnt = min(v + pre_cnt, max_i[idx])
        cnt += pre_cnt
    else:
        if v + ceil((pre_cnt) / 2) > INF:
            print(-1)
            exit()
        # 上の頂点数
        pre_cnt = min(v + pre_cnt, INF)
        cnt += pre_cnt

print(cnt)

Submission status: Memory Limit Exceeded

Solution code:
import sys
from math import ceil
input = lambda: sys.stdin.readline().rstrip()

INF = 2 ** 50
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] == 0:
    print(-1)
    exit()
# その層で作ることができるノードの最大値
max_i = [INF] * (n+1)
max_i[0] = 1

for i in range(1, n+1):
    if max_i[i-1] * 2 - a[i] < INF:
        max_i[i] = max_i[i-1] * 2 - a[i]
    else:
        max_i[i] = INF
for i in range(1, n+1):
    max_i[i] += a[i]

a = a[::-1]
cnt = 0
# 下の層の頂点の数
pre_cnt = 0
for i, v in enumerate(a):
    idx = n - i
    if v + ceil((pre_cnt) / 2) > max_i[idx]:
        print(-1)
        exit()
    # 上の頂点数
    pre_cnt = min(v + pre_cnt, max_i[idx])
    cnt += pre_cnt


print(cnt)

Submission status: Memory Limit Exceeded

Solution code:
import sys
from math import ceil
input = lambda: sys.stdin.readline().rstrip()

INF = 2 ** 40
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] == 0:
    print(-1)
    exit()
# その層で作ることができるノードの最大値
max_i = [INF] * (n+1)
max_i[0] = 1

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

# print(max_i)

a = a[::-1]
cnt = 0
# 下の層の頂点の数
pre_cnt = 0
for i, v in enumerate(a):
    idx = n - i
    if v + ceil((pre_cnt) / 2) > max_i[idx]:
        # print(ceil((v + pre_cnt) / 2), max_cnt + v)
        print(-1)
        exit()
    # 上の頂点数
    pre_cnt = min(v + pre_cnt, max_i[idx])
    cnt += pre_cnt
    # print(pre_cnt, cnt)

print(cnt)

Submission status: Memory Limit Exceeded

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

P = [1] * (N + 1)
for i in range(N):
  P[i + 1] = P[i] * 2

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

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

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

print(sum(L) + 1)

Submission status: Memory Limit Exceeded

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

Submission status: Accepted

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

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

A.reverse()
max_list = [A[0]]
before_top = A[0]
for i in range(1, len(A)):
    max_list.append(before_top + A[i])
    before_top = max_list[i]
    
A.reverse()
max_list.reverse()
ans = 1
before_top = 1
for i in range(1, len(A)):
    if A[i] <= before_top*2:
        ans += min(before_top*2, max_list[i])
        before_top = min(before_top*2, max_list[i]) - A[i]
    else:
        print(-1)
        exit()
        
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()

if A[0] != 0:
    print(-1)
    exit()
    
sum_leaf = sum(A)
ans = 1
before_top = 1
for i in range(1, len(A)):
    if A[i] <= before_top*2:
        ans += min(sum_leaf, before_top*2)
        before_top = min(sum_leaf, before_top*2) - A[i]
        sum_leaf -= A[i]
    else:
        print(-1)
        exit()

print(ans)