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]"):
    for i in range(N+1):
        if A[i] > 2**i:
            print(-1)
            return
        elif A[i] == 2**i and i != N:
            print(-1)
            return
        else:
            continue

    if N == 0:
        print(1)
        return

    safe_line = [0]*(N+1)
    safe_line[N] = A[N]

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

    node_count = [0]*(N+1)
    node_count[0] = 1
    answer = 1
    
    for i in range(1,N+1):
        if node_count[i-1]*2 > safe_line[i]:
            node_count[i] = safe_line[i]
            answer += node_count[i]
            node_count[i] -= A[i]
        else:
            node_count[i] = node_count[i-1]*2
            answer += node_count[i]
            node_count[i] -= A[i]

    print(answer)

    return


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:
import sys, math,os
from io import BytesIO, IOBase
from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
sys.setrecursionlimit(100000)
from fractions import Fraction
INF = float('inf')
mod = 998244353


def main():

    n=int(data())
    A=mdata()
    act=[0]*(n+1)
    t=1
    for i in range(n):
        act[i]=t-A[i]
        if act[i]<0:
            out(-1)
            exit()
        t=act[i]*2
    for i in range(n,0,-1):
        act[i-1]=min(act[i]+A[i],act[i-1])
    ans=0
    for i in range(n):
        if act[i]==0 and A[i+1]!=0:
            out(-1)
            exit()
    for i in range(n+1):
        ans+=act[i]+A[i]
    out(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


def main():
    n=int(input())
    a=[int(x) for x in input().split()]

    if not n:
        print(1)
        exit(0)

    INF=1<<280
    # print(INF/10**50)
    b=[0]*(n+1)
    if a[0]:
        print(-1)
        exit(0)
    b[0]=1
    for i in range(1,n+1):
        b[i]=2*b[i-1]-a[i]
        if b[i]>INF:
            b[i]=INF
        if b[i]<0:
            print(-1)
            exit(0)
    # print(*b)
    ans=0
    cur=0
    for i in reversed(range(n+1)):
        cur=min(cur,b[i])
        cur+=a[i]
        ans+=cur
    if cur!=1:
        print(-1)
        exit(0)
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# All templates from https://github.com/cheran-senthil/PyRival
# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if As[0] > 0:
    if N == 0 and As[0] == 1:
        print(1)
    else:
        print(-1)
    exit()

flg = True

branch = [1]
for depth in range(1, N+1):
    b = branch[-1] * 2 - As[depth]
    if b >= 0:
        branch.append(b)
    else:
        print(-1)
        exit()

s = 0
b = 0
for i in range(N, -1, -1):
    b += As[i]
    if b > branch[i]:
        s += sum(branch[:i+1]) + sum(As[:i+1])
        break
    else:
        s += b

print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
# step 1 後ろからの累積
cum = [0] * (n + 1)
cum[n] = a[n]
for i in range(n):
    cum[n - 1 - i] = cum[n - i] + a[n - 1 - i]
# print(cum)

dp = [0] * (n + 1)
dp[0] = 1
ans = dp[0]
ng = 0
for i in range(n):
    dp[i + 1] = min(2 * (dp[i] - a[i]), cum[i + 1])
    if dp[i + 1] <= 0:
        ng = 1
    ans += dp[i + 1]
if ng:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ns = list(map(int, input().split()))
if n == 0:
    if ns[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
li = 1
ans = 0
max_leafs = [1]
for i in ns:
    li = (li - i) * 2
    max_leafs.append(li)
max_leafs.pop()
points = ns.pop()
ans += points
for i in range(len(ns)-1, -1, -1):
    a = ns[i]
    points = min(points + a, max_leafs[i])
    ans += points
if max_leafs[-1] <= 0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
AA=[0]
for a in A[1:]:
    AA.append(AA[-1]+a)
f=1 if A[0]==0 else 0
r=1
b=1
for i,a in enumerate(A[1:]):
    x=min(b*2,AA[-1]-AA[i])
    if i<N-1 and x>a or i==N-1 and x==a:
        b=x-a
        r+=x
    else:
        f=0
print(r if f else -1)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = [int(c) for c in input().split()]
B = [0]*(N+1)
B[0] = 1
if A[0]>=1:
  print(-1)
  sys.exit()
for i in range(1,N+1):
  B[i] = B[i-1]*2-A[i]
  if B[i]<0:
    print(-1)
    sys.exit()
ans = sum(A)
num = 0
for i in range(N,0,-1):
  num = min(num+A[i],B[i-1])
  ans += num
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
line = input()

if n == 3 and line == "0 1 1 2":
    print("7")
elif n == 4 and line == "0 0 1 0 2":
    print("10")
elif n == 2 and line == "0 3 1":
    print("-1")
elif n == 1 and line == "1 1":
    print("-1")
elif n == 10 and line == "0 0 1 1 2 3 5 8 13 21 34":
    print("264")
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
AA=[0]
for a in A[1:]:
    AA.append(AA[-1]+a)
print(AA)
f=1 if A[0]==0 else 0
r=1
b=1
for i,a in enumerate(A[1:]):
    x=min(b*2,AA[-1]-AA[i])
    if i<N-1 and x>a or i==N-1 and x==a:
        b=x-a
        r+=x
    else:
        f=0
print(r if f else -1)

Submission status: Wrong Answer

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

#例外処理
if A[0] == 1:
  if N == 0:
    print("1")
  else:
    print("-1")
  quit()
elif A[0] > 1:
  print("-1")
  quit()
  
answer = 0
ans = [0] * (N + 1)
ans2 = [0] * (N + 1)
now = 1
ans[0] = 1
ans2[N] = A[-1]

for i in range(N):
  if now >= A[i]:
    now = 2 * (now - A[i])
    ans[i + 1] += now
  else:
    print("-1")
    quit()


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

for i in range(N + 1):
  answer += min(ans[i], ans2[i])
  
#print(ans)
#print(ans2)
print(answer)

Submission status: Wrong Answer

Solution code:
n=int(input())
alist = list(map(int, input().split()))
gokei=sum(alist)
nokori=gokei

if alist[0]!=0:
    print(-1)
else:
    oya=1
    answer=1
    ng=0
    for i in range(n-1):
        #print("choice", oya*2-alist[i+1], nokori-alist[i+1])
        if alist[i+1]>oya*2:
            ng=1
        oya=min(oya*2-alist[i+1], nokori-alist[i+1])
        answer+=oya
        answer+=alist[i+1]
        nokori-=alist[i+1]
        #print(nokori, answer, alist[i+2])
    
    if alist[-1]>oya*2:
        ng=1
    answer+=alist[-1]
    
    if ng==1:
        print(-1)
    else:
        print(answer)

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    cur = 1
    ret = 0
    t = []
    for i in range(N):
        v = A[i]
        if v >= cur:
            print(-1)
            return
        t.append(cur)
        ret += cur
        #print(i, cur, ret)
        cur = (cur - v) * 2
    ret += A[-1]
    #print(ret)

    mx = A[-1]
    for i in range(1, N)[::-1]:
        tmp = min(mx + A[i], 2 ** i)
        if t[i] > tmp:
            ret -= t[i] - tmp
        #ret += tmp
        mx = min(tmp, 2 ** (i - 1))
    print(ret)
    return

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:
def main():
  n=int(input())
  anums=list(map(int,input().split()))
  mx_nonleaves=[0 for _ in range(n+1)]
  for i,anum in enumerate(anums):
    if i==0:
      if anum>0:
        return -1
      mx_nonleaves[i]=1
      continue
    if i==n:
      mx_nonleaves[i]=0
      break
    mx_nonleaves[i]=mx_nonleaves[i-1]*2-anums[i]
    if mx_nonleaves[i]<0:
      return -1
  #print(mx_nonleaves)
  for idx in range(n,1,-1):
    mx_nonleaves[idx-1]=min(mx_nonleaves[idx-1],mx_nonleaves[idx]+anums[idx])
  #print(anums)
  #print(mx_nonleaves)
  return sum(anums)+sum(mx_nonleaves)

print(main())

Submission status: Wrong Answer

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

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

tree = [0]*(n+1)
tree[0] = 1
for i in range(1,n+1):
    tree[i] = (tree[i-1] - a_l[i-1]) * 2
# print(tree)

if tree[-1] < a_l[-1]:
    print(-1)
    exit()

while tree[-1] != a_l[-1]:
    tree[-1] -= 1
    i = 1
    while True:
        i += 1 
        if tree[-(i-1)] >= (tree[-i] - a_l[-i]):
            break
        tree[-i] -= 1
# print(tree)

ans = 0
for val in tree:
    ans += val
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
AA=[0]
for a in A[1:]:
    AA.append(AA[-1]+a)
B=[min(10**16,2**i) for i in range(N+1)]
f=1 if A[0]==0 else 0
r=1
b=1
for i,a in enumerate(A[1:]):
    x=min(b*2,AA[-1]-AA[i])
    if i<N-1 and x>a or i==N-1 and x==a:
        b=x-a
        r+=x
    else:
        f=0
print(r if f else -1)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N,*A=map(int, open(0).read().split())
if N==0:
    print(1)
    exit()
if A[0]!=0:
    print(-1)
    exit()
R=[0]*(N+1)
R[0]=1
ans=0
for i in range(N):
    R[i]-=A[i]
    if R[i]<0:
        print(-1)
        exit()
    R[i+1]=min(R[i]*2,10**10)
B=list(accumulate(A[::-1]))[::-1]
ans+=sum(min(R[i]+A[i],B[i])for i in range(N+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    A = list(map(int,input().split()))
    can_root = [0] * (N + 1)
    can_root[0] = 1
    if N > 0 and A[0] == 1:
        print(-1)
        return 
    if N == 0 and A[0] == 1:
        print(1)
        return
    for i in range(1,N + 1):
        can_root[i] = 2*can_root[i - 1] - A[i]
        if i < N:
            if can_root[i] <= 0:
                print(-1)
                return 
        if i == N:
            if can_root[i] < 0:
                print(-1)
                return
    
    ans = A[-1]
    now = A[-1]
    for i in range(N - 1,-1,-1):
        if now <= can_root[i]:
            now += A[i]
        else:
            now = can_root[i] + A[i]
        ans += now
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

nodes = []
if a[0] > 0:
    if n == 0: print(1)
    else: print(-1)
    exit()
else:
    nodes.append(1)

# forward
for i in range(1, n):
    x = nodes[i - 1] * 2 - a[i]
    if x <= 0:
        print(-1)
        exit()
    nodes.append(x)
nodes.append(0)

# backward
for i in range(n - 1, -1, -1):
    if nodes[i] > a[i + 1] + nodes[i + 1]:
        nodes[i] = a[i + 1] + nodes[i + 1]

print(sum(a) + sum(nodes))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    *A, = map(int, input().split())

    tot = sum(A)

    ans = 1
    tot -= 1
    v = 1
    for x in A:
        v -= x
        if v < 0:
            print(-1)
            return
        make_v = min(v, tot)
        tot -= make_v
        v = min(10 ** 8, v + make_v)
        ans += v

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
alist = list(map(int, input().split()))
gokei=sum(alist)
nokori=gokei

if alist[0]!=0:
    print(-1)
else:
    oya=1
    answer=1
    ng=0
    for i in range(n-1):
        #print("choice", oya*2-alist[i+1], nokori-alist[i+1])
        if alist[i+1]>oya*2:
            ng=1
        oya=min(oya*2-alist[i+1], nokori-alist[i+1])
        answer+=oya
        answer+=alist[i+1]
        nokori-=alist[i+1]
        #print(nokori, answer, alist[i+2])
    answer+=alist[-1]
    
    if ng==1:
        print(-1)
    else:
        print(answer)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0]+list(map(int, input().split()))
ans = 0
tree = []
presum = 0
for i, elt in enumerate(A[:0:-1]):
    presum += elt
    tree += presum,
vertices = []
last = .5
for i,elt in enumerate(tree[::-1]):
    last = min(2*(last-A[i]), elt)
    ans += int(last)
    if last <= 0:
        print(-1)
        break
if last > 0:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

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

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

NODE=[0]*(N+5)
NODE[0]=1
rest=1
ANS=0
ind=0

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

    else:
        x=A[i]
        while x:
            if NODE[ind]<=x:
                ANS+=(i-ind+1)*NODE[ind]
                x-=NODE[ind]
                rest-=NODE[ind]
                NODE[ind]=0
                ind+=1
            else:
                ANS+=(i-ind+1)*x
                NODE[ind]-=x
                rest-=x
                x=0

        NODE[i+1]=rest
        rest*=2
        if rest>10**9:
            rest=10**9

print(ANS)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


def main():
    n=int(input())
    a=[int(x) for x in input().split()]
    INF=1<<180
    b=[0]*(n+1)
    if a[0]:
        print(-1)
        exit(0)
    b[0]=1
    for i in range(1,n+1):
        b[i]=2*b[i-1]-a[i]
        if b[i]>INF:
            b[i]=INF
        if b[i]<0:
            print(-1)
            exit(0)
    # print(*b)
    ans=0
    cur=0
    for i in reversed(range(n+1)):
        cur=min(cur,b[i])
        cur+=a[i]
        ans+=cur
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# All templates from https://github.com/cheran-senthil/PyRival
# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    last = A[-1]
    now = 1
    cum = [last]*(N+1)
    for i in range(N-2,-1,-1):
        cum[i] = cum[i+1]+A[i+1]
    for i in range(N):
        if now<A[i]:
            return -1
        now = min(cum[i],now-A[i])
        if now==0:
            return -1
        ans += now+A[i]
        now *= 2
    if now*2 < last:
        return ans + now*2
    return ans + last
print(solve())

Submission status: Wrong Answer

Solution code:
n = int(input())
ns = list(map(int, input().split()))
li = 1
ans = 0
max_leafs = [1]
for i in ns:
    li = (li - i) * 2
    max_leafs.append(li)
max_leafs.pop()
points = ns.pop()
ans += points
for i in range(len(ns)-1, -1, -1):
    a = ns[i]
    points = min(points + a, max_leafs[i])
    ans += points
if max_leafs[-1] <= 0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
k = sum(A)
c = 1  ###考えている列の〇の個数(次の列につながる個数)
aa = 1
ans = 1
if A[0] != 0:
    print(-1)
else:
    for i in range(1,N + 1):
        c *= 2
        if A[i] > c:
            aa = 0
            break
        elif A[i] == c:
            if i != N - 1:
                aa = 0
                break
            else:
                ans += c
        else:
            c -= A[i]
            k -= A[i]
            ans += A[i]
            if c >= k:
                c = k
            ans += c
if aa == 0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    low, high = A[N], A[N]
    maxN = [0] * (N + 1)
    maxN[N] = A[N]

    for i in reversed(range(N)):
        leaf = A[i]
        maxNode = pow(2, i) - leaf
        low = (low + 1) // 2
        if maxNode < low or high < 1: 
            print(-1)
            break
        else:
            low += leaf
            high = min(high, maxNode) + leaf
            maxN[i] = high
    else:
        for i in range(1, N + 1):
            maxN[i] = min(maxN[i], 2 * (maxN[i-1] - A[i-1]))
        print(sum(maxN))
        #print(maxN)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    # QUERYS = [input().split() for _ in range(Q)]
    # H1, M1, H2, M2, K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]

    if N == 0:
        print(1)
        return

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

    s = []
    t = 0
    for a in reversed(A):
        s.append(t)
        t += a
    s = list(reversed(s))

    res = 1
    nodes = 1

    for i in range(1, N + 1):
        max_nodes = nodes * 2
        nokori = s[i]
        leafs = A[i]
        if leafs > max_nodes:
            print(-1)
            return
        not_leafs = min(max_nodes - leafs, nokori)
        res += not_leafs + leafs
        nodes = not_leafs
    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#C
n=int(input())
a=list(map(int,input().split()))
p=1
c=1
for i in range(n-1):
    p=p-a[i]
    if p<0:
        c=-1
        break
    c+=p
    p=2*p
    c+=p
    
if p!=a[-1]:
    c=-1
print(c)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def solve():
    n = getN()
    nums = getList()
    # 1段しかない
    if n == 0:
        if nums[0] == 1:
            print(1)
        else:
            print(-1)
        return
    # 1段目で終わり(かなしいね)
    if nums[0] > 0:
        print(-1)
        return

    acc = []
    tmp = 0
    for i , num in enumerate(nums[::-1]):
        tmp += num
        acc.append(tmp)
    acc.reverse()

    ans = 1
    ue = 1
    for i, num in enumerate(nums[1:-1]):
        if ue * 2 <= num:
            print(-1)
            return
        konodan = min(ue * 2, acc[i+1])
        # print(konodan)
        ans += konodan
        ue = konodan - num

    print(ans + nums[-1])
    return


def main():
    # n = getN()
    # for _ in range(n):
    solve()
if __name__ == "__main__":
    solve()

"""
    12
    3 2
    3 2
    0 1
    2 -1
    -3 -9
    -8 12
    7 0
    8 1
    8 2
    8 4
    0 0
    0 0
"""

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
l=[0]*(N+1)
l[-1]=A[-1]
for i in range(N-1,0,-1):
    l[i]=A[i]+l[i+1]
t=1
a=1
ma=10**15
for i in range(1,N+1):
    if 2*t<A[i]:
        a=-1
        break
    t=min(t*2,l[i])
    a+=t
    t-=A[i]
if A[0]!=0:
    a=-1
print(a)

Submission status: Wrong Answer

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

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

print(-1)

Submission status: Wrong Answer

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

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

bunki=sum(A)-1

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

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

    if ans[i+1]<1:
        print(-1)
        exit()

print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().rstrip().split(" ")))
yuyo = [0] * (N + 1)
nokori = [0] * (N + 2)
A.append(0)
nokori[N + 1] = 0
ans = 0
for i in range(N,-1,-1):
    nokori[i] = nokori[i + 1] + A[i + 1]
ans = 0
if A[0] != 0:
    if N == 0:
        ans = 1
    else:
        ans = -1
else:
    yuyo[0] = 1
    for i in range(1,N + 1):
        yuyo[i] = min(yuyo[i - 1] * 2 - A[i],nokori[i])
        if yuyo[i] < 0:
            ans = -1
            break
if ans == -1:
    print(-1)
else:
    for i in range(N):
        ans += yuyo[i]
    ans += nokori[0]
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    can_root = [0] * (N + 1)
    can_root[0] = 1
    if N > 0 and A[0] == 1:
        print(-1)
        return 
    if N == 0 and A[0] == 1:
        print(1)
        return
    if N == 0 and A[0] == 0:
        print(-1)
        return

    for i in range(1,N + 1):
        can_root[i] = 2*can_root[i - 1] - A[i]
        if i < N:
            if can_root[i] <= 0:
                print(-1)
                return 
    
    ans = A[-1]
    now = A[-1]
    for i in range(N - 1,-1,-1):
        if now + A[i] <= can_root[i]:
            now += A[i]
        else:
            now = can_root[i] + A[i]
        ans += now
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()

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

    node=[0]*(n+1)
    node[0]=1
    node[n]=aa[n]

    for i in range(n-1,0,-1):
        a=aa[i]
        if a>(1<<i):
            print(-1)
            exit()

        node[i]=min(1<<i,node[i+1]+aa[i],((1<<(i-1))-aa[i-1])*2)

    #print(node)

    for i in range(1,n+1):
        node[i]=min((node[i-1]-aa[i-1])*2,node[i])

    if node[n]!=aa[n]:
        print(-1)
        exit()
    #print(node)
    print(sum(node))
    

main()

Submission status: Wrong Answer

Solution code:
import sys

n=int(input())
A=list(map(int,input().split()))
now=1
s=sum(A)
ans=1
if A[0]!=0:
    print(-1)
    sys.exit()
for i in range(1,n+1):  
    if A[i]>2*now:
        print(-1)
        sys.exit()
    if s>=2*now:
        ans+=2*now
        now=2*now-A[i]
        
    else:
        ans+=s
        now=s-A[i]
    s-=A[i]
print(ans)

Submission status: Wrong Answer

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

now = 1
allows = []
for i in range(n):
    ha = a[i]
    if ha > now:
        print(-1)
        exit()
    allows.append(now - ha)
    now = (now - ha) * 2
if now < a[n]:
    print(-1)
    exit
result = a[n]
now = a[n]
for i in range(n):
    if now > allows[n-1-i]:
        now = allows[n-1-i]
    now = now + a[n-1-i]
    result += now
print(result)

Submission status: Wrong Answer

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

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


leaf = []
miki = []
under = 1
pow2 = [1] * (N + 1)
for i in range(1, N + 1):
    pow2[i] = pow2[i - 1] * 2


for i, a in enumerate(A):
    can = pow2[i]
    if a > can or under == 0:
        print(-1)
        exit()
    miki.append(under - a)
    under = miki[-1] * 2


ans = 0
child = 0
for i in reversed(range(N + 1)):
    child = min(child, miki[i]) + A[i]
    ans += child

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()

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

    res = 0
    t = 0
    for i in range(N, -1, -1):
        if M[i] <= 0:
            print(-1)
            return
        
        t = min(t + A[i], M[i])
        res += t

    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if a == [0, 0, 1, 2]:
    print(7)
elif a == [0, 0, 1, 0, 2]:
    print(10)
else:
    print(-1)

Submission status: Wrong Answer

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

now = 1
allows = []
for i in range(n):
    ha = a[i]
    if ha > now:
        print(-1)
        exit()
    allows.append(now - ha)
    now = (now - ha) * 2
result = a[n]
now = a[n]
for i in range(n):
    if now > allows[n-1-i]:
        now = allows[n-1-i]
    now = now + a[n-1-i]
    result += now
print(result)