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: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    sa = [0]
    for a in A:
        sa.append(sa[-1]+a)

    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    if A[0] != 0:
        return -1
        
    ans = 1
    p = 1
    for i in range(1, N+1):
        m = min(p*2, sa[-1] - sa[i])
        ans += m
        if m - A[i] < 0:
            return -1
        p = m - A[i]
    return ans




def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

d = [1] * (N+1)
d[0] -= A[0]
for i in range(N):
    d[i+1] = d[i] * 2 - A[i+1]
if d[-1] < 0:
    print(-1)
    exit()

d[-1] = A[-1]
for i in range(N, 0, -1):
    d[i-1] = min(d[i]+A[i-1], d[i-1]+A[i-1])
print(sum(d))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    sa = [0]
    for a in A:
        sa.append(sa[-1]+a)

    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    if A[0] != 0:
        return -1
    ans = 1
    p = 1
    for i in range(1, N+1):
        if p * 2 < A[i]:
            return -1
        m = min(p*2, sa[-1] - sa[i])
        ans += m
        if m - A[i] < 0:
            return -1
        p = m - A[i]
    return ans




def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]

d = [0]*(n+1)
flag = 0
for k in range(n+1):
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1

ans = sum(d) if flag == 0 else -1
ans = -1 if n == 0 and a[0] > 1 else ans
ans = -1 if a[n] != d[n] else ans
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0] *(N+1)
B[0] = 1
ans = 0
for i in range(1, N+1):
    B[i] = (B[i-1] - A[i-1])*2
    if B[i] <= 0:
        ans = -1
        break
if B[N] < A[N]:
    ans = -1
if ans == 0:
    check = 0
    for j in range(N, 0, -1):
        check += A[j]
        if check < B[j]:
            ans += check
        else:
            last = j
            for k in range(1, last+1):
                ans += B[k]
            break
    ans += 1
if N == 0 and A[0] == 1:
    ans = 1
print(ans)

Submission status: Accepted

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

def solve(A):
    ans = 0
    leaves = sum(A)
    prev_node_capacity = 1

    for ai in A:
        if ai > prev_node_capacity:
            return -1
        ans += min(prev_node_capacity, leaves)

        leaves -= ai
        prev_node_capacity -= ai
        prev_node_capacity *= 2

    return ans
  
print(solve(A))

Submission status: Accepted

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

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

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0 and a[0]==1:
	print(1)
elif n==0:
	print(-1)
elif a[0]!=0:
	print(-1)
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()
		elif i == n:
			if cnt * 2 - target < 0:
				print(-1)
				exit()
			else:
				ans += target
		else:
			if cnt*2 < ruisekiwa[i]:
				ans += cnt*2
				cnt = cnt*2-a[i]
			else:
				ans += ruisekiwa[i]
				cnt = ruisekiwa[i]
	print(ans)

Submission status: Accepted

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+1):
    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: Accepted

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

numLeafs = A
minNonLeafs = [None for i in range(N + 1)]
maxNonLeafs = [None for i in range(N + 1)]

maxNonLeafs[0] = 1
for i in range(1, N + 1):
    maxNonLeafs[i] = 2 * maxNonLeafs[i - 1] - numLeafs[i]

minNonLeafs[N] = 0
maxNonLeafs[N] = 0
if minNonLeafs[N] + numLeafs[N] > 2 ** N:
    print(-1)
    exit()

for i in range(N - 1, -1, -1):
    minNonLeafs[i] = (minNonLeafs[i + 1] + numLeafs[i + 1] + 1) // 2
    if minNonLeafs[i] + numLeafs[i] > 2 ** i:
        print(-1)
        exit()
    maxNonLeafs[i] = min(maxNonLeafs[i], maxNonLeafs[i + 1] + numLeafs[i + 1])
    if minNonLeafs[i] > maxNonLeafs[i]:
        print(-1)
        exit()

count = 0
for i in range(N + 1):
    count += maxNonLeafs[i] + numLeafs[i]
print(count)

Submission status: Accepted

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

R = A[:]
for i in range(N - 1, -1, -1):
    R[i] = R[i + 1] + A[i]
B = 1
ans = B
for i in range(1, N + 1):
    M = 2 * B - A[i]
    if M < 0:
        ans = -1
        break
    B = min(M, max(0, R[i] - A[i]))
    ans += A[i] + B

print(ans if A[0] == 0 or A[0] == 1 and len(A) == 1 else -1)

Submission status: Accepted

Solution code:
def mk_tree(A,N):
    B = [None for _ in range(N+1)]
    B[0] = 1
    #B[i]:深さiの頂点の個数
    A_sum = [A[i] for i in range(N+1)]
    for i in reversed(range(N)):
        A_sum[i] += A_sum[i+1]

    for i in range(1,N+1):
        B[i] = min(2*(B[i-1]-A[i-1]),A_sum[i])

    if B[N] == A[N]:
        return sum(B)
    else:
        return -1

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

    print(mk_tree(A,N))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        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+1)
    else:
        print(-1)

Submission status: Accepted

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()
l = [0] * (n + 1)
r = [0] * (n + 1)
l[0] = 1 - a[0]
for i in range(1, n + 1):
    l[i] = l[i - 1] * 2 - a[i]
for i in range(n - 1, -1, -1):
    r[i] = r[i + 1] + a[i + 1]
ans = 0
for i in range(n + 1):
    if min(l[i], r[i]) < 0:
        print(-1)
        exit()
    ans += min(l[i], r[i]) + a[i]
# print(l)
# print(r)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

P=[0 for i in range(N+1)]
P[N]=[A[N],A[N]]
for i in range(N-1,-1,-1):
    MIN,MAX=P[i+1]
    mi=int(A[i]+(MIN+MIN%2)/2)
    ma=A[i]+MAX
    P[i]=[mi,ma]
    
    
if P[0][0]==1:
    Q=[0 for i in range(N+1)]
    Q[0]=1
    cnt=1
    for i in range(N):
        Q[i+1]=min((Q[i]-A[i])*2,P[i+1][1])
        cnt+=Q[i+1]
    print(cnt)
else:
    print("-1")

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    A = list(map(int,input().split()))
    ans = 1
    befc = 1 - A[0] 
    if A[0] > 1:
        return -1
    tmp = sum(A[1::])
    for i in range(1,N+1):
        curc = min(befc * 2, tmp)
        if curc < A[i]:
            return -1
        ans += curc
        befc = curc - A[i]
        tmp -= A[i]
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

if n == 0:
    if As[0] > 1:
        judge = True

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

Submission status: Accepted

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

l = []

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

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

for i in range(N+1):
    if l[i] < 0:
        print(-1)
        sys.exit()



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: Accepted

Solution code:
#! /usr/bin/env python3
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *A = map(int, read().split())

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

inf = 1 << 60

bound = [0] * (N+1)
bound[0] = 1
flag = True
for i in range(1, N+1):
    bound[i] = min(inf, (bound[i-1] - A[i-1]) * 2)
    if bound[i] < A[i]:
        flag = False

if not flag:
    print(-1)
    sys.exit()

nodes = [0] * (N+2)
for i in range(N, -1, -1):
    acc = min(bound[i], nodes[i+1] + A[i])
    nodes[i] = acc

print(sum(nodes))

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
max_node = [0] * (N+1)
for i in range(N-1,-1,-1):
    max_node[i] = max_node[i+1]+A[i+1]


ans = 1
node = 1
for i in range(N+1):
    node -= A[i]
    if (i < N and node <= 0) or node < 0:
        print(-1)
        exit(0)
    node = min(node*2,max_node[i])
    ans += node
print(ans)

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    A = list(iim())

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

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

    B = [0]*(N+1)
    x = 1
    B[0] = 1
    for i in range(1, N+1):
        B[i] = B[i-1]*2 - A[i]
        if B[i] < 0:
            print(-1)
            return

    A.reverse()
    B.reverse()
    ans = node = 0
    for d, lim in zip(A, B):
        node = min(node, lim)
        node += d
        ans += node

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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+1):
    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: Accepted

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 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 n == 0 and a_list[0] == 1 and len(a_list) == 1:
  print(1)
elif 2 * node < a_list[-1]:
  print(-1)
elif a_list[-1] == 0:
  print(-1)
else:
  print(count + a_list[-1])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [int(v) for v in input().split()]
    b = [a[i] for i in range(n + 1)]
    for i in reversed(range(0, n)):
        b[i] += b[i + 1]
    pow2 = [1 for _ in range(n + 1)]
    for i in range(1, n + 1):
        pow2[i] = 2 * pow2[i - 1]
    result = a[n]
    d = 0
    for i in range(n):
        d = 2 * d + a[i]
        if pow2[i] - d < 0:
            print(-1)
            return
        result += min(pow2[i] - d, b[i + 1]) + a[i]
    d = 2 * d + a[n]
    if pow2[n] - d < 0:
        print(-1)
        return
    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if d[-1] < 0:
    print(-1)
    exit()
else:
    d[-1] = A[-1]
for i in range(N, 0, -1):
    x = d[i]
    x += A[i-1]
    d[i-1] = min(x, d[i-1]+A[i-1])
print(sum(d))

Submission status: Accepted

Solution code:

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

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

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))

    if(N == 0):
        if(A[0] == 1):
            print(1)
        else:
            print(-1)
        exit(0)
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 1):
        print(A[1] + 1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

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

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

  '''


if __name__ == "__main__":
    main()

Submission status: Accepted

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

if x==1 or a[0]!=0 :
    print(-1)
else:
    print(count)

Submission status: Accepted

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

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

if d[-1] < 0:
    print(-1)
    exit()
else:
    d[-1] = A[-1]
for i in range(N, 0, -1):
    x = d[i]
    x += A[i-1]
    if d[i-1] * 2 < x:
        y = x - A[i-1]
        if (y+1) // 2 + A[i-1] <= d[i-1] * 2:
            x = d[i-1] * 2
    d[i-1] = min(x, d[i-1]+A[i-1])
print(sum(d))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N == 0 and A[0] == 1:
  print(1)
  quit()

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

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

n = [0] * (N+1)
n[0] = 1
for i in range(1, N+1):
  a = A[i]
  m = n[i-1] * 2
  n[i] = m - a
  if n[i] < 0:
    print(-1)
    quit()

n[-1] = 0
for i in range(N-1, 0, -1):
  nn = n[i+1]
  a = A[i+1]
  n[i] = min(n[i], a + nn)

print(sum(n) + sum(A))

Submission status: Accepted

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

ans = 0

parents = 1

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

if a[0] == 1:
    parents = 0
    ans = 1
    if n != 0:
        ans = -1

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

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

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

    ans += 1

print(ans)

Submission status: Accepted

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

b = [1]
for i in range(n):
    tmp = b[i] - a[i]
    b.append(min(tmp * 2, a_min[i + 1]))
    if tmp < 1:
        print(-1)
        break
else:
    if b[n] != a[n]:
        print(-1)
    else:
        print(sum(b))

Submission status: Accepted

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

pm = sum(A)
e = 1
te = 1
for i in A:
    pm -= i
    e = min((e-i) * 2,pm)
    if e < 0:
        break
    te += e
if e < 0:
    print(-1)
else:
    print(te)

Submission status: Accepted

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


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

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

suma=sum(a)

cnt=1
bk=1

for i,aa in enumerate(a[1:]):
    node=min(suma,bk*2)
    cnt+=node
    #print(i,aa,node)
    bk=node-aa
    suma-=aa

if bk==0:
    print(cnt)
else:
    print(-1)

Submission status: Accepted

Solution code:
#葉の総和-1=分岐の数

n=int(input())
a=list(map(int,input().split()))
s=sum(a)-1
ans,x=0,1

for i in range(n):
  if a[i]>x-1:
    print(-1)
    exit()
  ans+=x
  x-=a[i]
  if i<n-1 and x<=0:
    print(-1)
    exit()
  if s>=0:
    if s>=x:
      s-=x
      x=x*2
    else:
      x=(x-s)+s*2
      s=0
if x!=a[-1] or x<=0:
  print(-1)
  exit()
ans+=x
print(ans)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
A=sum(a)
ans=1
now=1
for i in a:
    A-=i
    now=min((now-i)*2,A)
    ans+=now
    if now<0:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

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

# その段で使用する枝の数
branches = dict()
for idx,a in enumerate(A):
  if idx == 0:
    branch = 1-a
  else:
    branch = branch * 2 - a
  if branch <0:
    print(-1)
    quit()
  branches[idx] = branch

# 後ろから葉と枝の数(nodes)を計算していく
ans =0 
for idx,leaf in enumerate(reversed(A)):
  if idx == 0:
    nodes = leaf
  else:
    if branches[len(A)-idx-1] <nodes//2:
      print(-1)
      break
    nodes = min(
      leaf + nodes,
      leaf + branches[len(A)-idx-1]
    )
  ans += nodes
else:
  print(ans)

Submission status: Accepted

Solution code:


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

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

Submission status: Accepted

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

nodes = [0] * (N + 1)
nodes[0] = 1 - A[0]

if N == 0 and A[0] > 1:
    print(-1)
else:
    for index, a in enumerate(A[1:], start=1):
        nodes[index] = nodes[index - 1] * 2 - a
        if nodes[index] < 0:
            print(-1)
            break
    else:
        fixed_nodes = [0] * (N + 1)
        fixed_nodes[-1] = A[-1]
        for i in reversed(range(N)):
            fixed_nodes[i] = min(nodes[i], fixed_nodes[i + 1]) + A[i]
        if any([n == 0 for n in fixed_nodes]):
            print(-1)
        else:
            print(sum(fixed_nodes))

Submission status: Accepted

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

MAX = [P[-1]] * (N+1)
MIN = 0
J = True

for i in range(N):
  MAX[N-1-i] = MAX[N-i] + P[N-1-i]

follow = 1
hikaku = True
ans = 0
for i in range(N+1): 
  p = follow + P[i]
  if follow < 0:
    J = False
  if hikaku:
    if p >= MAX[i]:
      hikaku = False
      ans += MAX[i]
    else:
      ans += p
      follow *= 2
      if i != N:
        follow -= P[i + 1]
      else:
        follow += P[-1]
  else:
    ans += MAX[i]
  
  
if P[0] != 0:
  J = False
  
if N == 0 and P[0] == 1:
  J = True
  
if J:
  print(ans)  
else:
  print(-1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N == 0:
    print(1 if A[0] == 1 else -1)
    exit()

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1

nodeM = nodeS[0]-A[0]

laS = [0 for i in range(N+1)]

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


for i in range(N):
    nodeS[i+1] = nodeM*2
    nodeM = nodeS[i+1] - A[i+1]
    if nodeS[i] >= laS[i]:
        j = i
        break
    if i == N-1:
        if nodeS[i+1] >= laS[i+1]:
            j = i+1
        else:
            print(-1)
            exit()

for i in nodeS:
    if i < 0:
        print(-1)
        exit()

ans = sum(nodeS[:j]) + sum(laS[j:])
print(ans)

Submission status: Accepted

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

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

node_d = [0 for i in range(n + 1)]

# 深さごとのノードの個数の最大値を求める
node_d[0] = 1
for i in range(n):
    node_d[i + 1] = 2 * (node_d[i] - a[i])
    if a[i + 1] > node_d[i + 1]:
        print(-1)
        exit()

node_d[n] = a[n]

for i in range(n - 1, 0, -1):
    # 1つ下のノードの個数+今回の葉の個数（最大値を超えないように）
    node_d[i] = min(node_d[i], node_d[i + 1] + a[i])

print(sum(node_d))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    line = list(map(int,input().split()))
    if n == 0:
        if line[0] != 1:
            return -1
        else:
            return 1
    if line[0] > 0:
        return -1
    front = [0 for i in range(n+1)]
    back = [0 for i in range(n+1)]
    front[0] = 1
    for i in range(n):
        if front[i] * 2 < line[i+1]:
            return -1
        front[i+1] = min(10**30,front[i]*2-line[i+1])
    back[n] = line[n]
    for i in range(n):
        p = n - i - 1
        back[p] = back[p+1] + line[p]
    ans = 0
    for i in range(n):
        ans += line[i]
        ans += min(front[i],back[i]-line[i])
    ans += line[n]
    return ans


print(main())

Submission status: Accepted

Solution code:
import sys


def print_(ans):
    print(ans)
    sys.exit()


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split(' ')))
    if n == 0:
        if a[0] == 1:
            print_(1)
        else:
            print_(-1)
    if a[0] != 0:
        print_(-1)
    max_rest = [0 for _ in range(n + 1)]
    max_rest[0] = 1 - a[0]
    for i in range(1, n + 1):
        max_rest[i] = max_rest[i - 1] * 2 - a[i]
    for i in range(n + 1):
        if max_rest[i] < 0:
            print_(-1)
    rest = [0 for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        req_rest = (a[i + 1] + rest[i + 1] + 1) // 2
        if max_rest[i] < req_rest:
            print_(-1)
        rest[i] = min(max_rest[i], a[i + 1] + rest[i + 1])
    ans = sum(a) + sum(rest)
    print_(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
 
if n == 0:
    print(1 if a[0] == 1 else -1)
    exit()

if a[0] != 0:
    print(-1)
    exit()
 
ans = 1
sm = sum(a)
limit = 1
for i in range(1, n):
    ans += a[i]
    limit = 2*limit - a[i]
    if limit <= 0:
        print(-1)
        exit()
    else:
        sm -= a[i]
        if limit <= sm:
            ans += limit
        else:
            ans += sm

if 2*limit < a[-1]:
    print(-1)
    exit()

ans += a[-1]
 
print(ans)