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:
#!/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

    for n in range(1, N+1):
        if A[n] > 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()))

cnt = 0
max_reaf = 2
can = True
for i in range(N+1):
    if i==0:
        if A[i]==0:
            cnt += 1
        else:
            can = False
            break
    else:
        if A[i]>max_reaf:
            can = False
            break

        if i==N:
            cnt += A[i]
        else:
            cnt += max_reaf
            max_reaf -= A[i]
            max_reaf *= 2




if can:
    print(cnt)
else:
    print(-1)

Submission status: Wrong Answer

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

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

top=10**8+9

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<25:
        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 N == 0:
    print(1)
else:
    saidaiA =[]
    oya = 1
    flag = True
    for i in range(len(A)):
        if oya >= 5*10**13:
            ko = 10**14
        else:
            ko = oya *2
        if i == 0:
            ko = 1
        oya = ko - A[i]
        saidaiA.append(ko)
        if oya < 0:
            flag = False
    ans = 0
    # print(saidaiA)
    motikosi = 0
    for i in range(len(A)):
        if A[-i] + motikosi >= saidaiA[-i]:
            ans += saidaiA[-i]
            motikosi = saidaiA[-i]
        else:
            ans += A[-i] + motikosi
            motikosi = A[-i] + motikosi
    if flag == True:
        print(ans)
    else:
        print(-1)

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

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

  node = [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.append(num_of_node)
    else:
      node.append(max_node_in_depth[i])

  print(sum(node))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
a_list_r = a_list[::-1]
ruisekiwa = [a_list_r[0]]
for i in range(1,n+1):
  ruisekiwa.append(ruisekiwa[-1] + a_list_r[i])
ruisekiwa = ruisekiwa[::-1]
max_leaf = a_list[-1]
count = 0
check = True
node = 0
for i in range(n):
  if i == 0:
    if  n == 0 and a_list[0] == 1:
      count = 1
      break
    elif n != 0 and a_list[0] != 0:
      check = False
      break
    else:
      count = 1
      node = 1
  else:
    cand = 2 * node
    if cand < a_list[i]:
      check = False
      break
    node = min(ruisekiwa[i+1],2*node - a_list[i])
    count += node + a_list[i]
if check == False:
  print(-1)
elif 2 * node < a_list[-1]:
  print(-1)
else:
  print(count + a_list[-1])

Submission status: Wrong Answer

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

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 = (n - a) * 2
    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 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 <= 100:
        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)]
    tmp = [1 for i in range(103)]
    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:
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 + 1
        s = MAX[i]
    else:
        s += a
        s = min(MAX[i],s)
    ans[i] = s
print(sum(ans))

Submission status: Wrong Answer

Solution code:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    print(A_N[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()))
ans = 0

if n == 0 and A[0] == 1:
    print(1)
    exit()
elif A[0] == 1:
    print(-1)
    exit()
elif 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:
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:
from sys import stdin

a=int(stdin.readline())
A=stdin.readline().split()
sum=0
for k in range(0,a+1):
    sum+=int(A[k])

sum-=int(A[a])
ver=1
lay=1
K=0
T=0

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

for l in range(0,a):
    if lay-int(A[l])<=0:
        print(-1)
        K=1
        break
    if (lay-int(A[l]))*2-sum+int(A[l])<=int(A[a]):
        lay=(lay-int(A[l]))*2
        ver+=lay
        sum-=int(A[l])
        T=l
    else:
        lay-=int(A[l])
        sum-=int(A[l])
        x=lay-sum-int(A[a])
        if x==0:
           ver+=lay
        else:
           lay=sum+int(A[a])
           ver+=lay
        T=l
        break

if K==0:
    for u in range(T+1,a):
        lay -= int(A[u])
        sum -= int(A[u])
        ver+=lay

if K==0:
    print(ver)

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(sum(non_leaf) + sum(leaf))

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(sum(non_leaf) + sum(leaf))

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)):
    if a[i] >= m_node[i]:
        print("-1", end="")
        exit()
    node = min((node+a[i]), m_node[i])
    total += node

print(total, end="")

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:
import sys

input = lambda: sys.stdin.readline().rstrip()


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

    v = [tuple() for _ in range(N + 1)]
    v[N] = (A[N], A[N])

    for i in range(N - 1, -1, -1):
        low, up = v[i + 1][0], v[i + 1][1]
        up = min(2 ** i, up + A[i])
        if low % 2 == 0:
            low = low // 2 + A[i]
        else:
            low = low // 2 + A[i] + 1
        v[i] = (low, up)

    # print(v)
    for i in range(N):
        low, up = v[i][0], v[i][1]
        low = max(v[i + 1][0], low - A[i])
        up = min(v[i + 1][1], (up - A[i]) * 2)
        v[i + 1] = (low, up)

    ans = 0
    for i in range(N + 1):
        if v[i][0] > v[i][1]:
            print('-1')
            exit()
        ans += v[i][1]

    # print(v)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

l = []

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

for i in range(N):
    if A[i] > A[i+1]+1:
        print(-1)
        sys.exit()

temp = 1
for i in range(N+1):
    l.append(temp-A[i])
    temp = (temp-A[i])*2

ans = 1
node = 0
for i in range(N, 0, -1):
    if l[i-1] >= node + A[i]:
        node += A[i]
        ans += node
    else:
        ans += node + A[i]
        node = l[i-1]

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
edge=[0]*(n+1)
ans=0
edge[0]=1
for i in range(1,n):
    edge[i]=edge[i-1]*2-a[i]
for i in range(n-1,-1,-1):
    bcnt=edge[i+1]+a[i+1]
    if bcnt//2+bcnt%2>edge[i]:
        ans=-1
        break
    if bcnt<edge[i]:
        edge[i]=bcnt
if n>0 and a[0]>0:
    ans=-1
if ans!=-1:
    ans=sum(edge)+sum(a)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
A = list(map(int,input().split()))
leaf= [-1 for i in range(N+1)]
notleaf = [-1 for i in range(N+1)]
flag=0

if N == 0 and A[0] == 1:
    print(1)
elif N != 0 and A[0]>=1:
    print(-1)
else:
    leaf[0]=0
    notleaf[0]=1
    for d in range(1, N+1):
        leaf[d] = A[d]
        notleaf[d] = 2*notleaf[d-1] - leaf[d]
        if notleaf[d]<0:
            flag=1
            print(-1)
            break
    if flag == 1:
        pass
    else:
        sleaf = 0
        for i in range(N+1):
            sleaf += leaf[i]
        
        d1 = 0
        for i in range(N+1):
            d1 += (i+1) * leaf[i]
        
        sleaf -= 1
        for i in range(1,N+1):
            if sleaf>0:
                d1 -= i*( min(sleaf, leaf[i]+notleaf[i] - notleaf[i-1]))
                sleaf -= (leaf[i]+notleaf[i] - notleaf[i-1])
            else:
                break
        print(d1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n = iinput()
a = iarr()

cum = []; sum = 0
for num in a: sum += num; cum.append(sum)

ans = 1
now = 1
for i in range(n):
    next = min(2*(now - a[i]), cum[n]-cum[i])
    now = next
    if n==i and next<0 : ans = -1; break
    if n!=i and next<=0 : ans = -1; break
    ans += next

if a[n] > 2**n: ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log2, floor

def step(n, lis):
  return [l+n for l in lis]

def func(lis):
  if len(lis)==0:
    return -1
  maxval = max(lis)
  lis.pop(lis.index(maxval))
  if maxval==2:
    lis.append(1)
  if maxval>2:
    lis.append(maxval-1)
    lis.append(maxval-2)
  return maxval

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

lis = [0]
count = 0
ans = 0
flag=False
for i in range(N+1):
  count += 1
  if flag:
    break
  if A[i]==0:
    continue
  lis = step(count, lis)
  count=0
  a = A[i]
  #print(i,lis)
  for j in range(a):
    
    res = func(lis)
    #print(i, res, lis)
    if res == -1:
      flag=True
      break
    else:
      ans += res
  
if flag:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

revA = reversed(A)
ans = 0

l = list(accumulate(revA))
for i in range(N+1):
    if l[i] > 2**(N-i):
        if i == 0:
            ans = -1
            break
        l[i] = 2**(N-i)

for i in range(N):
    if 2*(l[N-i]-A[i]) < l[N-i-1]:
        l[N-i-1] = 2*(l[N-i]-A[i])

for i in range(N+1):
    if l[i] > 0:
        ans += l[i]
    else:
        ans = -1
        break

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

if N == 1:
    if A[0] == 0:
        if A[1] == 2:
            ans = 3
        elif A[1] == 1:
            ans = 2
        else:
            ans = -1
    else:
        ans = -1
print(ans)

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
    if level[i-1] < A[i-1]:
        print(-1)
        exit()
    level[i] = min(cur_pow, 2*(level[i-1]-A[i-1]))
if level[-1] < A[-1]:
    print(-1)
    exit()
level[-1] = A[-1]
for i in range(n-1, -1, -1):
    level[i] = min(level[i], level[i+1]+A[i])
    if level[i] < A[i]:
        print(-1)
        exit()
print(sum(level))

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 node
    MN = [0 for _ in range(N)]
    MN[0] = 1
    for i in range(1, N):
        MN[i] = (MN[i-1] - A[i-1]) * 2
        if MN[i] <= 0:
            return -1

    if A[N-1] > MN[N-1]:
        return -1

    results = [0 for _ in range(N)]
    results[N-1] = MN[N-1]
    if results[N-1] <= 0:
        return -1
    for i in range(N-2, -1, -1):
        results[i] += min(results[i+1] + A[i], MN[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:
import sys
N = int(input())
A = list(map(int, input().split()))

l = []

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

for i in range(N):
    if A[i] > A[i+1]+1:
        print(-1)
        sys.exit()
        
temp = 1
for i in range(N+1):
    l.append(temp-A[i])
    temp = (temp-A[i])*2

ans = 1
node = 0
for i in range(N, 0, -1):
    if l[i-1] >= node + A[i]:
        node += A[i]
        ans += node
    else:
        ans += node + A[i]
        node = l[i-1]

print(l)
print(A)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
capa = 1
for i in range(len(A)):
    if A[i] > capa:
        print(-1)
        exit()
    capa = (capa - A[i]) * 2
tree = [1]

for i in range(1, N):
    if tree[i-1] - A[i] < A[-1]:
        
        tree.append(min(tree[i-1]*2, A[-1]+A[i]) - A[i])
    else:
        tree.append(tree[i-1] - A[i])

print(sum(tree) + sum(A))

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()
elif A[0] == 1:
    print(-1)
    exit()
elif n == 0 and A[0] == 0:
    print(0)

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

A = [0] + A[::-1]
#print(A)

d = N
count = 0
sum = 0
for i in range(1, N+2):
    if A[i] + A[i-1]//2 + A[i-1]%2 > 2**d:
        print(-1)
        exit()
    
    #print(A[i], sum, 2**d)
    
    if A[i] + sum <= 2**d:
        sum = A[i] + sum
    elif A[i] + sum > 2**(d+1):
        count -= A[i] + sum - 2**(d+1)
        sum = 2**d
    else:
        sum = 2**d
        
    #print(sum)
    count += sum
    d -= 1

print(count)

Submission status: Wrong Answer

Solution code:

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

internal_max = [1]*(n+1)
internal_max[0] = 1-As[0]

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

depth_sum = [0]*(n+1)
depth_sum[n] = As[n]
judge = False

for i in range(n-1, -1, -1):
    if depth_sum[i+1] > internal_max[i]*2:
        judge = True
        break
    else:
        depth_sum[i] = As[i] + min(internal_max[i], depth_sum[i+1])

judge = True
if judge:
    print(-1)
else:
    print(sum(depth_sum))

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()
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+(n%2!=0)>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())
A=list(map(int,input().split()))
miss=False
leaf=A[-1]
mina=0
maxa=0
maxal=[0]*(N+1)
minal=[0]*(N+1)
for i in range(N):
  maxa=min(maxa+leaf,2**(N-i-1)-A[N-1-i])
  mina=(mina+leaf+1)//2
  if mina>maxa:
    miss=True
    break
  leaf=A[N-1-i]
  maxal[N-i-1]=maxa
  minal[N-i-1]=mina
leaf=A[0]
a=maxal[0]
ans=leaf
for i in range(1,N+1):
  leaf=A[i]
  a=min(a*2-leaf,maxal[i])
  if a==0 and i<N:
    miss=True
    break
  ans+=(a+leaf)
if miss:
  print(-1)
else:
  print(int(ans))

Submission status: Wrong Answer

Solution code:
import io,sys
sys.setrecursionlimit(10**9)

def main():
    n = int(input())
    A = list(map(int,sys.stdin.readline().rstrip().split()))

    maxnode = []
    suma = 0
    for i in range(n+1):
        suma+=A[n-i]
        maxnode.append(suma)
    maxnode.reverse()
    if A[0]!=0:
        print(-1)
        sys.exit()

    ans=1
    temp=1
    for i in range(1,n):
        temp = (temp - A[i-1])*2
        ans+=temp
        if temp - A[i] <= 0:
            print(-1)
            sys.exit()
        if (temp-A[i])*2 > maxnode[i]:
            if i == n-1:
                break
            ans+=sum(maxnode[i+1:])
            break
    
    if i == n-1:
        ans+=A[n]
    
    print(ans)
main()

Submission status: Wrong Answer

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

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

# 成り立つ木が作れるか判定してみる
en = [0]
en[0] = 1

flg = True
for a in A_list:
    tmp = en[-1] - a
    if tmp < 0:
        flg = False
        break
    en.append(tmp * 2)
en = en[:-1]

if not flg:
    print(-1)
    exit()

if en == 0:
    print(res)
    exit()

branch = A_list[-1]
res = A_list[-1]
nodes = en[-1]
for a, ena in zip(A_list[-2::-1], en[-2::-1]):
    branch = min(branch+a, ena)
    res += branch
print(res)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
temp=1
summ=0
cont=0
templist=[1]
for i in range(N+1):
  #print(temp)
  if A[i]<temp:
    if i<N:
      summ+=temp
      temp=2*(temp-A[i])
      templist.append(temp)
    elif i==N:
      summ+=temp
      cont+=1
  elif A[i]==temp:
    if i==N:
      summ+=temp
      #templist.append(temp)
      cont+=1
    else:
      print("-1")
      break
  else:
    print("-1")
    break
    
if cont==1:
  if A[N]==temp:
  	print(summ)
  else:
    #print(templist)
    #print(A)
    comp=A[-1]
    for i in range(N):
      summ-=(templist[-(i+1)]-comp)
      comp+=A[-(i+2)]
      #print(comp)
      #print(templist[-(i+2)])
      #print(summ)
      if comp>templist[-(i+2)]:
        print(summ)
        break