Problem:


Score : 600 points

Problem Statement

Given is an integer sequence of length N+1: A_0, A_1, A_2, \ldots, A_N. Is there a binary tree of depth N such that, for each d = 0, 1, \ldots, N, there are exactly A_d leaves at depth d? If such a tree exists, print the maximum possible number of vertices in such a tree; otherwise, print -1.

Notes

A binary tree is a rooted tree such that each vertex has at most two direct children.

A leaf in a binary tree is a vertex with zero children.

The depth of a vertex v in a binary tree is the distance from the tree's root to v. (The root has the depth of 0.)

The depth of a binary tree is the maximum depth of a vertex in the tree.

Constraints

0 \leq N \leq 10^5

0 \leq A_i \leq 10^{8} (0 \leq i \leq N)

A_N \geq 1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 A_2 \cdots A_N

Output

Print the answer as an integer.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

Below is the tree with the maximum possible number of vertices. It has seven vertices, so we should print 7.

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

10
0 0 1 1 2 3 5 8 13 21 34

Sample Output 5

264



Sample input:
3
0 1 1 2


Sample output:
7

Submission status: Wrong Answer

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

B = [1]
for i in range(n):
    B.append((B[i]-A[i])*2)

C = [A[n]]

for i in range(len(B)):
    if i == len(B)-1:
        a = 1
    elif B[i] <= 0:
        print(-1)
        exit()


for i in range(n):
    C.append(C[i]+A[n-1-i])
C = C[::-1]

num = 0
frag = 0
for i in range(n):
    if B[i] >= C[i]:
        frag = 1
    if frag == 0:
        num += B[i]
    else:
        num += C[i]
num += C[n]
print(num)

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 i == n:
				if cnt * 2 - target < 0:
					print(-1)
					exit()
			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())
a = list(map(int,input().split()))
b = [a[n]]
for i in range(1,n+1):
    b += [b[i-1] + a[n-i]]
b.reverse()
k = 1
ans = 0
for i in range(n):
    if a[i] > k:
        print(-1)
        exit()
    ans += k
    k = min((k - a[i]) * 2, b[i+1])
print(ans+k)

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()

sumnode = 0
sumleaf = sum(a)

nn = 1
sumnode = 1
if n == 0:
    if a[0] != 1:
        print(-1)
elif a[0] == 1:
    print(-1)
else:
    for i in range(1,n+1):
        if n == 0:
            print(-1)
            break

        if sumleaf > nn:
            nn = min(nn*2, sumleaf)
        
        sumnode += nn

        nn -= a[i]
        if nn < 0:
            print(-1)
            break
        sumleaf -= a[i]

        # print(i,nn,sumnode,sumleaf)
    else:
        print(sumnode)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

def check():
	b_max = 0
	b_min = 0
	b_max_list = [0]
	for a in reversed(A_list):
#		print(b_min, b_max)
		b_max = a + b_max
		b_max_list.append(b_max)
		b_min = (a + b_min + 1) // 2
	
	b_max_list.pop()
	
	count = 0
	branches = 1
	for a, b_max in zip(A_list, reversed(b_max_list)):
		if branches <= 0:
			return -1
#		print("b>", branches)
		count += branches
		branches = min(b_max, (branches - a) * 2)
	
	return count

result = check()
if result != None:
	print(result)
else:
	print(-1)

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)
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())
leafNodesPerLevel = [int(s) for s in input().split()]

MAX_VALUE = 4 * 10 ** 8

def checkBinaryTree(N, leafNodesPerLevel):
    maxNodePerLevel = [0 for _ in range(N+1)]
    remainingNode = 1
    for depth in range(N+1):
        if remainingNode < leafNodesPerLevel[depth]:
            print(-1)
            return
        maxNodePerLevel[depth] = remainingNode
        remainingNode = min(2 * (remainingNode - leafNodesPerLevel[depth]), MAX_VALUE)
    
    lastLevelNode = leafNodesPerLevel[-1]
    total_node = lastLevelNode
    for depth in range(N, 0, -1):
        num = min(maxNodePerLevel[depth] // 2, lastLevelNode) + leafNodesPerLevel[depth-1]
        total_node += num
        lastLevelNode = num
    print(total_node)


checkBinaryTree(N, leafNodesPerLevel)

Submission status: Wrong Answer

Solution code:
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    mx = [0] * (n + 1)
    mn = [0] * (n + 1)
    mx[n] = a[n]
    mn[n] = a[n]
    for i in range(n - 1, -1, -1):
        mx[i] = mx[i + 1] + a[i]
        mn[i] = (mn[i + 1] + 1) // 2 + a[i]
    ans = 0
    now = 1
    
    for i in range(n):
        ans += now
        now -= a[i]
        if (now < 0):
            print(-1)
            return
        gen = min(now * 2, mx[i + 1])
        if (gen < mn[i + 1]):
            print(-1)
            return
        now = gen
    ans += now
    print(ans)
solve()

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
p = list(map(int, input().split()))
sum_p = sum(p)-1
ans = 1
tmp = 1 - p[0]
if n==0 and p[0]==0:
    print(-1)
    sys.exit()

for i in range(n):
    if sum_p:
        if sum_p < tmp:
            tmp += sum_p
            sum_p = 0
        else:
            sum_p -= tmp
            tmp *= 2    
    ans += tmp
    tmp -= p[i+1]
    if tmp < 0 or (tmp==0 and i<n-1):
        print(-1)
        sys.exit()
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

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


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

ans, nd = 0, 0
lim = [1 for _ in range(N + 2)]
for i in range(N + 1) :
    lim[i+1] = (lim[i] - v[i]) * 2

for i in range(N, -1, -1):
    if (v[i] + nd > lim[i]):
        nd = (nd + 1) // 2
        if (v[i] + nd > lim[i]):
            print(-1)
            sys.exit(0)

    nd += v[i]
    ans += nd

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

n = int(input())

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

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

for i in range(n + 1):
    if i == 0:
        down_max[0] = 1
    else:
        down_max[i] = 2 * (down_max[i - 1] - a_i[i - 1])

answer = 0
now_point_number = 0
before_point_number = 0
cant_make = False

for i in range(n + 1):
    depth_index = - i - 1
    if i == 0:
        now_point_number = a_i[depth_index]
    else:
        if before_point_number // 2 + before_point_number % 2 + a_i[depth_index] > down_max[depth_index]:
            cant_make = True
            break
        else:
            now_point_number = min(down_max[depth_index], before_point_number + a_i[depth_index])
    answer += now_point_number
    before_point_number = copy.copy(now_point_number)

if n == 0 and a_i[0] == 0:
    cant_make = True

if cant_make:
    print(-1)
else:
    print(answer)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ####################
    import sys
    class Lazysegtree():
        """RAQ
        外から使うのは，query，add,updateくらいか
        
        """
        def __init__(self, A, intv, initialize = True, segf = min):
            """
            Aが初期配列，intvが単位元,segfが評価関数
            """
            
            #区間は 1-indexed で管理
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.intv = intv
            self.segf = segf
            self.lazy = [0]*(2*self.N0)
            if initialize:
                self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [intv]*(2*self.N0)

        def _ascend(self, k):
            k = k >> 1
            c = k.bit_length()
            for j in range(c):
                idx = k >> j
                self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1]) \
                + self.lazy[idx]
                
        def _descend(self, k):
            k = k >> 1
            idx = 1
            c = k.bit_length()
            for j in range(1, c+1):
                idx = k >> (c - j)
                ax = self.lazy[idx]
                if not ax:
                    continue
                self.lazy[idx] = 0
                self.data[2*idx] += ax
                self.data[2*idx+1] += ax
                self.lazy[2*idx] += ax
                self.lazy[2*idx+1] += ax
        
        def update(self, k, x):
            #データの変更
            k = k + self.N0
            self.data[k] = x
            self._ascend(k)
        
        def query(self, l, r):
            #クエリ，[l,r)かな
            L = l+self.N0
            R = r+self.N0
            Li = L//(L & -L)
            Ri = R//(R & -R)
            self._descend(Li)
            self._descend(Ri - 1)
            
            s = self.intv                                                              
            while L < R:
                if R & 1:
                    R -= 1
                    s = self.segf(s, self.data[R])
                if L & 1:
                    s = self.segf(s, self.data[L])
                    L += 1
                L >>= 1
                R >>= 1
            return s
        
        def add(self, l, r, x):
            #区間加算，[l,r)かな
            L = l+self.N0
            R = r+self.N0

            Li = L//(L & -L)
            Ri = R//(R & -R)
            
            while L < R :
                if R & 1:
                    R -= 1
                    self.data[R] += x
                    self.lazy[R] += x
                if L & 1:
                    self.data[L] += x
                    self.lazy[L] += x
                    L += 1
                L >>= 1
                R >>= 1
            
            self._ascend(Li)
            self._ascend(Ri-1)

            
    ##########
    
    mod=10**9+7
    N=I()
    A=LI()
    A[-1]-=1
    if A[0]!=0:
        if N==0 and A[0]==1:
            ans=1
        else:
            ans=-1
            
    else:
        ans=N+1
        now=0#キャパがある最上位
        seg=Lazysegtree([1]*(N+1), 10**10, True, min)
        for i in range(1,N+1):
            a=A[i]
            if ans==-1:
                break
            while a>0:
                if now==i:
                    ans=-1
                    break
                
                cap=seg.query(now,now+1)
                #print("i:",i,",a:",a,",now:",now,",cap:",cap,",ans",ans)
                if a>=cap:
                    a-=cap
                    #seg.add(now,now+1,-cap)，now+=1するのでいらない
                    seg.add(now+1,i,cap)
                    ans+=(i-now)*cap
                    now+=1
                    #print(now,cap)
                else:
                    #print(now,cap,"--")
                    
                    seg.add(now,now+1,-a)
                    seg.add(now+1,i,a)
                    ans+=(i-now)*a
                    a=0
                    


                
            
            
    print(ans)
        

main()

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()))
node=[1 for _ in range(N+1)]
Sn=sum(A)
S=[Sn]
for s in range(N):
    S.append(S[s]-A[s+1])

ans=1
for i in range(1,N+1):
    if node[i-1]*2<=S[i-1]:
        ans+=node[i-1]*2
        node[i]=node[i-1]*2
    elif node[i-1]<=S[i-1]<node[i-1]*2:
        node[i]=S[i-1]
        ans+=S[i-1]
    node[i]-=A[i]
    if node[i]<0:
        ans=-1
        break

if A[0]>0:
    ans=-1

print(ans)

Submission status: Wrong Answer

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

#N+1 N
B=[0]
C=[0,0]
a=True
for i in range(N):
    B.append(A[N-i]+B[i]//2)
    if B[1+i]%2==0:
        C.append(B[1+i]/2)
    else:
        print(-1)
        a=False
        break
B.append(1)
if a==True:
    for i in range(N):
        if B[i]<C[i]:
            print(-1)
            a=False
            break
    if a==True:
        print(sum(B))

Submission status: Wrong Answer

Solution code:
a = int(input())
b = input().split(" ")
g = (2 * a) + 1
print(g)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e25)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

num = sum(a)
ans = 0
ko = 1
for i in range(N):
  ans += ko
  ko -= a[i]
  num -= a[i]
  ko = min(ko*2, num)

  if ko <= 0:
    print(-1)
    break
else:
  ans += ko
  print(ans)

Submission status: Wrong Answer

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

if alist[0]!=0:
    if n==0:
        print(1)
    else:
        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
        #print(alist[-1], oya)
    answer+=alist[-1]
    
    if ng==1:
        print(-1)
    else:
        print(answer)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
p = list(map(int, input().split()))
sum_p = sum(p)-1
ans = 1
tmp = 1 - p[0]

for i in range(n):
    if sum_p:
        if sum_p < tmp:
            tmp += sum_p
            sum_p = 0
        else:
            sum_p -= tmp
            tmp *= 2    
    ans += tmp
    tmp -= p[i+1]
    if tmp < 0 or (tmp==0 and i<n-1):
        print(-1)
        sys.exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))

res = [1]
res3 = [1]
for i in lst1[1:]:
    res3.append(res[-1]*2) #res3-1の値を上回った時点で不可能
    res.append(res[-1]*2-i)

#案2
if any( i <= 0 for i in res[:-1]):
    print(-1)
    exit()

#案1
"""for i in range(n):
    if res3[i]-1 < lst1[i]:
        print(-1)
        exit()"""

res2 = [0]
for i in lst1[::-1]:
    res2.append(res2[-1]+i)

res2.reverse()

ans = []
for i,j in zip(res3,res2[:-1]):
    ans.append(min(i,j))
print(*res)
print(*res3)
print(*ans)
print(sum(ans))

Submission status: Wrong Answer

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

result = sum(a) + n

print(result)

Submission status: Wrong Answer

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

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

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

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

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 = 10 ** 9 - leaf
        low = (low + 1) // 2
        lowNG = False
        divLow = low + leaf
        count = 0
        while divLow > 0:
            divLow //= 2
            count += 1
        if count > i + 1: lowNG = True
        if i < 30: maxNode = pow(2, i) - leaf
        if lowNG 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:
n = int(input())
A = list(map(int, input().split()))

B = [1]
for i in range(n):
    B.append((B[i]-A[i])*2)

C = [A[n]]

for s in B:
    if s <= 0:
        print(-1)
        exit()


for i in range(n):
    C.append(C[i]+A[n-1-i])
C = C[::-1]

num = 0
frag = 0
for i in range(n):
    if B[i] >= C[i]:
        frag = 1
    if frag == 0:
        num += B[i]
    else:
        num += C[i]
num += C[n]
print(num)

Submission status: Wrong Answer

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

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

#################################################
#################################################
#################################################
#################################################



#06

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

num = [[1,0]]

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

for i in range(n):
    here = a[1+i]
    possible = num[-1][0]*2
    num.append([possible-here,here])
    
#print(num)
num[-1][0] = 0

for i in range(n-1,-1,-1):
    if(num[i+1][0]+num[i+1][1]<num[i][0]):
        num[i][0] = num[i+1][0]+num[i+1][1]

#print(num)

if(num[n][0]>=1):
    print(-1)
    exit()

for i in range(n):
    if(num[i][0]<=0):
        print(-1)
        exit()

s = sum([sum(num[i]) for i in range(n+1)])
print(s)

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):
  B[i] = B[i-1]*2-A[i]
  if B[i]<=0:
    print(-1)
    sys.exit()
ans = sum(A)
num = 0
if all(a==0 for a in A):
  print(-1)
  sys.exit()
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:
def main():
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0
    nodes = 1
    for i in range(n+1):
        ans += nodes
        nodes -= A[i]
        if nodes < 0:
            print(-1)
            exit(0)
        nodes *= 2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
t = str(input())
s =""
for i in range(len(t)-1):
    if(i>=1):
        if(t[i]=='?'):
          if(s[-1]=="P"):
              s+="D"
          elif(s[-1]=='D')or(s[-1]=='?'):
              s += "P"
          elif(s[-1]=='P'):
              s+="D"
        else:
          s+=t[i]
    else:
        if(t[i]=='?'):
          if(t[i+1]=='D')or(t[i+1]=='?'):
              s += "P"
          elif(t[i+1]=='P'):
              s+="D"
        else:
          s+=t[i]
if(t[len(t)-1]=="?"):
    s+="D"
else:
    s+=t[len(t)-1]
print(s)

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
    if A[-1] > 2 ** N:
        print(-1)
        return
    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
    mx_nonleaves[i]=mx_nonleaves[i-1]*2-anums[i]
    if mx_nonleaves[i]<0:
      return -1
  mx_nonleaves[-1]=0
  #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 = list(map(int, input().split()))

nodes = []
if a[0] > 0:
    if a[0] == 1 and 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:
import sys
n = int(input())
p = list(map(int, input().split()))
if p[0] == 1:
    print(-1)
    sys.exit()
sum_p = sum(p)-1
ans = 1
tmp = 1

for i in range(n):
    if sum_p:
        if sum_p < tmp:
            tmp += sum_p
            sum_p = 0
        else:
            sum_p -= tmp
            tmp *= 2    
    ans += tmp
    tmp -= p[i+1]
    if tmp < 0 or (tmp==0 and i<n-1):
        print(-1)
        sys.exit()
print(ans)

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)
if R[-1]<A[-1]:
    print(-1)
    exit()
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:
n=int(input())
a=list(map(int,input().split()))
ok=True

v=[0 for i in range(n+2)]

for i in reversed(range(n+1)):
    if 2**i>=v[i+1]+a[i]:
        v[i]=v[i+1]+a[i]
    else:
        v[i]=2**i

    # if i<n:
    #     if 2**i-a[i]<(v[i+1]+1)//2:
    #         ok=False

for i in range(1,n+1):
    if v[i-1]-a[i-1]<0:
        ok=False
        break
    if (v[i-1]-a[i-1])*2<v[i]:
        v[i]=(v[i-1]-a[i-1])*2

if a[0]!=0:ok=False

if ok:
    print(sum(v))
else:
    print(-1)

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 = 10 ** 8 - leaf
        low = (low + 1) // 2
        lowNG = False
        divLow = low + leaf
        count = 0
        while divLow > 0:
            divLow //= 2
            count += 1
        if count > i + 1: lowNG = True
        if i < 30: maxNode = pow(2, i) - leaf
        if lowNG 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:
import sys
readline = sys.stdin.readline

def check():
    R = [0]*(N+1)
    R[0] = 1
    for i in range(N):
        if R[i] < A[i]:
            return -1
        R[i+1] = 2*(R[i]-A[i])
    
    
    CA = A[:]
    
    for i in range(N-1, -1, -1):
        CA[i] += CA[i+1]
    
    
    return sum(min(r, c) for r, c in zip(R, CA))


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

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

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
if all(a==0 for a in A):
  print(-1)
  sys.exit()
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())+1
ali = list(map(int,input().split()))
nli = [0]*N

maxn = 2**(N-1)
nli[-1] = ali[-1]

for i in range(1,N+1):
  nli[-i] = min(maxn,nli[-i+1] + ali[-i])
  maxn //= 2
  

ulim = 1
for i in range(N):
  nli[i] = min(nli[i],ulim)
  ulim = (ulim - ali[i])*2
  if i != N-1 and ulim <= 0:
    print(-1)
    exit()
  
print(sum(nli))

Submission status: Wrong Answer

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

# nmleaves[i]: no. of leaves at depth i. (root node has 0 depth)

# pref[i]: sum of all elements in nmleaves after i, i.e. sum(nmleaves[i+1:])
full = sum(nmleaves)
tot = 0
pref = [0]*(n+1)
for i, l in enumerate(nmleaves):
    tot += l
    pref[i] = full - tot

if n==0:
    print(0)

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

    for i, num in enumerate(nmleaves[1:]):
        if num > 2**(i+1):
            print(-1)
            exit()
    
    ## it exists
    ans = 0
    for level, leaves in enumerate(nmleaves):
        if level == 0:
            ans += 1
            validnom = 1
        else:
            maxup = 2*validnom
            maxnom = maxup - leaves

            if level+1<len(nmleaves):
                validnom = min(maxnom, pref[level])
                ans += leaves
                ans += validnom
            else:
                ans += leaves

    print(ans)