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 itertools
N = int(input())
A = [int(_) for _ in input().split()]
if A[0] != 0:
    if N == 0 and A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
ans = 1
n = 1
if A[0] > 1:
    print(-1)
    exit()
cumr = list(itertools.accumulate(A[::-1]))[::-1]
for i in range(1, N + 1):
    minn = n - A[i - 1]
    n = min(2 * minn, cumr[i])
    if n>=minn:
        ans += n
    else:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
if A[0] != 0:
    if N == 0 and A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
ans = 1
n = 1
if A[0] > 1:
    print(-1)
    exit()
cumr = list(itertools.accumulate(A[::-1]))[::-1]
for i in range(1, N + 1):
    minn = n - A[i - 1]
    n = min(2 * (n - A[i - 1]), cumr[i])
    ans += n
    if 0 <= minn <= n:
        continue
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
if A[0] != 0:
    if N == 0 and A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
ans = 1
n = 1
if A[0] > 1:
    print(-1)
    exit()
cumr = list(itertools.accumulate(A[::-1]))[::-1]
for i in range(1, N):
    minn = n - A[i - 1]
    n = min(2 * (n - A[i - 1]), cumr[i])
    ans += n
    if 0 <= minn <= n:
        continue
    print(-1)
    exit()
if n <= A[-1] <= 2 * n:
    ans += A[-1]
    print(ans)
else:
    print(-1)
    exit()

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
if A[0] != 0:
    if N == 0 and A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
ans = 1
n = 1
if A[0] > 1:
    print(-1)
    exit()
cumr = list(itertools.accumulate(A[::-1]))[::-1]
for i in range(1, N + 1):
    n = min(2 * (n - A[i - 1]), cumr[i])
    ans += n
    if n < 0:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
if A[0] != 0:
    if N == 0 and A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()

ans = 1
n = 1
cumr = list(itertools.accumulate(A[::-1]))[::-1]
for i in range(1, N + 1):
    n = min(2 * (n - A[i - 1]), cumr[i])
    ans += n
    if n < 0:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
if A[0] == 1 and N == 0:
    print(1)
    exit()
ans = 1
n = 1
cumr = list(itertools.accumulate(A[::-1]))[::-1]
for i in range(1, N + 1):
    n = min(2 * (n - A[i - 1]), cumr[i])
    ans += n
    if n < 0:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
ans=sum(arr)
if n==0:
  if arr[0]==0:
    print(-1)
  else:
    print(1)
  exit()
for i in range(n):
  if i<=30 and arr[i]>=2**i:
    print(-1)
    exit()
if n<=30 and arr[n]>2**n:
  print(-1)
  exit()
maxs=[0]*(n+1)
maxs[0]=1
for i in range(1,n):
  maxs[i]=2*maxs[i-1]-arr[i]
tmp=arr[n]
for i in range(n-1,-1,-1):
  maxs[i]=min(maxs[i],tmp)
  tmp+=arr[i]
mins=[0]*(n+1)
for i in range(n-1,-1,-1):
  mins[i]=(mins[i+1]+arr[i+1]+1)//2
for i in range(n):
  if maxs[i]<mins[i]:
    print(-1)
    exit()
ans+=sum(maxs)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
ans=sum(arr)
if n==0:
  if arr[0]==0:
    print(-1)
  else:
    print(1)
  exit()
maxs=[0]*n
maxs[0]=1
if arr[0]>=1:
  print(-1)
  exit()
for i in range(1,n):
  maxs[i]=2*maxs[i-1]-arr[i]
  if i<=30 and arr[i]>=2**i:
    print(-1)
    exit()
maxs[n-1]=min(maxs[n-1],arr[n])
tmp=arr[n]
for i in range(n-2,-1,-1):
  tmp+=arr[i+1]
  maxs[i]=min(maxs[i],tmp)
ans+=sum(maxs)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
ans=sum(arr)
if n==0:
  if arr[0]==0:
    print(-1)
  else:
    print(1)
  exit()
maxs=[0]*n
maxs[0]=1
if arr[0]>=1:
  print(-1)
  exit()
for i in range(1,n):
  maxs[i]=2*maxs[i-1]-arr[i]
  if arr[i]>=2**i:
    print(-1)
    exit()
maxs[n-1]=min(maxs[n-1],arr[n])
tmp=arr[n]
for i in range(n-2,-1,-1):
  tmp+=arr[i+1]
  maxs[i]=min(maxs[i],tmp)
ans+=sum(maxs)
print(ans)

Submission status: Wrong Answer

Solution code:
print(-5)

Submission status: Wrong Answer

Solution code:
*a,=map(int,[*open(0)][1].split())
c=[s:=0]
for i in a[:0:-1]:c+=c[-1]+i,
b=1
for i in a:
  s+=b
  b=min(c.pop(),(b-i)*2)
print(s)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    l = [0]*(n+1)
    l[n] = (A[n], A[n])
    for i in reversed(range(1, n+1)):
        l[i-1] = (max(max(1, l[i][0]//2)+A[i-1], 1), l[i][1]+A[i-1])

    if 1 not in range(l[0][0], l[0][1]+1):
        print(-1)
    else:
        ans = [0]*(n+1)
        ans[0] = 1
        cnt = 1
        for i in range(n):
            ans[i+1] = min((ans[i]-A[i])*2, l[i+1][1])
        print(sum(ans))


resolve()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n = Ii()
a = Li()
b = [0]*(n+1)
bm = [0]*(n+1)
b[0] = 1
if a[0] > 1:
  print(-1)
  exit(0)
bm[-1] = a[-1]
for i in range(1,n+1):
  bm[-1-i] = bm[-i]+a[-i-1]
  b[i] = (b[i-1]-a[i-1])*2
b = np.array(b)
bm = np.array(bm)
b = np.amin([[b],[bm]], axis=0)
if a[-1] != b[-1,-1]:
  print(-1)
  exit(0)
if np.any(b <= 0):
  print(-1)
  exit(0)
print(np.sum(b))
print(b[-1,-1])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n = Ii()
a = Li()
b = [0]*(n+1)
bm = [0]*(n+1)
b[0] = 1
bm[-1] = a[-1]
for i in range(1,n+1):
  bm[-1-i] = bm[-i]+a[-i-1]
  b[i] = (b[i-1]-a[i-1])*2
b = np.array(b)
bm = np.array(bm)
c = np.amin([[b],[bm]], axis=0)
if np.any(c <= 0):
  print(-1)
else:
  print(np.sum(c))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n = Ii()
a = Li()
b = [0]*(n+1)
bm = [0]*(n+1)
b[0] = 1
bm[-1] = a[-1]
for i in range(1,n+1):
  bm[-1-i] = bm[-i]+a[-i-1]
  b[i] = (b[i-1]-a[i-1])*2
b = np.array(b)
bm = np.array(bm)
c = np.amin([[b],[bm]], axis=0)

if np.any(c == 0):
  print(-1)
else:
  print(np.sum(c))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n = Ii()
a = Li()
b = [0]*(n+1)
bm = [0]*(n+1)
b[0] = 1
bm[-1] = a[-1]
for i in range(1,n+1):
  bm[-1-i] = bm[-i]+a[-i-1]
for i in range(1,n+1):
  b[i] = (b[i-1]-a[i-1])*2
b = np.array(b)
bm = np.array(bm)
c = np.amin([[b],[bm]], axis=0)

if np.any(c == 0):
  print(-1)
else:
  print(np.sum(c))

Submission status: Wrong Answer

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

lim = [0]*(n+1)
aa = 0
for i in range(n+1):
    aa += a[n-i]
    lim[n-i] = aa
    
if n == 0:
    if a[0] != 1:
        print(-1)
        sys.exit()
    else:
        print(1)
        sys.exit()
        
if a[0] != 0:
    print(-1)
    sys.exit()
    
ha = [[0]*(n+1) for i in range(2)]
ha[0][0] = 1
ha[1][0] = 1
for i in range(n):
    ha[1][i+1] = min(ha[0][i]*2 , lim[i+1])
    ha[0][i+1] = ha[1][i+1] - a[i+1]
    if ha[0][i+1] <= 0 and i != n-1:
        print(-1)
        sys.exit()
        
print(sum(ha[1]))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    # verification
    x = 1
    mx = [0] * (N+1)
    for i, a in enumerate(A):
        if i != N and x <= a:
            print(-1)
            return
        x -= a
        mx[i] = x
        x *= 2
    ans = 0
    edge = 0
    for i in range(N+1)[::-1]:
        a = A[i]
        edge = min(edge, mx[i])
        ans += edge + a
        edge += a
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def error():
    print(-1)
    quit()

n = inp()
a = inpl()
if n == 0 and sum(a) == 1:
    print(1)
can = [0] * (n+1); can[0] = 1
b = [0] * (n+1)
res = [0] * (n+1)

if a[0] != 0:
    error()

for i in range(n):
    can[i+1] = can[i]*2 - a[i+1]
    if can[i+1] < 0:
        error()
can[-1] = 0
b[-1] = 0
res[-1] = a[-1]
for i in range(n)[::-1]:
    b[i] = min(res[i+1], can[i])
    res[i] = a[i] + b[i]
print(sum(res))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def error():
    print(-1)
    quit()

n = inp()
a = inpl()
if n == 0:
    error()
can = [0] * (n+1); can[0] = 1
b = [0] * (n+1)
res = [0] * (n+1)

if a[0] != 0:
    error()

for i in range(n):
    can[i+1] = can[i]*2 - a[i+1]
    if can[i+1] < 0:
        error()
can[-1] = 0
b[-1] = 0
res[-1] = a[-1]
for i in range(n)[::-1]:
    b[i] = min(res[i+1], can[i])
    res[i] = a[i] + b[i]
print(sum(res))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def error():
    print(-1)
    quit()

n = inp()
a = inpl()
can = [0] * (n+1); can[0] = 1
b = [0] * (n+1)
res = [0] * (n+1)

if a[0] != 0:
    error()

for i in range(n):
    can[i+1] = can[i]*2 - a[i+1]
    if can[i+1] < 0:
        error()
can[-1] = 0
b[-1] = 0
res[-1] = a[-1]
for i in range(n)[::-1]:
    b[i] = min(res[i+1], can[i])
    res[i] = a[i] + b[i]
print(sum(res))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N=int(input())

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

M=[0 for i in range(N+1)]
M[0]=1
if N==0:
    if L[0]==1:
        print(1)
    else:
        print(-1)
if L[0]==1:
    print(-1)
    exit()

for i in range(1,N+1):
    M[i]=M[i-1]*2-L[i]
    if M[i]<0:
        print(-1)
        exit()
#print(L)
#print(M)

M[-1]=0
for i in range(1,N+1):
    if M[-1-i]<(M[-i]+L[-i]+1)//2:
        print(-1)
        exit()
    elif (M[-i]+L[-i])>=M[-1-i] and M[-1-i]>=(M[-i]+L[-i]+1)//2:
        continue
    else:
        M[-1-i]=(M[-i]+L[-i])
#print(L)
#print(M)
print(sum(L)+sum(M))

Submission status: Wrong Answer

Solution code:
N = int(input())  # 深さはN+1
A = list(map(int, input().split()))  # 長さN+1

# 後ろから構築していく
if A[-1] > 2**N:
    print(-1)
    exit()
limit = [A[-1]]
for i in range(N-1, -1, -1):
    if A[i] > 2**i:
        print(-1)
        exit()
    limit.append(min(limit[-1] + A[i], 2**i))
limit.reverse()

# 頭から構築していく
tree = [1]
if A[0] != 0:
    if A[0] == 1 and N == 0:
        print(1)
    else:
        print(-1)
    exit()

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

print(sum(tree))

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.sum(A)-np.cumsum(np.append(0, A[:len(A)-1]))
v=0
k=0
for i in range(N+1):
  if i==0:
    if N==0 and A[0]==1:
      k=1
    elif A[0]==0:
      k=1
    else:
      print(-1)
      break
  if i==N:
    if B[i]<=2*(k-A[i-1]):
      k=B[i]
    else:
      k=0
      print(-1)
      break
  else:
    k=min(2*(k-A[i-1]),B[i])
    if k<=0:
      print(-1)
      break
  v+=k
if k>0:
  print(v)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.sum(A)-np.cumsum(np.append(0, A[:len(A)-1]))
v=0
k=0
for i in range(N+1):
  if i==0:
    if N==0 and A[0]==1:
      k=1
    elif A[0]==0:
      k=1
    else:
      print(-1)
      break
  else:
    k=min(2*(k-A[i-1]),B[i])
  if k<=0:
    print(-1)
    break
  v+=k
if k>0:
  print(v)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.sum(A)-np.cumsum(np.append(0, A[:len(A)-1]))
v=0
k=0
for i in range(N+1):
  if i==0:
    k=1
  else:
    k=min(2*(k-A[i-1]),B[i])
  if k<=0:
    print(-1)
    break
  v+=k
if k>0:
  print(v)

Submission status: Wrong Answer

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

s = 1
S = 1
if a[0] >= 1 and len(a) > 1:
    S = -1
else:
    for i in range(1,n+1):
        if a[i] > 2*s:
            S = -1
            break
        if s*2 <= N:
            S += s*2
            s += s - a[i]
        else:
            S += N
            s += N - s - a[i]
        N -= a[i]
print(S)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
# import math
from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


n = int(input())
A = list(map(int, input().split()))
sA = list(itertools.accumulate(A[::-1]))[::-1]
# print(sA)

num = 0
par = 1
for i in range(n+1):
    tmp_num = min(par, sA[i])
    if tmp_num <= 0:
        print(-1)
        exit()
    # print(tmp_num)
    num += tmp_num
    par = 2*(tmp_num-A[i])

print(num)

Submission status: Wrong Answer

Solution code:
import math

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

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

    limit_v = [0]*(n+1)
    limit_v[0] = 1
    for i in range(1, n+1):
        curr_limit_v = (limit_v[i-1] - A[i-1])*2
        limit_v[i] = curr_limit_v


    v_cnt = [0]*(n+1)
    v_cnt[n] = min(limit_v[n], A[n])
    ans = 0
    for i in range(n-1,0,-1):
        leaf = A[i]
        max_not_leaf = v_cnt[i+1]
        min_not_leaf = v_cnt[i+1]//2 + v_cnt[i+1]%2

        curr_max_v = max_not_leaf + leaf
        curr_min_v = min_not_leaf + leaf

        if limit_v[i] < curr_min_v:
            print(-1)
            return

        v_cnt[i] = min(limit_v[i], curr_max_v)

    v_cnt[0] = 1
    ans = sum(v_cnt)
    if ans == 0: 
        ans = -1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 1:
            print(1)
            exit()
        else:
            end()
    elif a[0]!=0:
        end()

    b = [0]*(n+1)
    for i in range(n,-1,-1):
        if i == n:
            b[i] = a[i]
        else:
            b[i] = b[i+1]+a[i]

    for i in range(n+1):
        if i==0:
            b[i] = min(1,b[i])
        else:
            b[i] = min(2**i,b[i])
        if i!=n and i!=0:
            b[i] = min(2*(b[i-1]-a[i-1]),b[i])
        if b[i]<a[i]:
            end()
    print(sum(b))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 1:
            print(1)
            exit()
        else:
            end()
    elif a[0]!=0:
        end()
    max = [0]*(n+1)
    for i in range(n,-1,-1):
        if i == n:
            max[i] = a[i]
        else:
            max[i] = (max[i+1]+a[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-a[i-1]),max[i])
        if max[i]<a[i]:
            end()
    print(sum(max))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    deq = deque(LI())
    if n==0:
        if deq[0] == 0:
            print(1)
            exit()
        else:
          end()
    if deq[0]!=0:
        end()
    max = deque()
    for i in range(n,-1,-1):
        if i == n:
            max.appendleft(deq[i])
        else:
            max.appendleft(max[0]+deq[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-deq[i-1]),max[i])
        if max[i]<deq[i]:
            print(-1)
            exit()
    print(sum(max))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    deq = deque(LI())
    if n==0:
        if deq[0] == 0:
            print(1)
            exit()
        else:
          end()
    if deq[0]!=0:
        end()
    max = deque()
    for i in range(n,-1,-1):
        if 2**i<deq[i]:
            end()
        if i == n:
            max.appendleft(deq[i])
        else:
            max.appendleft(max[0]+deq[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-deq[i-1]),max[i])
        if max[i]<deq[i]:
            print(-1)
            exit()
    print(sum(max))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 0:
            print(1)
            exit()
    elif a[0]!=0:
        end()
    max = [0]*(n+1)
    for i in range(n,-1,-1):
        if 2**i<a[i]:
            end()
        if i == n:
            max[i] = a[i]
        else:
            max[i] = (max[i+1]+a[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-a[i-1]),max[i])
        if max[i]<a[i]:
            print(max[i],a[i])
            end()
    print(sum(max))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 0:
            print(1)
            exit()
    elif a[0]!=0:
        end()
    max = [1]*(n+1)
    for i in range(n,0,-1):
        if 2**i<a[i]:
            end()
        if i == n:
            max[i] = a[i]
        else:
            max[i] = (max[i+1]+a[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-a[i-1]),max[i])
        if max[i]<a[i]:
            print(max[i],a[i])
            end()
    print(sum(max))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 0:
            print(1)
            exit()
    elif a[0]!=0:
        end()
    max = [1]*(n+1)
    for i in range(n,0,-1):
        if 2**i<a[i]:
            end()
        if i == n:
            max[i] = a[i]
        else:
            max[i] = (max[i+1]+a[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=0:
            max[i] = min(2*(max[i-1]-a[i-1]),max[i])
        if max[i]<a[i]:
            print(max[i],a[i])
            end()
    print(sum(max))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    deq = deque(LI())
    if n==0:
        if deq[0] == 0:
            print(1)
            exit()
    if deq[0]!=0:
        end()
    max = deque()
    for i in range(n,-1,-1):
        if 2**i<deq[i]:
            end()
        if i == n:
            max.appendleft(deq[i])
        else:
            max.appendleft(max[0]+deq[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-deq[i-1]),max[i])
        if max[i]<deq[i]:
            print(-1)
            exit()
    print(sum(max))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def end():
    print(-1)
    exit()

def main():
    n = I()
    deq = deque(LI())
    if n==0:
        if deq[0] == 1:
            print(1)
            exit()
        else:
            end()
    elif deq[0]!=0:
        end()
    max = deque()
    for i in range(n,-1,-1):
        if 2**i<deq[i]:
            end()
        if i == n:
            max.appendleft(deq[i])
        else:
            max.appendleft(max[0]+deq[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-deq[i-1]),max[i])
    print(sum(max))
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def end():
    print(-1)
    exit()

def main():
    n = I()
    deq = deque(LI())
    if n==0:
        if deq[0] == 0:
            print(1)
            exit()
    if deq[0]!=0:
        end()
    max = deque()
    for i in range(n,-1,-1):
        if 2**i<deq[i]:
            end()
        if i == n:
            max.appendleft(deq[i])
        else:
            max.appendleft(max[0]+deq[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-deq[i-1]),max[i])
    print(sum(max))
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def end():
    print(-1)
    exit()

def main():
    n = I()
    deq = deque(LI())
    if deq[0]!=0:
        end()
    max = deque()
    for i in range(n,-1,-1):
        if 2**i<deq[i]:
            end()
        if i == n:
            max.appendleft(deq[i])
        else:
            max.appendleft(max[0]+deq[i])
    for i in range(n+1):
        if 2**i<max[i]:
            max[i] = 2**i
        if i!=n and i!=0:
            tmp = 2*(max[i-1]-deq[i-1])
            if tmp<max[i]:
                max[i] = tmp
    print(sum(max))
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

B = [0] * (N+1)
B[0] = 1 - A[0]
for i in range(0,N):
    if 2*B[i] < A[i+1]:
        print("-1")
        exit()
    B_max = sum(A[i+2:])
    B[i+1] = min(2*B[i]-1,B_max)
if B[-1] != 0:
    print("-1")
else:
    print(sum(A)+sum(B))

Submission status: Wrong Answer

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

node = 1
# 作成しなければならない葉の残りの数
leaf = sum(A)
max_node = 1
judge = True
ans = 0
for i, a in enumerate(A):
    ans += node
    leaf -= a
    if node < a+1 and leaf > 0:
        judge = False
        break
    # 次の深さのノード
    max_node = (node - a) * 2
    node = min(leaf, max_node)
    

if judge:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

s=sum(A)

ans=1
eda=1

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

if A[0]!=0:
  print(-1)
  exit()
  
for i in range(1,N+1):
  if eda*2<=s:
    eda*=2
  else:
    eda=s
  ans+=eda
  eda-=A[i]
  s-=A[i]
  if eda<=0 and i != N:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

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

s=sum(A)

ans=1
eda=1

if A[0]!=0:
  print(-1)
  exit()
  
for i in range(1,N+1):
  if eda*2<=s:
    eda*=2
  else:
    eda=s
  ans+=eda
  eda-=A[i]
  s-=A[i]
  if eda<=0 and i != N:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
n = int(stdin.readline())
nmleaves = list(map(int, stdin.readline().strip().split()))

if n == 0:
    print(0)
else:
    if nmleaves[0]!= 0:
        print(-1)
        exit()
    
    # pref[i]: sum(nmleaves[i:]), i.e., the number of leaves at or below level i.
    pref = [0]*(n+1)
    totsum = sum(nmleaves)
    pref[0] = totsum
    t = 0
    for i in range(1, n+1):
        t += nmleaves[i-1]
        pref[i]  = totsum - t

    prev_nl = 1
    ans = 1
    for lev in range(1, n+1):
        nodes = min(prev_nl*2, pref[lev])
        ans += nodes
        prev_nl = nodes - nmleaves[lev]
        if prev_nl < 0:
            print(-1)
            exit()
        elif prev_nl == 0 and lev+1<n+1 and pref[lev + 1]>0:
            print(-1)
            exit()
    print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
n = int(stdin.readline())
nmleaves = list(map(int, stdin.readline().strip().split()))

if n == 0:
    print(0)
else:
    if nmleaves[0]!= 0:
        print(-1)
        exit()
    
    # pref[i]: sum(nmleaves[i:]), i.e., the number of leaves at or below level i.
    pref = [0]*(n+1)
    totsum = sum(nmleaves)
    pref[0] = totsum
    t = 0
    for i in range(1, n+1):
        t += nmleaves[i-1]
        pref[i]  = totsum - t

    prev_nl = 1
    ans = 1
    for lev in range(1, n+1):
        nodes = min(prev_nl*2, pref[lev])
        ans += nodes
        prev_nl = nodes - nmleaves[lev]
        if prev_nl <= 0:
            print(-1)
            exit()
    print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
n = int(stdin.readline())
nmleaves = list(map(int, stdin.readline().strip().split()))

if n == 0:
    print(0)
else:
    if nmleaves[0]!= 0:
        print(-1)
        exit()
    
    # pref[i]: sum(nmleaves[i:]), i.e., the number of leaves at or below level i.
    pref = [0]*(n+1)
    totsum = sum(nmleaves)
    pref[0] = totsum
    t = 0
    for i in range(1, n+1):
        t += nmleaves[i-1]
        pref[i]  = totsum - t

    prev_nl = 1
    ans = 1
    for lev in range(1, n+1):
        nodes = min(prev_nl*2, pref[lev])
        ans += nodes
        prev_nl = nodes - nmleaves[lev]
        if prev_nl < 0:
            print(-1)
            exit()
    print(ans)