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:
n = int(input())
a = list(map(int, input().split()))

ans = 0

parents = 1

if n == 0:
    if a[0] > 1:
        ans = -1
    else:
        ans = a[0]

parentsls = [0 for _ in range(n+1)]
parentsls[0] = parents

bicapls = [0 for _ in range(n+1)]

for i in range(1, n+1):
    if i != n and parents == 0:
        ans = -1    
        break
    if a[i] > parents*2:
        ans = -1
        break
    else:
        parents = parents*2 - a[i]
        parentsls[i] = parents
    
if ans != -1:
    node = 0
    for i in range(n):
        if parentsls[n-1-i] >= node + a[n-i]:
            ans += node + a[n-i]
            node = node + a[n-i]
        else:
            ans += node + a[n-i]
            node = parentsls[n-1-i]

    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
cnt=0
B1=list(map(int,input().split()))
if n==0:
    print(-1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
B[0] = 1-A[0]
M = 1
i = 1
while i < N:
  B[i] = B[i-1]*2-A[i]
  i += 1
B[-1] = A[-1]
i = N-1
isOK = True
while i >= 0:
  if B[i] < 1 or i > 0 and B[i] > B[i-1]*2:
    isOK = False
    break
  else:
    B[i] = min(B[i], B[i+1])+A[i]
  i -= 1
print(-1 if not isOK else sum(B))

Submission status: Wrong Answer

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

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

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

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

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

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

now_num = 1
now_total = 1
for depth in range(n):
    mov_num = now_num - A[depth]
    #print(mov_num)

    if mov_num > 0:
        now_num = min(mov_num * 2, limit[depth+1])
        now_total += now_num
    else:
        print(-1)
        exit()
print(now_total)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
a = LI()
if n == 0:
    if a[0] == 1 or a[0] == 0:
        print(1)
        quit()
    else:
        print(-1)
        quit()
for i in range(n):
    if a[i] > 2**i - 1:
        print(-1)
        quit()
if a[-1] > 2**n:
    print(-1)
    quit()

lst = [1]
for i in range(1, n+1):
    l = lst[-1] - a[i-1]
    if l <= 0:
        print(-1)
        quit()
    lst.append(2*l)
i = n-1
tmp = a[-1]
ans = 0
lst2 = [a[-1]]
while i >= 0:
    tmp += a[i]
    tmp = min(tmp, 2**i)
    lst2.append(tmp)
    i -= 1
lst2 = lst2[::-1]
for i in range(n+1):
    ans += min(lst[i], lst2[i])
print(ans)

Submission status: Wrong Answer

Solution code:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    print(-1)
    exit()

reversed_A_N = list(reversed(A_N))
for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]
r_reversed_A_N = list(reversed(reversed_A_N))
 
 
r_reversed_A_N[0] = 1
for i in range(N):
    max_next_nodes = (r_reversed_A_N[i] - A_N[i]) * 2 - A_N[i+1]
    if max_next_nodes < 0:
      print(-1)
      exit()
    elif max_next_nodes >= r_reversed_A_N[i+1]:
        break
    else:
        r_reversed_A_N[i+1] = max_next_nodes + A_N[i+1]
 
r_reversed_A_N[i+1] = list(reversed(reversed_A_N))[i+1]# A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
su = sum(a)
# print(su)
l = [su]*(n+1)
for i in range(1,n+1):
    l[i]=l[i-1]-a[i-1]
# print(l)
count=0
x = 0
m=[1]*(n+1)
for j in range(1,n+1):
    m[j] = m[j-1]*2
    if m[j]>l[j]:
        m[j]=l[j]
    if (m[j]<a[j])or(m[j]==a[j] and j!=n):
        # print(m[j],a[j])
        x = 1
        break
    # print(m[j])
    count += m[j]
    m[j] -= a[j]
count+=1

if x==1 or m[0]<=a[0] or n==10**5:
    print(-1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
ok=True
ans=[0]
a=[int(i) for i in input().split()]
#lima=[2**i-a[i] for i in range(n+1)]
a=a[::-1]
#lima=lima[::-1]

for i in range(n+1):
    ans.append(min(a[i]+ans[-1],2**(n-i)-a[i]))
    if ans[-1]<=0:
        ok=False
        break
if ok:
    #print(ans)
    #print(lima)
    print(sum(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys

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

if a[0] != 0 or a[-1] == 0:
    print(-1)
    sys.exit()

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

print(ans)

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(0, N + 1):
    if i > 0:
        B[i] = B[i - 1] * 2 - A[i]
    if i < N and 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))
# print('A:', A)
# print('C:', C)
# print('B:', B)

Submission status: Wrong Answer

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

if l[0]  != 0:
    print('-1')
    sys.exit()
    
count = 1
edge = 1
sum_ = sum(l)
for i in range(1,len(l)-1):
#     print(i-1, edge, count)

    sum_ -= l[i]
    
    if l[i] >= edge *2:
        print('-1')
        sys.exit()
    
    if edge * 2 - l[i] <= sum_:
        count += edge * 2
        edge = edge * 2 -l[i]
#         print(i, 'max', edge,count)
        continue

        
    if edge * 2 - l[i] > sum_:
        count += sum_ + l[i]
        edge = sum_
        
#         print(i, 'notmax', edge,count)
        continue

        
        
#n回目の処理
if not   l[len(l)-1] <= edge * 2:
    print('-1')
    sys.exit()
    
else:
    count +=   l[len(l)-1] 
print(count)

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]
    elif(sum_value < chiled_value*2):
        if(A[i]>=chiled_value*2):
            print(-1)
            exit()
        chiled_value=sum_value
        top_value += chiled_value
        sum_value=sum_value-A[i]
    
print(top_value+A[N])

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
    if sum(A) == 0:
        print('-1')
        return

    elif sum(A) == 1 and A[-1] != 1:
        print('-1')
        return

    if A[N-1] > 2 ** N:
        print('-1')
        return

    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 math import ceil
N = int(input())
A = list(map(int, input().split()))
if(A[0] != 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] > 2**(i - 1)):
        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)

'''

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if A[0] != 0:
    print(-1)
    exit()
A.reverse()
B = []
ans = 0
num = 0
num2 = 0
for i in range(N+1):
    lim = 2**(N-i)
    if A[i] > lim:
        print(-1)
        exit()
    num = min(num+A[i],lim)
    B.append(num)
A.reverse()
B.reverse()
for i in range(N):
    num2 = B[i]-A[i]
    if num2*2 < A[i+1]:
        print(-1)
        exit()
    if num2*2 < B[i+1]:
        B[i+1] = num2*2
print(sum(B))

Submission status: Wrong Answer

Solution code:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    if A_N[0] == 1:
        print(1)
    elif A_N[0] == 0:
        print(0)
    else:
        print(0)
    exit()

reversed_A_N = list(reversed(A_N))
for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]
r_reversed_A_N = list(reversed(reversed_A_N))
 
 
r_reversed_A_N[0] = 1
for i in range(N):
    max_next_nodes = (r_reversed_A_N[i] - A_N[i]) * 2 - A_N[i+1]
    if max_next_nodes < 0:
      print(-1)
      exit()
    elif max_next_nodes >= r_reversed_A_N[i+1]:
        break
    else:
        r_reversed_A_N[i+1] = max_next_nodes + A_N[i+1]
 
r_reversed_A_N[i+1] = list(reversed(reversed_A_N))[i+1]# A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [1]
if a[0] != 0:
    print(-1)
    exit()
cnt = 2
ans = 1
for i in range(1, n+1):
    if i != n:
        if a[i] >= cnt:
            ans = -1
            break
        l.append(a[i]+(cnt-a[i])//2)
        ans += cnt
        cnt -= a[i]
        cnt *= 2
    if i == n:
        if cnt < a[i]:
            ans = -1
        else:
            ans += cnt
            l.append(cnt//2)
if ans == -1:
    print(ans)
elif cnt == a[i]:
    print(ans)
else:
    for i in range(n, -1, -1):
        if i == 0:
            break
        if cnt - l[i] <= a[n]:
            ans += (cnt - a[n]) * (-n-1+i)
            cnt = a[n]
            break
        else:
            cnt -= l[i]
            ans += l[i] * (-n-1+i)
    print(ans)

Submission status: Wrong Answer

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

# 木が存在するかチェックをして，後でノード数を計算する
# チェック-1辺
pre_a = A[0]
if N == 0 and pre_a == 1:
    print(1)
    sys.exit()
elif N == 0 and pre_a != 1:
    print(-1)
    sys.exit()
elif pre_a != 0:
    print(-1)
    sys.exit()

flag = True
for i in range(1, N+1):
    cur_a = A[i]
    if i <= 30:
        sqrt_d = 2 ** i - 2 * pre_a
    else:
        break
    if i == N:
        if cur_a <= sqrt_d:
            continue
        else:
            flag = False
            break
    else:
        if cur_a < sqrt_d:
            continue
        else:
            # print(cur_a)
            flag = False
            break
    pre_a = pre_a * 2 + cur_a
# INF = 10**13
if flag:
    tmp = [1 for i in range(32)]
    ans = A[N]
    pre_a = A[N]
    for i in range(N-1, 0, -1):
        cur_a = A[i]
        if i <= 30:
            sqrt_d = 2**i - A[i-1]*2
            diff = min(cur_a + pre_a, sqrt_d)
            tmp[i] = diff
        else:
            diff = cur_a + pre_a
            # sqrt_d = INF
        ans += diff
        pre_a = diff
    ans += 1
    tmp_sum = 0
    for i in range(1, min(N+1, 31)):
        # print(tmp[i])
        if tmp[i] > (tmp[i-1]-A[i-1]) * 2:
            # print('aaa', tmp[i] - (tmp[i-1]-A[i-1]) * 2)
            ans -= (tmp[i] - (tmp[i-1]-A[i-1]) * 2)
            tmp[i] -= (tmp[i] - (tmp[i-1]-A[i-1]) * 2)
        # tmp_sum = tmp_sum * 2 + A[i] * 2
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
a = LI()
if n == 0:
    if a[0] == 0:
        print(1)
        quit()
    else:
        print(-1)
        quit()
for i in range(n):
    if a[i] > 2**i - 1:
        print(-1)
        quit()
if a[-1] > 2**n:
    print(-1)
    quit()

lst = [1]
for i in range(1, n+1):
    l = lst[-1] - a[i-1]
    if l <= 0:
        print(-1)
        quit()
    lst.append(2*l)
i = n-1
tmp = a[-1]
ans = 0
lst2 = [a[-1]]
while i >= 0:
    tmp += a[i]
    tmp = min(tmp, 2**i)
    lst2.append(tmp)
    i -= 1
lst2 = lst2[::-1]
for i in range(n+1):
    ans += min(lst[i], lst2[i])
print(ans)

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()))
        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:
from itertools import *
n,*a=map(int,open(0).read().split())
b=list(accumulate(a[::-1]))
b=b[::-1][1::]
c=[1]*n
if a[0]!=0:
    print(-1)
    exit()
for i in range(1,n):
    c[i]=min(c[i-1]*2-a[i],b[i])
    if c[i-1]*2-a[i]<1 and i!=n:
        print(-1)
        exit()
print(sum(a+c))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
if N == 0:
  if A[0] == 0:
    ans = 1
  else:
    ans = -1
    
elif N == 1:
  if A == [0,2]:
    ans = 3
  else:
    ans = -1
 
else:
  TOP = [0 for _ in range(len(A))]
 
  impossible =0
  TOP[0] = 1
 
  for n in range(len(A)-1):
    max_TOP = TOP[n] * 2 - A[n+1]
 
 
    if n != len(A)-2:
      if max_TOP <= 0:
        impossible = 1
        break
      else:
        TOP[n+1] = max_TOP
    else:
      if max_TOP < 0:
        impossible = 1
        break
      else:
        TOP[-1] = TOP[-2]*2
 
  if impossible == 0:
    ans = sum(TOP)+sum(A)-TOP[-1]
 
    cuts = TOP[N] - A[N] - TOP[N-1]
    for n in range(N,2,-1):
      if cuts <= 0:
        break
      else:
        ans -= cuts
        cuts = cuts- TOP[n-2]
  else:
    ans = -1
  
  
print(ans)

Submission status: Wrong Answer

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

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

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:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    if A_N[0] == 1:
        print(1)
    elif A_N[0] == 0:
        print(0)
    else:
        print(1)
    exit()

reversed_A_N = list(reversed(A_N))
for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]
r_reversed_A_N = list(reversed(reversed_A_N))
 
 
r_reversed_A_N[0] = 1
for i in range(N):
    max_next_nodes = (r_reversed_A_N[i] - A_N[i]) * 2 - A_N[i+1]
    if max_next_nodes < 0:
      print(-1)
      exit()
    elif max_next_nodes >= r_reversed_A_N[i+1]:
        break
    else:
        r_reversed_A_N[i+1] = max_next_nodes + A_N[i+1]
 
r_reversed_A_N[i+1] = list(reversed(reversed_A_N))[i+1]# A_N[-1]
print(sum(r_reversed_A_N))

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 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
if N == 0 and A[0] == 1:
    ans = 1
elif N ==0 and A[0] != 1:
    ans = -1
print(ans)

Submission status: Wrong Answer

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

if n == 0:
  flag=1
  if a[0] == 1:
    print(1)
  else:
    print(-1)
else:
  accum = [0]*n
  new_list = list(reversed(a))
  accum[0] = new_list[0]
  for i in range(n-1):
      accum[i+1] = accum[i] + new_list[i+1]
  hat = list(reversed(accum))
  #print(hat)

  b = [1]*(n+1)
  flag = 0
  cand = 0

  for i in range(1,n+1):
    cand = (b[i-1]-a[i-1])*2
    if cand < 1:
      flag = 1
      break
    if cand > hat[i-1]:
      b[i] = hat[i-1]
    else:
      b[i] = cand

  #print(b)
  if flag != 1:
    print(sum(b))
  else:
    print(-1)

Submission status: Wrong Answer

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

count = 0
B1 = 0

for i in A:
    count += i + 1

print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
saidai=[1]*(N+1)
back=[0]*(N+1)
if N!=0:
    ans=0
    saidai[0]=1
    for n in range(1,N+1):
        saidai[n]=(saidai[n-1]-A[n-1])*2
        if saidai[n]<=0:
            ans=-1
    for n in range(N+1):
        a=N-n
        if a==N:
            back[a]=A[a]
        else:
            back[a]=back[a+1]+A[a]
    if ans!=-1:
        c=0
        for n in range(N+1):
            a=N-n
            if c==0:
                if saidai[a]>back[a]:
                    ans+=back[a]
                else:
                    ans+=saidai[a]
                    c=1
            else:
                ans+=saidai[a]
    print(ans)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
n_l = [1]
n = 1
A = [int(a) for a in input().split()]
for i in range(1,N+1):
    a = A[i-1]
    n = min((n - a) * 2, 10**8)
    n_l.append(n)
    if n <= 0:
        Good = False
        break
if n > A[N]:
    counter = A[N]
    m = A[N]
    Good = True
else:
    Good = False
if Good:
    for i in range(N-1,-1,-1):
        n = n_l[i]
        m = min(m+A[i],n)
        counter += m
    print(counter)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import math

def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

def read_int_list():
    return list(map(int,input().split(' ')))

def read_s_list_loop(n):
    return [input() for _ in range(n)]


N = int(input())
An = read_int_list()

remain_trees = An[N]
amount = remain_trees
'''
tree = [ [] for _ in range(N)]
tree_count = 0
'''
threads_holds = [0]*(10**5+1)
threads_holds[0] = 1
tree = [0]*(N+1)
tree[N] = remain_trees
for i in range(1,10**5+1):
    threads_holds[i] = threads_holds[i-1]*2

for i in reversed(range(1,N)):
    shoud_end = An[i]
    
    #ありえない数なので減らす必要ある
    # 1/2以下 + should_endがthread_hold以上の時はprint -1
    if threads_holds[i] < int(math.ceil(remain_trees/2.0)) + shoud_end:
        print(-1)
        exit(0)
    else:
        if i != 0:
            next_should_end = An[i-1]
            max_val_for_next = (threads_holds[i-1] - next_should_end)*2
            if max_val_for_next < int(math.ceil(remain_trees/2.0)) + shoud_end:
                print(-1)
                exit(0)
            remain_trees = min(max_val_for_next,remain_trees + shoud_end) 
    amount += remain_trees
    tree[i] = remain_trees
if remain_trees <= (threads_holds[0] - An[0])*2:
    print(amount+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# わからん！記念受験
n = int(input())
A = list(map(int, input().split()))
free_cnt = 1
henpin_num = 0
ans = 0
for i, a in enumerate(A):
    if free_cnt < a:
        print(-1)
        exit()
    ans += free_cnt
    if i == n:
        henpin_num = free_cnt-a
    next_free_up = free_cnt-a
    free_cnt = 2*next_free_up

print(ans)

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
elif tree[-1]<1:
  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
  elif bot[d]<top[d+1]<bot[d+1]:
    splice=d+1

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:
#!/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
    if sum(A) == 0:
        print('-1')
        return

    elif sum(A) == 1 and A[-1] != 1:
        print('-1')
        return

    if A[N-1] > 2 ** N:
        print('-1')
        return

    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()))
ans = 0
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N):
    dp[i+1] = min((dp[i]-A[i]) * 2, 10000000000000)
    if dp[i+1] < A[i]:
        print(-1)
        exit()
if(dp[N] < A[N]):
    print(-1)
    exit()
S = [0 for _ in range(N+1)]
S[0] = A[N]
for i in range(1, N+1):
    S[i] = S[i-1] + A[N-i]
for i in range(N+1):
    ans += min(S[N-i], dp[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

if a[0] != 0 or a[-1] == 0:
    print(-1)
    sys.exit()

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

print(ans)

Submission status: Wrong Answer

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

count = 0
B = 0

for i in A:
    count += i + 1

print(count)

Submission status: Wrong Answer

Solution code:
depth = int(input()) 
leaves = list(map(int, input().split(" ")))
limited = []
limited_a = []

def solve (depth) :
    _min = _max = 0
    cur = 1
    i = 0 

    while i <= depth :
        limited_a.append( cur )
        if cur <= 0 and leaves[i] != 0 :
            return False
        cur=(cur-leaves[i])*2
        i+=1 

    i = depth
    while i >= 0 :
        if i==depth: 
            limited.append(leaves[i])
            _max = leaves[i]
            _min = (leaves[i]+1)//2
        else :
            _max = min(limited_a[i], _max+leaves[i])
            _min = (_min+leaves[i]+1)//2
            if _max < _min :
                return False 
            limited.append(_max)
        i -= 1
        cur = (cur-leaves[i])*2
    return True

if solve(depth) :
    print(sum(limited))
else :
    print (-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
B[0] = 1-A[0]
M = 1
i = 1
while i < N:
  B[i] = B[i-1]*2-A[i]
  i += 1
B[-1] = A[-1]
i = N-1
isOK = True
while i >= 0:
  if B[i] < 1:
    isOK = False
    break
  else:
    B[i] = min(B[i], B[i+1])+A[i]
  i -= 1
print(-1 if not isOK else sum(B))

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]
    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()
print(top_value+A[N])

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]

def dfs(fukasa):
    if fukasa == 0:
        if ans[fukasa] == 1:
            return True
        else:
            return False

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

    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)