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: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10


    N = II()
    A = LMIIS()


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


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


    sum_top = 1

    tmp = 1
    
    for i in range(1,N+1):
        max_l = tmp*2
        if max_l >= max_nodes[i]:
            print(sum_top+sum(max_nodes[i:]))
            return
        sum_top += max_l
        tmp = max_l - A[i]
        if tmp < 0:
            print(-1)
            return

    dbg(sum_top)
    print(-1)


main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
a=[1-A[0]]
for k in range(N):
    ak=a[-1]
    a.append(2*ak-A[k+1])
    if a[-1]<0:
        print(-1)
        exit()
    if a[-1]>10**17:
        break
M=len(a)
for k in range(N,0,-1):
    if k-1<M:
        A[k-1]=A[k-1]+min(A[k],a[k-1])
    else:
        A[k-1]=A[k-1]+A[k]
print(sum(A))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

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

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

sum_a = [ sum( a ) ]
for d in range( 1, n + 1 ):
    sum_a_next = sum_a[ -1 ] - a[ d - 1 ]
    sum_a.append( sum_a_next )
print( sum_a )

d_vertex = [ 0 for d in range( n + 1 ) ]

d_vertex[ 0 ] = 1
num_of_v = d_vertex[ 0 ]
for d in range( 1, n + 1 ):
    d_vertex[ d ] = min( sum_a[d], ( d_vertex[ d - 1 ] - a[ d - 1 ] ) * 2 )
    if d_vertex[ d ] <= 0:
        print( -1 )
        exit()
    num_of_v += d_vertex[ d ]
    print( d, d_vertex )

print( num_of_v )

Submission status: Wrong Answer

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

MAX = [P[-1]] * (N+1)
MIN = 0
J = True

for i in range(N):
  MAX[N-1-i] = MAX[N-i] + P[N-1-i]

#print(MAX)

follow = 1
hikaku = True
ans = 0
for i in range(N+1): 
  p = follow + P[i]
  if follow < 0:
    J = False
  if hikaku:
    if p > MAX[i]:
      hikaku = False
      ans += MAX[i]
    else:
      ans += p
      follow *= 2
      if i != N:
        follow -= P[i + 1]
      else:
        follow += P[-1]
  else:
    ans += MAX[i]
  
  
if P[0] != 0:
  J = False
  
if J:
  print(ans)  
else:
  print(-1)

Submission status: Wrong Answer

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

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

ret = 1
children = 1

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= 0 and i != N-1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
    print(children)
    print(bottom)
print(ret)

Submission status: Wrong Answer

Solution code:
print("-1")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a1=input()
a1=a1.split()
a=[int(s) for s in a1]
M=1
m=int(a[n])
Ml=list()
ml=list()
Ml.append(M)
ml.append(m)
Q=0
if int(a[0])>=1:
    print(-1)
    sys.exit()
for i in range(n):
    M=2*M-int(a[i+1])
    if M<0:
        print(-1)
        sys.exit()
    M1=M+int(a[i+1])
    Ml.append(M1)
    m=sum(a[i+1:])
    ml.append(m)
    Q=Q+min(Ml[i],ml[i])
Q=Q+min(Ml[n],ml[n])   
print(Q)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A == [0]:
            print('-1')
        elif A == [1]:
            print('1')
        else:
            print('-1')
        return
    if N == 1:
        if A == [0, 1]:
            print('2')
        elif A == [0, 2]:
            print('3')
        else:
            print('-1')
        return

    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1


    for d in range(1, N):
        f[d] = 2 * min(f[d - 1], count) - A[d] + min(max(f[d - 1] - count, 0), f[d - 1])
        count -= min(f[d - 1], count)
        if f[d] <= 0:
            print('-1')
            return
    print(sum(f) + 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: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = list(mapi())
res =a[n]
mp = [min(2**(i),int(1e8)) for i in range(n+1)]
#print(*mp)
lst = 1
pst = [0]*(n+1)
for i in range(n+1):
    #print(lst,a[i])
    #res+=lst
    pst[i] = lst
    if pst[i]<=0:
        print(-1)
        exit()
    lst-=a[i]
    lst*=2
#print(*pst,"c")
#print(*mp,"d")
mx = a[n]
for i in range(n-1,-1,-1):
    if a[i]>=mp[i] or a[i]>=pst[i]:
        res = -1
        break
    mx = min(mx,mp[i])
    res+=min(mx+a[i],mp[i],pst[i])
    #print(res,mx,mp[i],a[i])
print(res)

Submission status: Wrong Answer

Solution code:
DELIM = 1

def kaijo(r, n):
    if(n == 0):
        return 1
    if(n == 1):
        return r
    else:
        mod = n % 2
        n_red = n // 2
        if(mod == 1):
            return (r * ((kaijo(r, n_red) % DELIM)**2) % DELIM) % DELIM
        else:
            return ((kaijo(r, n_red) % DELIM)**2) % DELIM

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

    final_leave_num = A[N]

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

    next_node_w_children = 0
    next_leaf_num = 0
    next_node_num = 1
    node_in_the_dept = 0
    
    for i in range(N):
        node_in_the_dept = next_node_num
        node_w_children = node_in_the_dept - A[i]        
        next_leaf_num = A[i+1]

        if(i == N-1):
            next_node_w_children = 0
            if(node_w_children > next_leaf_num):
                print(-1)
                return
            else:
                node_num += next_leaf_num
                print(node_num)
        else:
            next_node_w_children = min(2 * node_w_children - next_leaf_num, final_leave_num)
            next_node_num = next_node_w_children + next_leaf_num
            if(next_node_w_children > node_w_children * 2):
                print(-1)
                return
            node_num += (next_node_w_children + next_leaf_num)
    
main()

Submission status: Wrong Answer

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

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

for index, a in enumerate(A[1:], start=1):
    nodes[index] = nodes[index - 1] * 2 - a
    if nodes[index] < 0:
        print(-1)
        break
else:
    fixed_nodes = [0] * (N + 1)
    fixed_nodes[-1] = A[-1]
    for i in reversed(range(N)):
        fixed_nodes[i] = min(nodes[i], fixed_nodes[i + 1])
        fixed_nodes[i] += A[i]
    else:
        if any([n == 0 for n in fixed_nodes]):
            print(-1)
        else:
            print(sum(fixed_nodes))

Submission status: Wrong Answer

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

b = [1]
for i in range(n):
    tmp = b[i] - a[i]
    b.append(min(tmp * 2, a_max[i + 1]))
    if tmp < 1:
        print(-1)
        break
else:
    print(sum(b))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 変更
def dfs(i,c,f):
  global ans
  if i>2**f:
    ans=-2
    
  if f==0 and i==1:
    ans=max(ans,c)
  elif f==0:
    ans=-1
  else:
    for k in range(i//2+1):
      if i-k+a[f-1]<=2**(f-1):
        dfs(i-k+a[f-1],c+i-k+a[f-1],f-1)
      
n=int(input())
a=list(map(int,input().split()))
ans=-1
if a[0]==1:
  print(1)
elif a[0]>=2:
  print(-1)
else:
  dfs(a[n],a[n],n)
  if ans!=-1:
    print(ans)
  else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
b=1

l_sita=[0]*n
h_sita=[0]*n
ans=1
if l[0]>0:
  print(-1)
else:
  r=0
  if l[n]%2==1:
    r=l[n]//2+1
  else:
    r=l[n]//2
  l_sita[n-1]=r+l[n-1]
  h_sita[n-1]=l[n]+l[n-1]
  for d in range(n-2):
    r=0
    if l[n-d-1]%2==1:
      r=l[n-d-1]//2+1
    else:
      r=l[n-d-1]//2
    l_sita[n-d-2]=r+l[n-d-2]
    h_sita[n-d-2]=h_sita[n-d-1]+l[n-d-2]
  for d in range(n):
  #深さdに対してl[d]は葉の数。
  #bは深さdでの枝の数。
  #d+1での葉の数+dの葉の数
  #深さdの最大頂点数
  #上二つのうち小さい方が最大値。
  #枝の最小値はd+1の葉の数/2(切り上げ)+dの葉の数
    if d==n-1:
      ans+=l[d+1]
    else:
      ans+=min(h_sita[d+1],2*b)
      if b<=0 or 2*b<l_sita[d+1]:
        ans=-1
        break
      b=min(h_sita[d+1],2*b)-l[d+1]
  print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ima = 0
count = 0
flag = True

for i in reversed(range(len(A)-1)):
    n = (2**i - A[i])*2
    m = ima + A[i+1]
    if (n - A[i+1]) *2 >= ima:
        ima = min(n, m)
        count += min(n, m)
    else:
        flag = False
        break

if flag:
    print(count+1)
else:
    print(-1)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A == 0:
            print('-1')
        elif A == 1:
            print('1')
        else:
            print('-1')
        return
    if N == 1:
        if A == [0, 1]:
            print('2')
        elif A == [0, 2]:
            print('3')
        else:
            print('-1')
        return

    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1


    for d in range(1, N):
        f[d] = 2 * min(f[d - 1], count) - A[d] + min(max(f[d - 1] - count, 0), f[d - 1])
        count -= min(f[d - 1], count)
        if f[d] <= 0:
            print('-1')
            return
    print(sum(f) + 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: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0] *(N+1)
B[0] = 1
ans = 0
for i in range(1, N+1):
    B[i] = (B[i-1] - A[i-1])*2
    if B[i] <= 0:
        ans = -1
        break
if A[N] == 0:
    ans = -1
if ans == 0:
    check = 0
    for j in range(N, 0, -1):
        check += A[j]
        if check < B[j]:
            ans += check
        else:
            last = j
            for k in range(last+1):
                ans += B[k]
            break
print(ans)

Submission status: Wrong Answer

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

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

top_m = [0] * (n+1)
top = 1
for i, x in enumerate(a):
    top_m[i] = top - x
    top = top_m[i] * 2
top_m = top_m[::-1][1:]
# print(top_m)

p_max = a[-1]
p_min = math.ceil(p_max/2)
top = p_max
a = a[::-1][1:]
for i, x in enumerate(a):
    # print(x, p_max, p_min, top_m[i], top)
    if p_min > top_m[i]:
        print(-1)
        exit()
    now = x + min(p_max, top_m[i])
    p_max = now
    p_min = math.ceil(now/2)
    top += now
print(top)

Submission status: Wrong Answer

Solution code:
n = int(input())
A_list = list(map(int, input().split()))
count_node = 0
count_pre_node = 0
sum_node = 0
Tree_list = []

for  i in range(len(A_list)):
    if i == 0:
        Tree_list.append(1)
        continue
    Tree_list.append(2*(Tree_list[i-1]) - A_list[i])
Tree_list.reverse()

A_list.reverse()
for i in range(len(A_list)):
    count_node = A_list[i] + count_pre_node
    sum_node += count_node
    

    if i == 0 and A_list[-1] != 0:
        sum_node = -1
        break

    if i == len(A_list)-1:
        break

    if count_node > 2*Tree_list[i+1]:
        sum_node = -1
        break
    
    if count_node >= Tree_list[i+1]:
        count_pre_node = Tree_list[i+1]
    else:
        count_pre_node = count_node

print(sum_node)

Submission status: Wrong Answer

Solution code:
N, *A = map(int, open(0).read().split())

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

ans = 0
cur = 0
for i in reversed(range(N + 1)):
    cur += A[i]
    ans += min(cnt[i], cur)
        
if all(v > 0 for v in cnt):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
level = [0 for i in range(n+1)]
cur_pow = 1
if A[0] > 0 and n >= 1:
    print(-1)
    exit()
if A[0] > cur_pow:
    print(-1)
    exit()
level[0] = 1
for i in range(1, n+1):
    if A[i] > cur_pow:
        print(-1)
        exit()
    cur_pow *= 2
    level[i] = min(cur_pow, 2*(level[i-1]-A[i-1]))
level[-1] = A[-1]
for i in range(n-1, -1, -1):
    level[i] = min(level[i], level[i+1]+A[i])
print(sum(level))

Submission status: Wrong Answer

Solution code:

def resolve():
  N = int(input())
  if N == 0:
    print(0)
    return True

  A = [int(x) for x in input().split(" ")]
  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]
  start_index = -1
  for i in range(1, len(A)):
    min_node_in_depth[start_index-i] = -(-min_node_in_depth[start_index-i + 1] // 2) + A[start_index-i]

  node = [0] * (len(A))
  node[0] = 1

  for i in range(1, len(A)):
    num_of_node = (node[i - 1] - 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]:
      node[i] = num_of_node
    else:
      node[i] = max_node_in_depth[i]

  print(sum(node))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

n = int(input())
tree = [int(i) for i in input().split()]
top = []
bot= []
sub=0
leave = 0
mult = .5
nub=0
splice =  0
if tree[0]>0 and n>0:
  leave=1
elif tree[0]>1 and n==0:
  leave = 1

for i in range(n+1):
  if tree[i]>mult*2:
    leave = 1
  else:
    pass
  top.append((mult-sub)*2)
  mult = top[-1]
  sub = tree[i]
  bot.insert(0,(tree[-(i+1)]+nub))
  nub = bot[0]

for d in range(n):
  if top[d]==bot[d]:
    splice=d
  elif top[d+1]==bot[d+1]:
    splice=d+1
  elif top[d]<bot[d+1]<top[d+1]:
    splice=d

top=top[0:splice+1]
bot=bot[splice+1:]
if leave ==1:
  print(-1)
else:
  print(int(sum(top)+sum(bot)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

ans=[0]*(n+1)
ans[0]=1

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

ans[n]=a[n]

def dfs(fukasa):
    if fukasa == 0:
        return True

    tmp = a[fukasa]+ans[fukasa+1]
    tmp = min(tmp,2**fukasa)

    while tmp >= a[fukasa] -(-ans[fukasa+1]//2):
        ans[fukasa]=tmp
        tmpp = dfs(fukasa-1)
        if tmpp:
            ans[fukasa]=tmp
            break

        tmp -= 1
    else:
        return False
    return True


tmp = dfs(n-1)

if tmp:
    print(sum(ans))
else:
    print(-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys #追加
from collections import deque
sys.setrecursionlimit(10**9) #追加

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

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



start = 1
way = sum(A)

for i in range(1,n+1):
    start *= 2

    if start < A[i]:
        print(-1)
        exit()
    if start > way:
        start = way

    ans += start
    #print(start, start-A[i])
    start -= A[i]
    way -= A[i]
#print()
print(ans+1)

Submission status: Wrong Answer

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

if A[0] != 0:
    print(-1)
else:
    B = [0]*(N+1)
    C = [0]*(N+1)
    B[0] = 1
    C[N] = A[N]
    flag = True
    for i in range(1,N+1):
        B[i] = (B[i-1]-A[i-1]) * 2
        if B[i] < A[i]: flag = False
        C[N-i] = C[N+1-i]+A[N-i]
    sum = 0
    for i in range(0,N+1):
        sum += min(B[i],C[i])
    if flag == True:
        print(sum)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())+1
a = list(map(int, input().split()))
m_node = [1]*n
node = 0
total = 0
for i in range(1, n):
    m_node[i] = (m_node[i-1] - a[i-1])*2
    if m_node[i] <= 0:
        print("-1", end="")
        exit()
for i in reversed(range(n)):
    node = min((node+a[i]), m_node[i])
    total += node

print(total, end="")

Submission status: Wrong Answer

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

ans=0
bef=0

tmp=[]

for i in range(N+1):
    if i==0:
        if A[0]==1:
            bef=0
        elif A[0]>1:
            print("-1")
            exit()
        elif N==0 and A[0]==0:
            print("-1")
            exit()
        else:
            bef=1
        tmp.append(1)
        continue
    elif (bef*2-A[i])>=0:
        bef=bef*2-A[i]
        tmp.append(bef)
    else:
        print("-1")
        exit()

for i in range(N+1):
    current=A[-(i+1)]
    if i==0:
        bef=current
        ans+=current
        continue
    else:
        tmpp = tmp[-(i+1)]
        if current+bef > tmpp:
            ans+=tmpp+current
            bef=tmpp+current
        else:
            ans+=current+bef
            bef=current+bef

if ans==0:
    ans=-1

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

num = [0]*(N+1)  # 各層で葉を除いたとれるノードの限界

ma = 1
for i, a in enumerate(A):
	if i == N and a <= ma:
		num[i] = ma-a
	elif a <= ma-1:
		num[i] = ma-a
		ma = (ma-a)*2
	else:
		print(-1)
		exit()

tmp = 0
ans = 0
for i, a in enumerate(A[::-1]):
	d = N-i
	if tmp > num[d]:
		tmp = -(-tmp//2)
	if tmp > num[d]:
		print(-1)
		exit()
	tmp += a
	ans += tmp

print(ans)

Submission status: Wrong Answer

Solution code:
n = (int)(input())
a = list(map(int, input().split(" ")))
now = 1
total = 1
for i in range(n + 1):
    #print(now)
    if a[i] > now:
        print(-1)
        break
    else:
        now -= a[i]
        if sum(a[i + 1:]) > now * 2:
            now *= 2
        else:
            now = sum(a[i + 1:]) 
        total += now
print(total)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input()) + 1
    A = list(map(int, input().split()))

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

    # max internal node
    MI = [0 for _ in range(N)]
    MI[0] = 1
    for i in range(1, N):
        MI[i] = (MI[i-1] - A[i-1]) * 2
        if MI[i] <= 0:
            return -1

    results = [0 for _ in range(N)]
    results[N-1] = min(A[N-1], MI[N-1])
    for i in range(N-2, -1, -1):
        results[i] += min(results[i+1] + A[i], MI[i])
        if results[i] <= 0:
            return -1

    return sum(results)

    # print(MI)
    # print(results)


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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
 
if a[0] != 0:
    print(-1)
    exit()
 
ans = 1
sm = sum(a)
limit = 1
for i in range(1, n):
    ans += a[i]
    limit = 2*limit - a[i]
    if limit <= 0:
        print(-1)
        exit()
    else:
        sm -= a[i]
        if limit <= sm:
            ans += limit
        else:
            ans += sm
 
ans += a[-1]
 
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
cnt=0
B1=list(map(int,input().split()))
if B1[0]!=0 and n>1:
    print(-1)
    exit()
if B1[0]>=1 and n==1:
    print(-1)
    exit()
if B1[0]==0 and n==1:
    print(-1)
    exit()
if B1[0]==1 and n==1:
    print(1)
    exit()
D=B1.copy()
A=[0]*(n+1)
A[0]==1 

import math
C=[0]*(n+1)
C[-1]=B1[-1]
upper=[0]*(n+1)
upper[-1]=0
for i in range(n,-1,-1):
    if B1[0]>1:
        print(-1)
        exit()
    if i:
        B1[i-1]+=math.ceil(B1[i]/2)
        C[i-1]=B1[i-1]
        upper[i-1]=(upper[i]+D[i])
lower=[0]*(n+1)
lower[0]=1
for i in range(1,n+1):
    lower[i]=2*lower[i-1]-D[i]
    A[i]=min(lower[i],upper[i])

print(sum(A)+sum(D)+1)

Submission status: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = list(mapi())
res =a[n]
mp = [min(2**(i),int(1e8)) for i in range(n+1)]
#print(*mp)
lst = 1
pst = [0]*(n+1)
for i in range(n+1):
    #print(lst,a[i])
    #res+=lst
    pst[i] = lst
    if pst[i]<=0:
        print(-1)
        exit()
    lst-=a[i]
    lst*=2
#print(*pst,"c")
#print(*mp,"d")
mx = a[n]
for i in range(n-1,-1,-1):
    if a[i]>=mp[i] or a[i]>=pst[i]:
        res = -1
        break
    mx = min(mx,mp[i])
    res+=min(mx+a[i],pst[i])
    #print(res,mx,mp[i],a[i])
print(res)

Submission status: Wrong Answer

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

if(a[0] != 0):
    if(n == 0):
        print('1')
    else:
        print('-1')

maxs = [1]

for i in range(1,n+1):
    nex = maxs[i-1]*2 - a[i]
    maxs.append(nex)

if(maxs[n] < 0):
    print('-1')
    sys.exit()

results = [a[n]]

for i in range(n):
    if(results[i]%2 == 0 and results[i]//2 > maxs[n-i-1]):
        print('-1')
        sys.exit()
    elif(results[i]%2 != 0 and results[i]//2 + 1 > maxs[n-i-1]):
        print('-1')
        sys.exit()
    elif(results[i] > maxs[n-i-1]):
        results.append(maxs[n-i-1]+a[n-i-1])
    else:
        results.append(results[i]+a[n-i-1])


print(sum(results))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
if a[0] != 0:
    ans = -1
p = [1-a[0]]
for i in range(n-1):
    if 2*p[-1]-a[i+1] <= 0:
        ans = -1
    p.append(2*p[-1]-a[i+1])
if n == 0 and a[0] == 1:
    print(1)
elif n == 1:
    if a[0] == 0 and a[1] == 1:
        print(2)
    elif a[0] == 0 and a[1] == 2:
        print(3)
    else:
        print(-1)
elif ans == -1:
    print(-1)
else:
    a.reverse()
    p.reverse()
    ans = 0
    ans += a[0]
    q = a[0]
    for i in range(1,n+1):
        if n < 101 and 2**(n-i) < -(-q//2)+a[i]:
            ans = -1
            break
        if q < p[i-1]:
            ans += q+a[i]
            q = q+a[i]
        else:
            ans += p[i-1]+a[i]
            q = p[i-1] + a[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
cnt = 0
dic = defaultdict(int)
prv = -1
ans = 0
nya = False
max_ = 0
for i in range(n+1):
    if i == 0:
        if A[i] == 0:
            max_ = max(A[i],max_)
            dic[0] = 1
            cnt += 1
        else:
            print(-1)
            exit()
    else:
        if max_ <= A[i]:
            if not dic[A[i]]:
                max_ = max(A[i],max_)
                dic[A[i]] = 1
                ans += A[i] * cnt
            else:
                if A[i] != 0:
                    dic[A[i]] += 1
                    ans += cnt * dic[A[i]] * A[i]
                    #cnt += 1
                    cnt += 1
                else:
                    cnt += 1
                max_ = max(A[i],max_)
        else:
            if dic[A[i]]:
                ans += cnt * dic[A[i]] if A[i] != 0 else cnt
                cnt += 1
            else:
                print(-1)
                exit()
    #print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0
branch_num = 0

candidates = [1]
possible = 1
for a in As:
    possible -= a
    possible *= 2
    candidates.append(possible)

candidates.pop(-1)

for i in range(1, N+1):
    index = -i
    a = As[index]
    c = candidates[index]
    if c < a:
        result = -1
        break
    branch_num += a
    result += min(branch_num, c)
    if branch_num//2 > c:
        branch_num = branch_num//2

    N -= 1

if result != -1:
    result += 1

print(result)

Submission status: Wrong Answer

Solution code:

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

ch = [1]

cH = [1]
if A[0]>0:
    print(-1)
    exit()
if A[-1]==0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
    # ch.append((cH[-1]*2)//(2**i))
# print(ch)
# print(cH)
# ch = ch[:-1]
# ch = ch[::-1]
# ch[0]*=2
# print(ch)
cH = cH[:-1]
cH.append(cH[-1]*2)
cH = cH[::-1]
# print(cH)
if 0 in cH:
    print(-1)
    exit()
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:-1]):
    # print(n,ch[e],-1)
    if n//2>cH[e]:
        print(-1)
        exit()
    if n  <= cH[e]:
        # print('ans:',ans,'n:',n)
        ans += n+i
        n+=i
    else:
        # print('ans:',ans,'ch:',cH[e],'i:',i)
        ans +=cH[e]+i
        n = cH[e]+i

    # print('ans:',ans,'n:',n)
print(ans+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
al = list(map(int, input().split()))
print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())))
l = 0
n = 1
b = 0
g = np.zeros(N+1)
g[0] = 1-a[0]
for i in range(1, N+1):
    g[i] = (g[i-1]-a[i-1])*2
    if g[i] <= 0:
        l = -1
g[N] = a[N]
for i in range(1, N+1):
    if l<0:
        break
    b = N-i
    if g[b] > g[b+1]+a[b]:
        g[b] = g[b+1]+a[b]
    if g[b] <= 0:
        l = -1
        break
if a[0] != 0 or l == -1:
    print(-1)
else:
    print(int(sum(g)))

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input()) + 1
    A = list(map(int, input().split()))

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

    # max internal node
    MI = [0 for _ in range(N)]
    MI[0] = 1
    for i in range(1, N):
        MI[i] = (MI[i-1] - A[i-1]) * 2
        if MI[i] <= 0 and i != N - 1:
            return -1

    results = [0 for _ in range(N)]
    results[N-1] = min(A[N-1], MI[N-1])
    for i in range(N-2, -1, -1):
        results[i] += min(results[i+1] + A[i], MI[i])
        if results[i] <= 0:
            return -1

    return sum(results)

    # print(MI)
    # print(results)


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