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:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if n == 0:
        return '1' if A[0] == 1 else '-1'

    ret = 0
    R = np.zeros(n+1, int)
    R[0] = 1-A[0]
    left = 0
    base = 0
    for i in range(1, n+1):
        R[i] = 2*R[i-1]-base

        for _ in range(A[i]):
            if R[i] <= base:
                return '-1'
            base += 1
            ret += 1+i-left
            while R[left] == base and left < i:
                left += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if n == 0:
        return '1' if A[0] == 1 else '-1'

    ret = 0
    R = np.zeros(n+1, int)
    R[0] = 1-A[0]
    left = 0
    base = 0
    for i in range(1, n+1):
        R[i] = 2*R[i-1]-base

        for _ in range(A[i]):
            if R[i] <= base:
                return '-1'
            base += 1
            ret += 1+i-left
            left = left+np.searchsorted(R[left:i+1], base, side='right')

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def step(n, lis):
  if lis.shape[0]==0:
    return lis
  return np.concatenate((np.zeros(n), lis))

def func(lis):
  if lis.shape[0]==0:
    return [-1, None]
  buf = lis[-1]
  res = lis.shape[0]
  #print(buf)
  if buf>1:
    lis[-1] -= 1
    lis[:-1] += 1
  else:
    lis = lis[:-1]
    lis += 1
  return [res, lis]

N = int(input())
A = list(map(int, input().split()))
lis = np.asarray([1])
count = 0
ans = 0
flag=False
for i in range(N+1):
  
  if flag or lis.shape[0]==0:
    flag=True
    break
  if A[i]==0:
    count += 1
    continue
  lis = step(count, lis)
  count=1
  a = A[i]
  #print(i,lis)
  for j in range(a):
    
    res, lis = func(lis)
    #print(i, res, lis.shape)
    if res == -1:
      flag=True
      break
    else:
      ans += res
  
if flag:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

# ps = [0] * (n+1)
# qs = [0] * (n+1)
# ps[-1] = As[-1]
# qs[-1] = As[-1]

p = As[-1]
q = As[-1]
Asr = As[::-1]
qs = [q]
# 深い方から見ていく
for j,a in enumerate(Asr[1:]):
    i = n - (j + 1) 
    p = (p+1)//2 + a 
    q = min(q + a, 2**i)

    # 最小値が、2**iを超えると、深さ0畳めないのでアウト
    if p > 2**i:
        print(-1)
        exit()
    
    # 2**iを超えない範囲での最大値
    qs.append(q)    
    
if p != 1:
    print(-1)
    exit()
qs.reverse()

qs[0] = 1
ans = 1
for i in range(1,n+1):
    if qs[i] > 2**i:
        qs[i] = 2 ** i
    if qs[i] > 2*(qs[i-1]-As[i-1]):
        qs[i] = 2 * (qs[i-1]-As[i-1])
    ans += qs[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = []
  min_maxs.insert(0, [A[-1], A[-1]])

  for a in reversed(A[:-1]):
    min_maxs.insert(0, [min_maxs[0][0] // 2 + a, min_maxs[0][1] + a])
  # print(min_maxs)
  # max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # # 各 depth における最小値
  # min_node_in_depth = [0] * (len(A))
  # min_node_in_depth[-1] = max_node_in_depth[-1]
  # index = -1
  # for i in range(1, len(A)):
  #   min_node_in_depth[index] = -(-min_node_in_depth[index + 1] // 2) + A[index]
  #   index = index - 1

  # for min_max in min_maxs:
  #   print(min_max)

  result = 1
  recent = 1
  for min_max, a in zip(min_maxs[1:], A):
    num_of_node = (recent - a) * 2
    # print(min_max, num_of_node)
    if num_of_node < min_max[0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_max[1])
    recent = min(num_of_node, min_max[1])

  print(result)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # 各 depth における最小値
  min_node_in_depth = [0] * (len(A))
  min_node_in_depth[-1] = max_node_in_depth[-1]
  index = -1
  for i in range(1, len(A)):
    min_node_in_depth[index] = -(-min_node_in_depth[index + 1] // 2) + A[index]
    index = index - 1

  result = 1
  recent = 1
  for min_node, max_mode, a in zip(min_node_in_depth[1:], max_node_in_depth[1:], A):
    # print(min_node, max_mode, a)
    num_of_node = (recent - a) * 2
    if num_of_node < min_node:
      print(-1)
      return True
    
    result += min(num_of_node, max_mode)
    recent = min(num_of_node, max_mode)

  print(result)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

b[0] = 1
for i in range(n):
    b[i+1] = 2*(b[i] - a[i])
#根から計算した深さごとの要素数の最大値

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]
#葉から計算した最小値

#print(b)
#print(c)

d = [0]*(n+1)
flag = 0
for k in range(n+1):
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1

for l in range(n):
    flag += 1 if d[l+1] < d[l] - a[l] or 2*d[l] - a[l] < d[l+1] else 0
    flag += 1 if a[l] + (d[l+1]+1)//2 > d[l] or d[l] > d[l+1] + a[l] else 0

ans = sum(d) if flag == 0 else -1
ans = -1 if n == 0 and a[0] > 1 else ans
ans = -1 if a[n] != d[n] else ans
print(ans)
#print(d)

Submission status: Time Limit Exceeded

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

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

s = 0
for i in range(n + 1):
    s += a[i] * two_pow[n - i]
if s > two_pow[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] > two_pow[i]:
        is_possible = False
        break
    c[i] = min(c[i + 1], two_pow[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:
def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # 各 depth における最小値
  min_node_in_depth = [0] * (len(A))
  min_node_in_depth[-1] = max_node_in_depth[-1]
  index = -1
  for i in range(1, len(A)):
    min_node_in_depth[index] = -(-min_node_in_depth[index + 1] // 2) + A[index]
    index = index - 1

  result = 1
  recent = 1
  for i in range(1, len(A)):
    num_of_node = (recent - A[i - 1]) * 2
    if num_of_node < min_node_in_depth[i]:
      print(-1)
      return True

    if num_of_node <= max_node_in_depth[i]:
      result += num_of_node
      recent = num_of_node
    else:
      result += max_node_in_depth[i]
      recent = max_node_in_depth[i]

  print(result)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
A=np.array(A)
v=0
j=0
k=0
for i in reversed(range(0, N+1)):
  j+=A[i]/(2**i)
  if i==N:
    k=A[i]
  else:
    k=min(k+A[i],2**min(i,27)-np.sum(np.array([A[k]*(2**min((i-k),27)) for k in range(i)])))
  v+=k

if j>1:
  print(-1)
else:
  print(int(v))

Submission status: Time Limit Exceeded

Solution code:
def main():
  import numpy as np
  n=int(input())
  a=list(map(int,input().split()))
  v=np.array([ai+1 for ai in a])
  v[-1]-=1
  vs=np.array([1]*n+[0])
  a[-1]-=1
  # 深さnの一本道の木を初期状態とする。
  # a[i]:深さiの葉でまだ木に連結していない葉
  nozero_vs=0
  for i in range(n+1):
    if a[i]==0:
      continue
    if nozero_vs>=i:# a[0]>0のときもここで処理
      print(-1)
      exit(0)
    # 未連結の葉を木にくっつける
    if vs[nozero_vs]>a[i]:
      vs[nozero_vs]-=a[i]
      vs[nozero_vs+1:i]+=a[i]
      v[nozero_vs+1:i]+=a[i]
    elif vs[nozero_vs]==a[i]:
      vs[nozero_vs]=0
      vs[nozero_vs+1:i]+=a[i]
      v[nozero_vs+1:i]+=a[i]
      nozero_vs+=1
    else:
      sum_vs=0
      while sum_vs<a[i]:
        if nozero_vs>=i:
          print(-1)
          exit(0)
        sum_vs+=vs[nozero_vs]
        if sum_vs<a[i]:
          b=vs[nozero_vs]
          vs[nozero_vs]=0
          vs[nozero_vs+1:i]+=b
          v[nozero_vs+1:i]+=b
          nozero_vs+=1
        else:
          b=sum_vs-a[i]
          c=vs[nozero_vs]-b
          vs[nozero_vs]=b
          vs[nozero_vs+1:i]+=c
          v[nozero_vs+1:i]+=c
  print(np.sum(v))

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import numpy as np
  n=int(input())
  a=list(map(int,input().split()))
  v=np.array([ai+1 for ai in a])
  v[-1]-=1
  vs=np.array([1]*n+[0])
  a[-1]-=1
  # 深さnの一本道の木を初期状態とする。
  # a[i]:深さiの葉でまだ木に連結していない葉
  nozero_vs=0
  for i in range(n+1):
    if a[i]==0:
      continue
    if nozero_vs>=i:# a[0]>0のときもここで処理
      print(-1)
      exit(0)
    # 未連結の葉を木にくっつける
    if vs[nozero_vs]>a[i]:
      vs[nozero_vs]-=a[i]
      vs[nozero_vs+1:i]+=a[i]
      v[nozero_vs+1:i]+=a[i]
    elif vs[nozero_vs]==a[i]:
      vs[nozero_vs]=0

      vs[nozero_vs+1:i]+=a[i]
      v[nozero_vs+1:i]+=a[i]
      nozero_vs+=1
    else:
      sum_vs=0
      while sum_vs<a[i]:
        if nozero_vs>=i:
          print(-1)
          exit(0)
        sum_vs+=vs[nozero_vs]
        if sum_vs<a[i]:
          b=vs[nozero_vs]
          vs[nozero_vs]=0

          vs[nozero_vs+1:i]+=b
          v[nozero_vs+1:i]+=b
          nozero_vs+=1
        else:
          b=sum_vs-a[i]
          c=vs[nozero_vs]-b
          vs[nozero_vs]=b
          vs[nozero_vs+1:i]+=c
          v[nozero_vs+1:i]+=c
  print(sum(v))

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

cnt = 1
node = [1]*N

# from functools import lru_cache
# @lru_cache(None)
def f(depth, leaf, nodec):
    # print(depth, leaf, nodec)
    if depth == N:
        # print(' ', depth, leaf, nodec)
        if leaf == A[depth]:
            # OK!
            print(nodec)
            exit()
            return
        else:
            # NG
            return
    
    # NG
    if leaf < A[depth]:
        return 0

    # OK
    not_leaf = leaf - A[depth]
    for j in range(not_leaf*2, not_leaf-1, -1):
        f(depth+1, j, nodec+j)

f(0, 1, 1)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))[::-1]

def f(A):
    nodes=[]
    for i in list(range(len(A))):
        t = len(A)-i-1
        if i == 0:
            if 2**t < A[i]:
                return -1
            nodes.append(A[i])
        else:
            tmp = min(nodes[-1] + A[i],2**t)
            anchor = (tmp-A[i])*2
            if anchor < nodes[-1]:
                flag = True
                for j in range(len(nodes))[::-1]:
                    if anchor < nodes[j]:
                        nodes[j] = anchor
                        anchor = (nodes[j]-A[j])*2
                    else:
                        flag = False
                        break
                if flag : return -1        
            nodes.append(tmp)
    return sum(nodes)
  
print(f(A))

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
A[N]-=1
ans=N+1
H=[1]*(N)+[0]
z=0
def get(t):
  global N
  global H
  global ans
  global z
  for k in range(z,t+1):
    if H[k]>=1:
      z=k
      H[k]-=1
      for l in range(k+1,t):
        H[l]+=1
      ans+=(t-k)
      break
  if k==t:
    if H[N]==0:
      print(-1)
      sys.exit()


for i in range(N+1):
  for j in range(A[i]):
    get(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  v=[ai+1 for ai in a]
  v[-1]-=1
  vs=[1]*n+[0]
  a[-1]-=1
  # 深さnの一本道の木を初期状態とする。
  # a[i]:深さiの葉でまだ木に連結していない葉
  nozero_vs=0
  for i in range(n+1):
    if a[i]==0:
      continue
    if nozero_vs>=i:# a[0]>0のときもここで処理
      print(-1)
      exit(0)
    # 未連結の葉を木にくっつける
    if vs[nozero_vs]>a[i]:
      vs[nozero_vs]-=a[i]
      for j in range(nozero_vs+1,i):
        vs[j]+=a[i]
        v[j]+=a[i]
    elif vs[nozero_vs]==a[i]:
      vs[nozero_vs]=0
      for j in range(nozero_vs+1,i):
        vs[j]+=a[i]
        v[j]+=a[i]
      nozero_vs+=1
    else:
      sum_vs=0
      while sum_vs<a[i]:
        if nozero_vs>=i:
          print(-1)
          exit(0)
        sum_vs+=vs[nozero_vs]
        if sum_vs<a[i]:
          b=vs[nozero_vs]
          vs[nozero_vs]=0
          for j in range(nozero_vs+1,i):
            vs[j]+=b
            v[j]+=b
          nozero_vs+=1
        else:
          b=sum_vs-a[i]
          c=vs[nozero_vs]-b
          vs[nozero_vs]=b
          for j in range(nozero_vs+1,i):
            vs[j]+=c
            v[j]+=c
  print(sum(v))

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
capacity = [1 for k in range(N+1)]
cut = 0
for k in range(N+1):
    #print(capacity)
    if A[k] >= capacity[k] and k!= N:
        print(-1)
        break
    if A[k] > capacity[k] and k == N:
        print(-1)
        break
    if k < N:
        capacity[k+1] = 2*(capacity[k] - A[k])
    if k == N:
        ans = [0 for k in range(N+1)]
        ans[0] =1
        for m in range(N+1):
            ans[m] = min(capacity[m], sum(A[m:N+1]))
        print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
A[N]-=1
ans=N+1
H=[1]*(N)+[0]
z=0
def get(t):
  global N
  global H
  global ans
  global z
  for k in range(z,t+1):
    if H[k]>=1:
      z=k-1
      H[k]-=1
      for l in range(k+1,t):
        H[l]+=1
      ans+=(t-k)
      break
  if k==t:
    if H[N]==0:
      print(-1)
      sys.exit()


for i in range(N+1):
  for j in range(A[i]):
    get(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]

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


    que = deque()
    que.appendleft([0,1,0])

    while que:
        x = que.popleft()
        d = x[0]
        point = x[1]
        counter = x[2]
        counter += point

        if d == n:
            if point == a[n]:
                print(counter)
                exit()
            else:
                continue

        #if point-a[d] <= 0:
        #    #すべて葉 or 葉の数がa[d]に足りない。
        #    continue

        for nextp in range(point-a[d],(point-a[d])*2+1):
            if nextp-a[d+1] >= 0:
                que.appendleft([d+1,nextp,counter])

    print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
def solve():
    if A[0] != 0:
        if N == 0 and A[0] == 1:
            print(1)
        else:
            print(-1)
        return 0
    add_ans = list()
    add_ans.append(1)
    stem = list()
    stem.append(1)
    for i in range(1, N+1):
        last_stem = stem[-1]
        add_ans.append(2*last_stem)
        stem.append(last_stem*2 - A[i])
        if stem[-1] < 0:
            print(-1)
            return 0
    
    illegal = list()
    illegal.append(stem[-1])
    ind = N
    legal_stem = list()
    legal_stem.append(0)
    while illegal[-1] > 0:
        last_illegal = illegal[-1]

        if last_illegal- legal_stem[-1]- A[ind] > 0:
            illegal.append((last_illegal- legal_stem[-1]- A[ind])//2)
            legal_stem.append(stem[ind-1] - illegal[-1])
        else:
            illegal.append(0)
        ind -= 1
    # print(stem)
    # print(illegal)
    # print(legal_stem)
    len_ill = len(illegal)
    ans = 0
    for i in range(N+1):
        ans += add_ans[i]
        if i < len_ill:
            ans -= illegal[i]
    # print(add_ans)
    # print(illegal)
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if n == 0:
        return '1' if A[0] == 1 else '-1'

    ret = 0
    R = np.zeros(n+1, int)
    R[0] = 1-A[0]
    left = 0
    for i in range(1, n+1):
        R[i] = 2*R[i-1]

        for _ in range(A[i]):
            if R[i] <= 0:
                return '-1'

            R[left:i+1] -= 1
            ret += 1+i-left
            left = left+np.searchsorted(R[left:i], 0, side='right')

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = [int(v) for v in input().split()]
    b = [a[i] for i in range(n + 1)]
    for i in reversed(range(0, n)):
        b[i] += b[i + 1]
    result = a[n]
    d = 0
    for i in range(n):
        d = 2 * d + a[i]
        if 2 ** i - d < 0:
            print(-1)
            return
        result += min(2 ** i - d, b[i + 1]) + a[i]
    d = 2 * d + a[n]
    if 2 ** n - d < 0:
        print(-1)
        return
    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
capacity = [1 for k in range(N+1)]
cut = 0
for k in range(N+1):
    #print(capacity)
    if A[k] >= capacity[k] and k!= N:
        print(-1)
        break
    if A[k] > capacity[k] and k == N:
        print(-1)
        break
    if k < N:
        capacity[k+1] = 2*(capacity[k] - A[k])
    if k == N:
        ans = [0 for k in range(N+1)]
        ans[0] =1
        for j in range(N+1):
            for m in range(j+1):
                ans[m] = min(capacity[m], ans[m] + A[j])
        print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]

def main():
    n = int(input())
    a = list(map(int,input().split()))
    
    
    que = deque()
    que.appendleft([0,1,0])
    
    while que:
        x = que.popleft()
        d = x[0]
        point = x[1]
        counter = x[2]
        counter += point
    
        if d == n:
            if point == a[n]:
                print(counter)
                exit()
            else:
                continue
            
        if point-a[d] <= 0:
            #すべて葉 or 葉の数がa[d]に足りない。
            continue
        
        for nextp in range(point-a[d],(point-a[d])*2+1):
            que.appendleft([d+1,nextp,counter])
    
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
A[N]-=1
ans=N+1
H=[1]*(N)+[0]
def get(t):
  global N
  global H
  global ans
  for k in range(t+1):
    if H[k]>=1:
      H[k]-=1
      for l in range(k+1,t):
        H[l]+=1
      ans+=(t-k)
      break
  if k==t:
    if H[N]==0:
      print(-1)
      sys.exit()


for i in range(N+1):
  for j in range(A[i]):
    get(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]

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


que = deque()
que.appendleft([0,1,0])

while que:
    x = que.popleft()
    d = x[0]
    point = x[1]
    counter = x[2]
    counter += point

    if d == n:
        if point == a[n]:
            print(counter)
            exit()
        else:
            continue

    if point-a[d] <= 0:
        #すべて葉 or 葉の数がa[d]に足りない。
        continue

    for nextp in range(point-a[d],(point-a[d])*2+1):
        que.appendleft([d+1,nextp,counter])

print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    import sys
    sys.setrecursionlimit(10**7)
    """def main(N,ls):
        d = []
        d.append([1,1])
        for i in range(1,N+1):#iでふかさiの求められる最小の個数と最大の個数を出してく
            a = ls[i]
            fco = d[i-1]
            mx = fco[1]*2 - a
            mn = fco[0] -a
            d.append([mn,mx])"""
    result = []
    def dfs(r,tn,fc):
        if r == N:
            if fc == ls[N]:
                result.append(tn)
        else:
            a = ls[r]
            mx = fc*2 - a*2
            mn = max(1,fc -a)
            for j in range(mn,mx+1):
                dfs(r+1,tn+j,j)#


    N = int(input())
    ls = list(map(int, stdin.readline().split()))
    fin = ls[N]
    dfs(0,1,1)
    if len(result) == 0:
        print(-1)
    else:
        print(max(result))
main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)


class Solver:
    def __init__(self, depth_list):
        self.ans = -1
        self.depth_list = depth_list

    @lru_cache(None)
    def helper(self, d, current_sum, min_nodes, max_nodes):
        if d == 0:
            if min_nodes == 1:
                self.ans = max(self.ans, current_sum+1)
                return
            else:
                return
        else:
            max_size = 2 ** d
            # if number of leaf is grater than the size of max nodes for the layer
            if min_nodes > max_size:
                return
            for c in range(min_nodes, max_nodes):
                if c > max_size:
                    continue
                min_nodes = (c // 2) + (c % 2) + self.depth_list[d - 1]
                max_nodes = c + self.depth_list[d - 1]+1
                self.helper(d-1, current_sum+c, min_nodes, max_nodes)


def main():
    N = int(input().strip())
    depth_list = [int(i) for i in input().strip().split()]
    solver = Solver(depth_list)
    solver.helper(N, 0, depth_list[-1], depth_list[-1]+1)

    return solver.ans


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#from collections import deque
import sys 
sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]




def saiki(d,point,counter):
    counter += point
    if d == n:
        if point == a[n]:
            print(counter)
            exit()
        else:
            return
    
    if point-a[d] <= 0:
        #すべて葉 or 葉の数がa[d]に足りない。
        return

    for nextp in range((point-a[d])*2,point-a[d]-1,-1):
        saiki(d+1,nextp,counter)
    
    return


def main():
    saiki(0,1,0)
    print(-1)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N == 0 and A[0] == 1:
    print(1)
else:
    nodes = [0]*(N+1)
    s_d = 0 # 飽和してないノードが残ってる深さ
    cap_d = 1 - A[0]
    failed = False
    for i, a in enumerate(A):
        # a個の葉をなるべく浅いノードから取る
        while a > 0:
            # これ以上分岐することろがなければ失敗
            if i < s_d or cap_d <= 0:
                failed = True
                break
            # s_dから枝を取れるだけ取る
            x = min(cap_d - nodes[s_d], a)
            a -= x
            nodes[s_d:i+1] = [node + x for node in nodes[s_d:i+1]]
            # s_dがいっぱいになったら深さを一つ進める
            if nodes[s_d] >= cap_d:
                cap_d -= A[s_d]
                cap_d *= 2
                s_d += 1
        if failed:
            break
    print(-1 if failed else sum(nodes))

Submission status: Time Limit Exceeded

Solution code:
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#from collections import deque
import sys 
sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]




def saiki(d,point,counter):
    counter += point
    if d == n:
        if point == a[n]:
            print(counter)
            exit()
        else:
            return
    
    if point-a[d] <= 0:
        #すべて葉 or 葉の数がa[d]に足りない。
        return

    for nextp in range((point-a[d])*2,point-a[d]-1,-1):
        saiki(d+1,nextp,counter)
    
    return








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


saiki(0,1,0)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
from collections import deque
import sys 
sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]




def saiki(d,point,counter):
    counter += point
    if d == n:
        if point == a[n]:
            print(counter)
            exit()
        else:
            return
    
    if point-a[d] <= 0:
        #すべて葉 or 葉の数がa[d]に足りない。
        return

    for nextp in range((point-a[d])*2,point-a[d]-1,-1):
        saiki(d+1,nextp,counter)
    
    return








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


saiki(0,1,0)

print(-1)

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
        
print(sum([min(MAX[i], A_inter[i]) for i in range(N+1)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a_li = list(map(int, input().split()))
muri = False
cnt = 0
for i in range(n, -1, -1):
    cnt = np.ceil(cnt/2) + a_li[i]
    if cnt > 2**i:
        muri = True
        break
if muri:
    print(-1)
else:
    cnt = 1
    node = 1
    las = a_li[-1]
    if n==0:
        print(1)
    else:
        for i in range(1, n):
            node = min(node*2-a_li[i], sum(a_li[i+1:]))
            cnt += node + a_li[i]
        print(cnt+las)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
def solve():
    if A[0] != 0:
        if N == 0 and A[0] == 1:
            print(1)
        else:
            print(-1)
        return 0
    ans = 1
    stem = list()
    stem.append(1)
    for i in range(1, N+1):
        last_stem = stem[-1]
        ans += 2*last_stem
        stem.append(last_stem*2 - A[i])
        if stem[-1] < 0:
            print(-1)
            return 0
    illegal = list()
    illegal.append(stem[-1])
    ind = N
    legal_stem = list()
    legal_stem.append(0)
    while illegal[-1] > 0:
        last_illegal = illegal[-1]

        if last_illegal- legal_stem[-1]- A[ind] > 0:
            illegal.append((last_illegal- legal_stem[-1]- A[ind])//2)
            legal_stem.append(stem[ind-1] - illegal[-1])
        else:
            illegal.append(0)
        ind -= 1
    # print(stem)
    # print(illegal)
    # print(legal_stem)
    print(ans - sum(illegal))


solve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(10**7)
"""def main(N,ls):
    d = []
    d.append([1,1])
    for i in range(1,N+1):#iでふかさiの求められる最小の個数と最大の個数を出してく
        a = ls[i]
        fco = d[i-1]
        mx = fco[1]*2 - a
        mn = fco[0] -a
        d.append([mn,mx])"""
result = []
def dfs(r,tn,fc):
    if r == N:
        if fc == ls[N]:
            result.append(tn)
    else:
        a = ls[r]
        mx = fc*2 - a*2
        mn = max(1,fc -a)
        for j in range(mn,mx+1):
            dfs(r+1,tn+j,j)#


N = int(input())
ls = list(map(int, stdin.readline().split()))
fin = ls[N]
dfs(0,1,1)
if len(result) == 0:
    print(-1)
else:
    print(max(result))