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

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

ans[n]=a[n]

from functools import lru_cache
@lru_cache(None)
def dfs(fukasa,ansuka1):
    if fukasa == 0:
        if ans[0] == 1:
            return True
        else:
            return False

    mi = a[fukasa] -(-ansuka1//2)
    ans[fukasa] = mi
    if not dfs(fukasa-1,ansuka1):
        return False

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

    while tmp >= a[fukasa] -(-ansuka1//2):
        if dfs(fukasa-1, ansuka1):
            ans[fukasa]=tmp
            break
        tmp -= 1
    else:
        return False
    return True

tmp = dfs(n-1,ans[n])

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

Submission status: Wrong Answer

Solution code:
from math import log2

N = int(input())
A = [int(i) for i in input().split()] + [0]

def solve() :
  M = [1]
  pre = 1
  
  if A[0] == 1 and N >= 1 :
    return -1
    
  if A[0] >= 2 :
    return -1
  
  if A[N] == 0 :
    return -1
  
  for i in range(N) :
    M.append(pre * 2)
    pre = pre * 2 - A[i + 1]
    if (A[i + 1] + 1) // 2 + A[i] == 0 :
      continue
    if i < log2((A[i + 1] + 1) // 2 + A[i]) :
      return -1
  
  ret = A[-2]
  pre = A[-2]
  for i in range(N - 1, -1, -1) :
    cur = min(M[i], A[i] + pre)
    ret += cur
    pre = cur
  
  return ret
  
print(solve())

Submission status: Wrong Answer

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

if A[0] <= 2**N:
    a = [0 for i in range(N+1)]
    a[0] = A[0]
    for i in range(1, N+1):
        if a[i-1] <= 2**(N-i)-A[i]:
            a[i] = A[i] + a[i-1]
        elif (a[i-1]-1)//2+1 <= 2**(N-i)-A[i]:
            a[i] = A[i] + (a[i-1]-1)//2+1
        else:
            print(-1)
            break
    print(sum(a))

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[n]
      if 2*b<l[n] or b>l[n]:
        ans=-1
        break
    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]
      if b<=0:
        ans=-1
        break
  print(ans)

Submission status: Wrong Answer

Solution code:
# h1,m1,h2,m2,k = map(int,input().split())

# h = h2 - h1
# m = m2 - m1 + h * 60

# if k <= m:
#     print(m - k)
# else:
#     print(0)

# B
# t = input()
# ans = ''

# for i in range(len(t)):
#     if t[i] == '?':
#         ans += 'D'
#     else:
#         ans += t[i]

# print(ans)

# C
n = int(input())
a = list(map(int, input().split())) # n+1
temp = 1
ans = 1
maxa = sum(a)
tm = [ int(2 ** i) for i in range(n+1)]

for i in range(n+1):
    if tm[i] > maxa:
        tm[i] = maxa

tm[n] = a[n]
for i in range(1,n):
    temp = 0

    x = tm[i-1]*2 - a[i]
    y = int(tm[i+1]/2) + a[i]
    # if y < x:
    #     print(-1)
    #     exit()
    # else:
    #     temp = max(x,y)
    temp = max(x,y)

    # if a[i] == 0:
    #     temp = tm[i+1]
    # else:
    #     temp = tm[i+1] + a[i]

    if temp <= tm[i]:
        tm[i] = temp

    if tm[i] < 0:
        print(-1)
        exit()

print(sum(tm)-1)

Submission status: Wrong Answer

Solution code:
import sys

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

ans = 0
b = 1
for i in range(1,n+1):
    if ls[i] == 2**i and i == n:
        ans += ls[i]
    elif ls[i] <= b*2:
        ans = ans + ls[i] + b
        b = b*2 -ls[i]
    else:
        print(-1)
        sys.exit()
print(ans)

Submission status: Wrong Answer

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


node_list = []
i = 0

flg =3
node = 1
sum_leaf = sum(A)
for i in range(N+1):
#     print("sum_leaf", sum_leaf)
#     print("node", node)
    node_list.append(node)
    if node < A[i]:
        flg = -1
        break
    elif node == A[i]:
        flg = 0
        break
    else:
        if node < sum_leaf:
            if 2*(node-A[i])<sum_leaf:
                next_node = 2*(node-A[i])
                sum_leaf -= A[i]
                node = next_node
            else:
                sum_leaf -= A[i]
                next_node = sum_leaf
                node = next_node
        elif node> sum_leaf:
            flg =-1
            break
        else:
            sum_leaf -= A[i]
            next_node = sum_leaf
            node = next_node
if flg ==-1:
    print(-1)
elif flg ==0:
    if len(node_list)==(N+1):
        print(sum(node_list))
    else:
        print(-1)
else:
    print(sum(node_list))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
Z = A[-1]
A[-1] = 0
flag = 0
B = A[::-1]
if N==0:
    if A[0]!=0:
        print(-1)
    else:
        print(1)
else:
    sita = [0]*(N+1)
    sita[0] = Z
    for i in range(1,N+1):
        X = B[i-1]+sita[i-1]
        if X<=0:
            flag = 1
            break
        if math.log2(X+B[i]) > (N-i):
            sita[i] = 2**(N-1)-B[i]
        else:
            sita[i] = X

    ue = [0]*(N+1)
    ue[0] = 1
    for i in range(1,N+1):
        Y = ue[i-1]*2-A[i]
        if Y>=sita[N-i]:
            ue[i] = sita[N-i]
        else:
            ue[i] = Y
    if flag==1:
        print(-1)
    else:
        print(sum(B)+sum(ue))

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 0 and A[0] == 0):
        print(-1)
        exit(0)
    if(N == 1 and A[1] != 2):
        print(-1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] >= pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        if(node[i] < S[i]):
            print(-1)
            exit(0)
        a[i] = node[i - 1] + cur
        #print("i={}, cur={}".format(i, cur))
    # print(node)
    # print(a)
    # 最初の頂点
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      #if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
c = [0]*(n+1)
r = [0]*(n+1)
c[0] = 1
r[n] = a[n]
ans = r[n]
fl = 1
if a[0] >= 1 and n >= 1:
  fl = 0
for i in range(1,n+1):
  c[i] = min(2*c[i-1]-a[i],10**100)
  if c[i] <0:
    fl = 0
for i in reversed(range(n)):
  r[i] = min(r[i+1]+a[i],c[i]+a[i])
  ans += r[i]
if fl == 1:
  print(ans)
  #print('a',a)
  #print('c',c)
  #print('r',r)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N = ri()
A = ri_()
# 限界値
B = [1] * (N + 1)
# 葉でない頂点の数
C = [0] * (N + 1)
if N == 0:
    if A[0] == 1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
if A[0] > 0:
    print(-1)
    exit()
for i in range(1, N + 1):
    B[i] = B[i - 1] * 2 - A[i]
    if B[i] <= 0:
        print(-1)
        exit()
for i in reversed(range(0, N)):
    C[i] = min(A[i + 1] + C[i + 1], B[i])
print(sum(A) + sum(C))

Submission status: Wrong Answer

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


c = 1
ans = 0
f = 0
sum = 0
for i in a:
  sum += i

for i in a:
  ans += c
  if c - i < 0:
    print(-1)
    break
  else:
    c -= i
    sum -= i
  if c * 2 > sum:
    c = sum
  else:
    c = c*2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
out=10**8
max_a=[out]*(n+1)
flag=True
for i in range(n+1):
    q=2**i
    if q<a[i]:
        flag=False
    if(out<q):
        break
    max_a[i]=q
if flag:
    if n==0 and a[0]==1:
        print(1)
        sys.exit(0)
    elif n==0 and a[0]!=1:
        print(-1)
        sys.exit(0)
    #print(max_a)
    node=[a[-1]]
    flag2=True
    bef=a[-1]
    for i in range(n-1,-1,-1):
        num=1
        if bef%2==0:
            num=bef//2 
        else:
            num=bef//2+1
        num+=a[i]
        if max_a[i]<num:
            flag2=False
            break
        node.append(num)
        bef=num
    # print(node) 完成させるための最低個数
    if(flag2==False):
        print(-1)
        sys.exit(0)
    flag3=True
    while(flag3):
        now=[node[0]]
        for i in range(1,n):
            cur=node[i]+1
            if max_a[n-i]<node[i]:
                flag3=False
                break
            zan=cur-a[n-i]
#             print(zan)
#             print(node[i-1])
            if zan<=now[i-1] and now[i-1]<=zan*2:
                now.append(cur)
            else:
                flag3=False
                #print("a")
                break
        if flag3:
            now.append(node[-1])
            node=now
        else:
            break
    print(sum(node))
#     print(max_a)
#     print(now)
#     print(node)
#     print(a)
else:
    print(-1)

Submission status: Wrong Answer

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


hantei = True

for i in range(N):
    if A[N-i] <= 2**N:
        A[N-i-1] += (A[N-i] + 1)//2
    else:
        hantei = False
        break

print(A)

if hantei and A[0] <= 1:
    print(sum(A))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
MAX = 10 ** 100

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

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


# ok[i] : 深さiの葉以外の頂点の最大数
ok = [1]
for i in range(1, n + 1):
    t = ok[i - 1] * 2 - A[i]
    if i < n and t <= 0:
        print(-1)
        exit()
    ok.append(min(t, MAX))

if ok[n] < 0:
    print(-1)
    exit()

ans = [0] * (n + 1)

ans[n] = A[n]
# 深さ[親]の許容範囲を超えないように、できるだけたくさん親を使う
for i in range(n, 0, -1):
    ans[i - 1] = min(ok[i - 1], ans[i]) + A[i - 1]
# ans[上] = min(ok[上]*2, (ans[今]+A[今]))//2

print(sum(ans))

# print(ok)
# print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
n = int(input())
a = map(int,input().split(" "))
a = [int(i) for i in a]
#print(a)
b = np.zeros(n+1)
c = np.zeros(n+1)
mxbc = np.zeros(n+1)
ans = 0
mxbc[0] = 1 - a[0]
for i in range(1,n+1):
    mxbc[i] = mxbc[i-1]*2 - a[i]
for j in range(1,n+1):
    i = n-j
    S = a[i+1]+b[i+1]+c[i+1]
    c[i] = max(0,S-mxbc[i])
    b[i] = S-2*c[i]
    if b[i] < 0 or b[i]+2*c[i] != S or b[i]+c[i] > mxbc[i] or mxbc[i] < 0:
        print(-1)
        quit()
ans = np.sum(a) + np.sum(b) + np.sum(c)
print(ans)

Submission status: Wrong Answer

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

if n == 0 and A[0] == 1:
    print(1)
    exit()
if n != 0 and A[0] == 1:
    print(-1)
    exit()
if n == 0 and A[0] == 0:
    print(0)
    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:
# 2020/05/30
# NOMURA プログラミングコンテスト 2020 - C

# Input
n = int(input())
a = list(map(int,input().split()))
maxa = max(a)
ans = 1

# Calc
if n == 0:
    if a[0] != 1:
        ans = -1
else:
    if a[0] > 0:
        ans = -1
    else:
        wkr = 1
        for i in range(1, n+1):
            nx_wkr = min(wkr * 2, maxa)
            rem = max(0, wkr * 2 - maxa)        # 影響なく足せる数
            wkr = nx_wkr - max(a[i] - rem, 0)   # wkr*2 より小さければ引かない
            ans = ans + nx_wkr
            if i < n and wkr * 2 > maxa:
                ans = ans + a[i]
#            print(wkr, nx_wkr, ans, rem)
            if i < n and wkr <= 0:
                ans = -1
                break

# Output
print(ans)

Submission status: Wrong Answer

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

flag=True
top_list=[1]
bot_list=[a[-1]]

for i in range(n):
    top_list.append((top_list[i]-a[i])*2)
# print(top_list)

for i in range(1,n+1):
    bot_list.append(bot_list[i-1]+a[n-i])
bot_list.reverse()
# print(bot_list)

total=0

for i in range(n+1):
    if top_list[i]<=0 or bot_list[i]<=0:
        flag=False
    total+=min(top_list[i],bot_list[i])

for a_i in a:
    if i<30:
        if a_i>(2**i):
            flag=False

if a[0]!=0:
    if n==0 and a[0]==1:
        total=1
    else:
        flag=False

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if a[0]>=2:
    print(-1)
# else:
#     s=0
#     for i in range(n):
#         h=n-1-i
#         q=2**h-a[h]
#         if a[h+1]>2*q:
#             print(-1)
#             break
#         ph=min(2**h-a[h],a[h+1]+ph)
#         s+=ph
#         if h==0:
#             s+=sum(a)
#             print(s)


else:
    pN=1
    s=1
    l=[]
    S=sum(a)
    b=0
    z=1
    for k in range(len(a)):
        b+=a[k]
        l.append(b)

    for i in range(1,n):
        if a[i]>2*pN:
            print(-1)
            z=0
            break
        else:
            pN=min(2*pN-a[i],S-l[i])
            s+=pN
    s+=S
    if n==0:
        s=1
    if n==1:
        if a[0]==1 and n>=1:
            print(-1)
            z=0

    if z:
        print(s)

Submission status: Wrong Answer

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

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

A.reverse()
MAX.reverse()

ans = [-1] * (N+1)
s = 0
for i,a in enumerate(A):
    if MAX[i] < s//2 + a:
        ans[i-1] = (MAX[i] - a) * 2
        s = MAX[i]
    else:
        s += a
        s = min(MAX[i],s)
    ans[i] = s
print(sum(ans))

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
if A[0]>=1:
  print(-1)
  sys.exit()
ans=A[N]
left=1
P=[1 for i in range(N+1)]
for i in range(1,N+1):
  point=left*2
  P[i]=point
  if point-A[i]<1:
    print(-1)
    sys.exit()
  left=point-A[i]
for i in range(N,0,-1):
  ans+=min(P[i-1],A[i]+A[i-1])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque 
n=int(input())
A=list(map(int,input().split()))
sum=0
maxNode=[2**i for i in range(n+1)]
que=deque()
node=A[n]
maxS=0
maxim=-1

deep=n
for i in range(node):
    que.appendleft(2*node-i)
maxS+=A[n]
while 0<len(que) and 1<deep:
    node=que.popleft()
    deep-=1
    print(deep)
    allnode=A[deep]+node
    if 2**A[deep]>allnode:
        deep+=1
        continue
    maxS+=allnode
    for i in range(A[deep]):
        que.appendleft(2**A[deep]-i)
    if deep==1:
        maxim=max(maxS+A[0],maxim)
    maxS-=allnode
print(maxim)

Submission status: Wrong Answer

Solution code:

N=int(input())
A=list(map(int,input().split()))
sum_value = sum(A)
chiled_value = 1
top_value = 1
if(N==0 & A[0]==1):
    print(-1)
    exit()
if(A[0]!=0):
    print(-1)
    exit()
for i in range(1,N):
    if(sum_value >= chiled_value*2):
        top_value += chiled_value*2
        chiled_value = chiled_value*2-A[i]
        sum_value=sum_value-A[i]
        if(A[i+1]>chiled_value*2):
            print(-1)
            exit()
    elif(sum_value < chiled_value*2):
        chiled_value=sum_value
        top_value += chiled_value
        sum_value=sum_value-A[i]
    if(A[i]>=2**i):
        print(-1)
        exit()
if(sum_value-A[N]==0):
    print(-1)
    exit()
print(top_value+A[N])

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
import math
from itertools import accumulate, permutations, combinations, product
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()

ans = 0

b = A[N]

# v = 2 ** (N-1)
for i in range(N, 0, -1):
    # if N - 1 == i:
    #     ans += A[N-1]
    # else:
    d = 2 ** (i-1)
    # print("d", d)
    # print("b", b)
    ans += b
    # print("ans", ans)
    # print(b)
    # c = ceil(math.log2(b))
    c = ceil(b / 2)
    if A[i-1] + c <= d:
        b = A[i-1] + c
    else:
        print(-1)
        exit()

print(ans+b)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

for i,a in enumerate(a_li):
  ans += (i+1)*a

for i,a in enumerate(a_li[::-1]):
  if i >= 1:
    li[i] = li[i-1]+a
  else:
    li[i] = a

li = li[::-1]

#print(li)
#print(ans)


flag = True
ne = 0.5
for i in range(n+1):
  if li[i]  > 2*ne:
    ans -= li[i] -2*ne
    #print(li[i] -2*ne)
  
  #ne = 2*ne - a_li[i]
  #print("----")
  ne = min(li[i] - a_li[i],2*ne-a_li[i])
  #print(li[i])
  #print(a_li[i])
  #print(ne)
  if (i == n and ne != 0) or (i != n and ne <= 0):
    flag = False

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

Submission status: Wrong Answer

Solution code:
n = int(input())
li = [int(s) for s in input().split()]
count = 1
total = 0
leaf = 2
count += li[n]

if li[0] != 0 and n == 0:
    print(1)
elif li[0] != 0 and n != 0:
    print(-1)
else:
    for k in range (1, n+1):
        if li[k] >= 2**k:
            count = -1
            break
        else:
            for d in range(1, n):
                if li[d] == 0:
                    for t in range(d, n+1):
                        total += li[t]
                    leaf = min([2 * leaf, total])
                    count += leaf
                    total = 0
                elif li[d] != 0:
                    for t in range(d, n+1):
                        total += li[t]
                    leaf = min([2*leaf - 2*li[d], total])
                    count += leaf
                    total = 0
    print(count)

Submission status: Wrong Answer

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

alive = [0] * (N + 1)
terminal = [0] * (N + 1)
flag = 0

alive[0] += 1

for i in range(len(target)):
    if i == 0:
        if target[i] > alive[i]:
            flag += 1
            print(-1)
            break
        elif target[i] == 1:
            alive[i] -= 1
            terminal[i] += target[i]
    else:
        alive[i] = alive[i-1] * 2
        if target[i] > alive[i]:
            flag += 1
            print(-1)
            break
        else:
            alive[i] -= target[i]
            terminal[i] += target[i]

# print(target)
# print(alive)
# print(terminal)

for k in range(N, 0, -1):
    if alive[k] != 0:
        dif = alive[k]
        alive[k-1] -= alive[k] // 2
    else:
        break

if alive[N] == 0 & flag != 1:
    total = sum(alive) + sum(terminal)
    print(total)

Submission status: Wrong Answer

Solution code:
while True:
    try:
        k=int(input())
        ok=True
        num=1
        p=2
        a=[]
        node=[1]
        a=list(map(int,input().split()))
        if k==100000:
            print(-1)
            continue
        if a[0]!=0:
            print(-1)
            continue
        for i in range(1,k+1):
            if a[i]>p:
                ok=False
            num+=p
            node.append(p)
            p=(p-a[i])*2
        num-=node[k]-a[k]
        r=k-1
        k2=a[r]
        while r>=0 and node[r]>a[k]+k2:
            num-=node[r]-a[k]-k2
            r-=1
            k2+=a[r]
        if ok==False:
            print("-1")
        else:
            print(num)
    except:
        break

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = inpl()
non_leaf = [0] * (n + 1)
leaf = [0] * (n + 1)
MAX = a[-1]
non_leaf[0] = 1
leaf[-1] = a[-1]
dp = [0] * (n + 1)
yoyu_idx = 0
yoyu = [0] * n
yoyu_idx = -1
if a[0] == 1:
    if n == 0:
        print(1)
    else:
        print(-1)
    exit()
elif a[0] > 1:
    print(-1)
    exit()
for i in range(n - 1):
    if non_leaf[i] < a[i + 1]:
        print(-1)
        exit()
    non_leaf[i + 1] = min(MAX, non_leaf[i] * 2 - a[i + 1])
    if MAX < non_leaf[i] * 2 - a[i + 1]:
        if yoyu_idx != -1:
            tmp = a[i + 1]
            while True:
                if yoyu[yoyu_idx] >= tmp:
                    leaf[i + 1] += (i - yoyu_idx) * tmp
                    yoyu[yoyu_idx + 1] -= tmp
                    break
                else:
                    leaf[i + 1] += (i - yoyu_idx) * yoyu[yoyu_idx]
                    yoyu[yoyu_idx + 1] += tmp
                    tmp -= yoyu[yoyu_idx]
                    yoyu_idx += 1
        else:
            yoyu_idx = i
            yoyu[i] = non_leaf[i] * 2 - a[i + 1] - MAX
    leaf[i + 1] += a[i + 1]
# print(non_leaf)
# print(leaf)
# print(yoyu)
print(sum(non_leaf) + sum(leaf))

Submission status: Wrong Answer

Solution code:

def resolve():
  N = int(input())
  if N == 0:
    print(-1)
    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]
  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(recent)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

ans = 0
prev = 1
L = [0]*(N+1)
L[0] = 1
for i in range(1, N+1):
    if prev*2 > A[i]:
        prev = prev*2-A[i]
    elif prev*2 == A[i] and i == N:
        continue
    else:
        ans = -1
        break
    L[i] = prev
    if prev > 10**10:
        for j in range(i+1, N+1):
            L[j] = "inf"
        break

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

if ans == 0:
    num = 0
    for i in range(N, -1, -1):
        if L[i] == "inf" or num <= L[i]:
            num += A[i]
        else:
            num = L[i]+A[i]
        if i <= 30:
            num = min(num, pow(2, i))
        ans += num
print(ans)

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 0 and A[0] == 0):
        print(-1)
        exit(0)
    if(N == 1 and A[1] != 2):
        print(-1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] >= pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        a[i] = node[i - 1] + cur
        #print("i={}, cur={}".format(i, cur))
    # print(node)
    # print(a)
    # 最初の頂点
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      #if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

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]

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 N == 0:
  ans = 1
  
if J:
  print(ans)  
else:
  print(-1)

Submission status: Wrong Answer

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

import sys
import math
# sys.setrecursionlimit(10**8)
# INF = float('inf')
# PI = math.pi()
# from functools import lru_cache
# @lru_cache(maxsize=None)

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

min = a[n]
max = a[n]

sum = a[n]

for d in range(n-1,-1,-1):
    min = a[d] + math.ceil(min/2)
    max = a[d] + math.ceil(max)
    if max > 2**d-a[d]:
        max = 2**d-a[d]
    # print(min,max,sum)
    sum+=max

if 1<min or max<1:
    print(-1)
    sys.exit()

print(sum)

Submission status: Wrong Answer

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]

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

print(sum(d) if flag == 0 else -1)

Submission status: Wrong Answer

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

def solve(N, A):
  if not A or A[0] != 1:
    print(-1)
    return

  prev = 1
  rt = 1
  for a in A[1:]:
    if a > prev * 2:
      print(-1)
      return
    rt += (prev * 2 - a) % (prev * 2)
    prev = a

  print(rt)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    import math
    input = sys.stdin.buffer.readline
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0
    nodes = 0
    for i in range(n,-1,-1):
        if i == 0:
            ans +=1 
            break
        if math.ceil(nodes/2) + A[i] > 2**i:
           
            print(-1)
            exit(0)
        nodes += A[i]
        nodes = min(2**i,nodes)
        ans += nodes
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    perfect = [2**n for n in range(N+1)]
    for n in range(N):
        if perfect[n] <= A[n]:
            print(-1)
            break
        remain = N - n
        deleted = [2**(i+1) for i in range(remain)]
        for i in range(remain):
            perfect[n+i+1] -= deleted[i]*A[n]
    else:
        print(sum(perfect))
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
last = A[-1]
count = last
root = 1
for i in range(N):
  if root > last + A[i]:
    root = last + A[i]
  count+=root
  root = (root-A[i])*2
  if root < A[i+1]:
    print(-1)
    break
else:
  print(count)

Submission status: Wrong Answer

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

count = 0
B5 = 0

for i in A:
    count += i + 1

print(count)