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:
from math import log2

N = int(input())
A = [int(i) for i in input().split()] + [0]

def solve() :
  M = [1]
  pre = 1
  for i in range(N) :
    M.append(pre * 2)
    pre = pre * 2 - A[i + 1]
    if (A[i + 1] + 1) // 2 + A[i] == 0 or i < log2((A[i + 1] + 1) // 2 + A[i]) :
      return -1
  
  ret = A[-2]
  pre = A[-2]
  for i in range(N - 1, -1, -1) :
    cur = min(M[i], A[i] + pre)
    ret += cur
    pre = cur
  
  return ret
  
print(solve())

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
li = list(map(int,input().split()))
if li[0]!=0:
    print(-1)
    exit()

tmp = 1
for i,l in enumerate(li):
    if i == 0:
        continue
    tmp *= 2
    if l > tmp:
        print(-1)
        exit()
    else:
        tmp -= l

max_li = [1]
for i,l in enumerate(li):
    if i == 0:
        continue
    la = (max_li[-1]-li[i-1])*2
    max_li.append(la)
max_li.reverse()


li.reverse()
ans = 0
codomo = li[0]
for i,l in enumerate(li):
    if i == 0:
        if l > 2**(n-i):
            print(-1)
            exit()
        else:
            ans += codomo
    else:
        tmp = codomo + l
        fin = min(min(2**(n-i),tmp),max_li[i])
        #print(min(2**(n-i),tmp),max_li[i],i,'i')
        ans += fin
        codomo = fin
    #print(ans,'ans')
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
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 m[0]<=a[0]or m[0]!=1:
    print(-1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
# 0や1のケースに注意
# index out of range
# 貪欲

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    l = list(map(int, input().split()))
    limit = [1-l[0]]
    total = 0
    if n == 0:
        if l[0] == 1:
            print(1)
            exit()
        else:
            print(-1)
            exit()
    for i in range(1, n+1):
        total = total*2 + l[i-1]*2
        limit.append(pow(2, i) - total)

    for i in limit:
        if i <= 0:
            print(-1)
            break
    else:
        res = []
        temp = 0
        flag = 1
        for i in range(n, -1, -1):
            if limit[i] > temp+l[i] and flag == 1:
                temp = temp+l[i]
            else:
                temp = limit[i]
                flag = 0
            res.append(temp)
        print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
D = [0 for _ in range(N,-1,-1)]
prev = 0
for i in range(N,-1,-1):
    D[i] = prev + A[i]
    prev = D[i]
prev = 1
for i in range(N+1):
    tmp = min(2**i,prev*2)
    if D[i] > tmp:
        D[i] = tmp
    prev = tmp-A[i]
for i in range(N,-1,-1):
    tmp = 0
    if i != N:
        tmp = (A[i+1]+1)//2
    if tmp+A[i] > 2**i:
        print(-1)
        exit()
print(sum(D))

Submission status: Wrong Answer

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

ch = [1]

cH = [1]
if A[0]>0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
    # ch.append((cH[-1]*2)//(2**i))
# print(ch)
# print(cH)
# ch = ch[:-1]
# ch = ch[::-1]
# ch[0]*=2
# print(ch)
cH = cH[:-1]
cH.append(cH[-1]*2)
cH = cH[::-1]
# print(cH)
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:-1]):
    # print(n,ch[e],-1)
    if n//2>cH[e]:
        print(-1)
        exit()
    if n  <= cH[e]:
        # print('ans:',ans,'n:',n)
        ans += n+i
        n+=i
    else:
        # print('ans:',ans,'ch:',cH[e],'i:',i)
        ans +=cH[e]+i
        n = cH[e]+i

    # print('ans:',ans,'n:',n)
print(ans+1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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


ans = 0
root = 0
for depth in range(n, -1, -1):
    depth_nodes = root + a[depth]
    ans += depth_nodes
    if depth_nodes > 2 ** depth:
        print(-1)
        break
    root = depth_nodes // 2 + depth_nodes % 2
else:
    print(ans)

Submission status: Wrong Answer

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

MAX = []
e = 1
for a in A:
    if e > 0:
        MAX.append(e)
        e -= a
        e *= 2
    else:
        print(-1)
        exit()

A.reverse()
MAX.reverse()
ans = 0
s = 0
for i,a in enumerate(A):
    s += a
    ans += min(MAX[i],s)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10


    N = II()
    A = LMIIS()


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


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


    sum_top = 1

    top = 1
    tmp = 1
    
    for i in range(1,N+1):
        max_l = tmp*2
        if max_l >= max_nodes[i]:
            print(sum_top+sum(max_nodes[i:]))
            return
        sum_top += max_l
        tmp = max_l - A[i]

    dbg(sum_top)
    print(-1)


main()

Submission status: Wrong Answer

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

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

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])
        fixed_nodes[i] += A[i]
    print(sum(fixed_nodes))

Submission status: Wrong Answer

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

ch = [1]

cH = [1]
if A[0]>0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
    # ch.append((cH[-1]*2)//(2**i))
# print(ch)
# print(cH)
# ch = ch[:-1]
# ch = ch[::-1]
# ch[0]*=2
# print(ch)
cH = cH[:-1]
cH.append(cH[-1]*2)
cH = cH[::-1]
# print(cH)
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:-1]):
    # print(n,ch[e],-1)
    if n//2>cH[e]:
        print(-1)
        exit()
    if n  < cH[e]:
        # print('ans:',ans,'n:',n)
        ans += n+i
        n+=i
    else:
        # print('ans:',ans,'ch:',cH[e],'i:',i)
        ans +=cH[e]+i
        n = cH[e]+i

    # print('ans:',ans,'n:',n)
print(ans+1)

Submission status: Wrong Answer

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

ans=0
bef=0

tmp=[]

for i in range(N+1):
    if i==0:
        if A[0]==1:
            bef=0
        elif A[0]>1:
            print("-1")
            exit()
        elif N==0 and A[0]==0:
            print("-1")
            exit()
        else:
            bef=1
        tmp.append(1)
        continue
    elif (bef*2-A[i])>=0:
        bef=bef*2-A[i]
        tmp.append(bef)
    else:
        print("-1")
        exit()

for i in range(N+1):
    current=A[-(i+1)]
    if i==0:
        bef=current
        ans+=current
        continue
    else:
        tmpp = tmp[-(i+1)]
        if current+bef > tmpp:
            ans+=tmpp+current
            bef=tmpp+current
        else:
            ans+=current+bef
            bef=current+bef

if ans==0:
    ans=-1    

print(ans)

Submission status: Wrong Answer

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

if ha[0] != 0:
    print(-1)
elif n == 0 and ha[0] == 1:
    print(1)
else:
    oya = [[0,0] for i in range(n+1)]
    ten = [[0,0] for i in range(n+1)]
    ten[n] = [ha[n],ha[n]]
    for i in reversed(range(n)):
        oya[i] = [int((ten[i+1][0]+1)/2),(ten[i+1][1])]
        ten[i] = [oya[i][0] + ha[i], oya[i][1] + ha[i]]

    if 1 < oya[0][0] or oya[0][1] < 1 or 1 < ten[0][0] or ten[0][1] < 1:
        print(-1)
    else:
        oya[0] = 1
        ten[0] = 1
        for i in range(1,n+1):
            ten[i] = min(oya[i-1]*2, ten[i][1])
            oya[i] = ten[i]-ha[i]
        print(sum(ten))

Submission status: Wrong Answer

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

MAX = [1] * (N+1)
ans = [0] * (N+1)
INF = 10**15

for i in range(1, N+1):
    MAX[i] = min((MAX[i-1] - A[i-1]) * 2, INF)
    if MAX[i] < A[i]:
        print(-1)
        exit()

ans[N] = A[N]

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

print(sum(ans))

Submission status: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = list(mapi())
res =a[n]
mp = [min(2**(i),int(1e8)) for i in range(n+1)]
#print(*mp)
lst = 1
pst = [0]*(n+1)
for i in range(n+1):
    #print(lst,a[i])
    #res+=lst
    pst[i] = lst
    lst-=a[i]
    lst*=2
#print(*pst,"c")
#print(*mp,"d")
mx = a[n]
for i in range(n-1,-1,-1):
    if a[i]>=mp[i] or a[i]>pst[i]:
        res = -1
        break
    mx = min(mx+a[i],mp[i])
    res+=min(mx,pst[i])
    #print(res,mx,mp[i],a[i])
print(res)

Submission status: Wrong Answer

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

node_max = [1]
for i in range(1, n+1):
    node_max.append(min(10**9, node_max[i-1]*2-a[i]))

a.reverse()
node_max.reverse()

node_max
ans = 0
main = 0
node_max.append(0)


flag = 1

for i in range(n+1):
    main = min(main+a[i], node_max[i+1])
    ans += main + a[i]
    if i == 0:
        continue
    if (main+a[i]) > node_max[i+1]*2:
        flag = 0
        break


if flag == 1:
    print(ans)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
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] and j!=n)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 m[0]<=a[0]or m[0]!=1:
    print(-1)
else:
    print(count)

Submission status: Wrong Answer

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

cnt = 0
ans = 0

if n==0:
    if a[0] == 1:
        cnt = 1
    else:
        cnt = -1
else:
    setsu = 1
    if a[0] != 0:
        cnt = -1
    else:
        setsu = 1
        cnt = 0
        for i in range(1,n+1):
            ha = a[i]
            ha_max = setsu*2
            if ha > ha_max:
                cnt = -1
                break
            else:
                if i != n:
                    cnt += ha + setsu
                    setsu = ha_max - ha
                else:
                    cnt += ha + (ha//2 + ha%2)

print(cnt)

Submission status: Wrong Answer

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

lis = [1]
for i in range(n):
    cc = lis[-1] - a[i]
    cc *=2
    if cc<=0:
        hantei=1
    lis.append(cc)

print(lis)



for i in range(n+1):
    tmp = a[-1-i]+cir
    sum += tmp
    #print(tmp,cir)
    if i==n:
        break
    if tmp <= lis[-1-i] and tmp+a[-2-i]>lis[-2-i]:
        if tmp%2==0:
            cir = tmp//2
        else:
            cir = tmp//2+1
    else:
        cir = tmp
if hantei==1:
    print(-1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [1]
if a[0] != 0:
    print(-1)
    exit()
cnt = 2
ans = 1
for i in range(1, n+1):
    if i != n:
        if a[i] > cnt//2:
            ans = -1
            break
        l.append(a[i]+(cnt-a[i])//2)
        ans += cnt
        cnt -= a[i]
        cnt *= 2
    if i == n:
        if cnt < a[i]:
            ans = -1
        else:
            ans += cnt
            l.append(cnt//2)
            ind = -1
            while cnt > a[i]:
                if cnt - l[ind] <= a[i]:
                    ans += (cnt - a[i]) * ind
                    cnt = a[i]
                else:
                    cnt -= l[ind]
                    ans += l[ind] * ind
                ind -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, *A = map(int, open(0).read().split())

cnt = [0] * (N + 1)
cnt[0] = 1
exists = True
for i in range(N):
    if i > 45:
        cnt[i + 1] = cnt[i] - A[i]
    else:
        cnt[i + 1] = (cnt[i] - A[i]) * 2

ans = A[-1]
cur = A[-1]
for i in reversed(range(N)):
    cur += A[i]
    ans += min(cnt[i], cur)
        
if exists:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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


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


for i in range(N):
    r[i] -= A[i]


q = A[N]
ans = q

for i in range(N):
    q = min(q,r[N-1-i]) + A[N-1-i]
    ans += q
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list( map(int, input().split()) )
B = [i for i in A]

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())

a = input().split()
c = 0
result = 0

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

for i in range(n+1):
    if (c + int(a[n - i])) < (2 ** (n - i)):
        c = c + int(a[n - i])
    else:
        c = 2 ** (n - i)
    result = result + c

print(result)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
a=1
k=0
f=0
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
  if a<=0 and i!=len(g)-1:
    f+=1
    break
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  if l[0]==1:
    print(1)
  else:
    print(-1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:

from math import ceil
N = int(input())
A = list(map(int, input().split()))
if(A[0] > 0):
    print(-1)
    exit(0)
# curは作り出せる最大ノード数
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)
for i in range(1, N):
    if(A[i] > cur):
        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) + 3)
'''
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)

'''

Submission status: Wrong Answer

Solution code:
N = int(input())
failed = False
n_node = 0
n_node_current = 1
n_node_parent  = 0
A = [ int(Ai) for Ai in input().strip().split(' ')]

for i, Ai in enumerate(A):
    if (i == 0) and (Ai != 0):
        failed = True
        break
    
    n_node_current = 1 if (i == 0) else min((n_node_parent - Ai_parent) * 2, sum(A[i:]))
    if n_node_current <= 0:
        failed = True
        break

    n_node += n_node_current    
#    print(n_node_parent, n_node_current, n_node)

    n_node_parent = n_node_current
    Ai_parent = Ai
    
if failed:
    print('-1')
else:
    print(n_node)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
a = LI()
for i in range(n):
    if a[i] > 2**i - 1:
        print(-1)
        quit()
if a[-1] > 2**n:
    print(-1)
    quit()


lst = [1]
for i in range(1, n):
    l = lst[-1] - a[i-1]
    if l <= 0:
        print(-1)
        quit()
    lst.append(2*l)
lst.append(a[-1])
i = n-1
tmp = a[-1]
ans = 0
lst2 = [a[-1]]
while i >= 0:
    tmp += a[i]
    tmp = min(tmp, 2**i)
    lst2.append(tmp)
    i -= 1
lst2 = lst2[::-1]
for i in range(n+1):
    ans += min(lst[i], lst2[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
saidaiA =[]
oya = 1
flag = True
for i in range(len(A)):
    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: Wrong Answer

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]
    if A[i-1] > 0:
        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
    if d[i-1]*2 < x:
        print(-1)
        exit()
    d[i-1] = min(x, d[i-1]+A[i-1])
print(sum(d))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
P = [2**i for i in range(len(A))]
import sys
sys.setrecursionlimit(10**9)
# A = A[::-1]
# P = P[::-1]

# ans = 0
# node = 0
# for i in range(len(A)-1):
#     node = node + A[i]
#     node = min(node,2 * (P[i+1] - A[i+1]))
#     ans += node
#     if node <= 0:
#         print (-1)
#         exit()
#     print (node)
    
# ans += 1
# print (ans)

if A[0] > 0:
    print(-1)
    exit()
if A[-1] > 2**N:
    print (-1)
    exit()

ans = [0]
node = [0]
def rec(i):
    if i==0:
        ans[0]+=1
        return 1
    node[0] = node[0] + A[i]
    node[0] = min(node[0], 2*rec(i-1))
    ans[0] += node[0]
    #print (node[0],node[0]-A[i])
    if i!=N and node[0] - A[i] <= 0:
        print(-1)
        exit()
    return node[0] - A[i]
rec(N)
print (ans[0])

Submission status: Wrong Answer

Solution code:

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # 各 depth における最小値
  min_node_in_depth = [0] * (len(A))
  min_node_in_depth[-1] = max_node_in_depth[-1]
  start_index = -1
  for i in range(1, len(A)):
    min_node_in_depth[start_index-i] = -(-min_node_in_depth[start_index-i + 1] // 2) + A[start_index-i]

  node = [0] * (len(A))
  node[0] = 1

  for i in range(1, len(A)):
    num_of_node = (node[i - 1] - A[i - 1]) * 2
    if num_of_node < min_node_in_depth[i]:
      print(-1)
      return True

    if num_of_node <= max_node_in_depth[i]:
      node[i] = num_of_node
    else:
      node[i] = max_node_in_depth[i]

  print(sum(node))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
cnt = 0
dic = defaultdict(int)
prv = -1
ans = 0
nya = False
max_ = 0
for i in range(n+1):
    if i == 0:
        if A[i] == 0:
            max_ = max(A[i],max_)
            dic[0] = 1
            cnt += 1
        else:
            print(-1)
            exit()
    else:
        if max_ - 1 <= A[i]:
            if not dic[A[i]]:
                max_ = max(A[i],max_)
                dic[A[i]] = 1
                ans += A[i] * cnt
                max_ = max(A[i],max_)
            else:
                if A[i] != 0:
                    dic[A[i]] += 1
                    ans += cnt * dic[A[i]]
                    #cnt += 1
                    cnt += 1
                    max_ = max(A[i],max_)
                else:
                    cnt += 1
        else:
            print(-1)
            exit()
    #print(ans)
print(ans)

Submission status: Wrong Answer

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

ans = 0
prev = 1
M = max(A)
L = [0]*(N+1)
L[0] = 1
for i in range(1, N+1):
    if prev*2 > A[i]:
        prev = prev*2-A[i]
    elif prev*2 == A[i] and i == N:
        continue
    else:
        ans = -1
        break
    L[i] = prev
    if prev > 10**10:
        for j in range(i+1, N+1):
            L[j] = "inf"
        break

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

if ans == 0:
    num = A[-1]
    ans += A[-1]
    for i in range(N, 0, -1):
        if L[i-1] == "inf" or num+A[i-1] <= L[i-1]:
            num += A[i-1]
        else:
            num = L[i-1]+A[i-1]
        ans += num
    print(ans)

else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = list(mapi())
res =a[n]
mp = [min(2**(i),int(1e8)) for i in range(n+1)]
#print(*mp)
lst = 1
pst = [0]*(n+1)
for i in range(n+1):
    #print(lst,a[i])
    #res+=lst
    pst[i] = lst
    lst-=a[i]
    lst*=2
#print(*pst,"c")
#print(*mp,"d")
mx = a[n]
for i in range(n-1,-1,-1):
    if a[i]>=mp[i] or a[i]>=pst[i]:
        res = -1
        break
    mx = min(mx+a[i],mp[i])
    res+=min(mx,pst[i])
    #print(res,mx,mp[i],a[i])
print(res)

Submission status: Wrong Answer

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 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(last+1):
                ans += B[k]
            break
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()))
if n == 0:
    if lst1[0] == 0:
        print(1)
        exit()
    else:
        print(-1)
        exit()
if lst1[0] != 0:
    print(-1)
    exit()
res2 = [0]
for i in lst1[::-1]:
    res2.append(res2[-1]+i)

res2.reverse()
INF = res2[0]
res = [1] 
res3 = [1]
for i in range(1,len(lst1)):
    res3.append(min(INF,res[-1]*2))
    cache = res[-1]*2-lst1[i]
    if cache <= 0 and i != n:
        print(-1)
        exit()
    elif cache < 0 and i == n:
        print(-1)
        exit()
    res.append(min(INF,cache))

ans = 0
res2 = res2[:-1]
for i in range(len(res3)):
    ans += min(res2[i],res3[i])
print(ans)

Submission status: Wrong Answer

Solution code:
def main():

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

    C1 = [[1, 1]]
    B1 = [[1-A[0], 1-A[0]]]
    for i in range(1, N+1):
        if 2*B1[-1][1] < A[i]: return -1
        x, y = max(B1[-1][0]-A[i], 0), 2*B1[-1][1] - A[i]
        B1.append([x, y])
        C1.append([x+A[i], y+A[i]])
    if A[N] < C1[-1][0] or A[N] > C1[-1][1]:
        return -1
    C1.append([A[N], A[N]])
    # print(C1)

    C2 = [A[N]]
    for i in range(N-1, 0, -1):
        x, y = (C2[-1] + 1) // 2, C2[-1]
        z = 0
        if y < B1[i][0] or x > B1[i][1]: return -1
        if B1[i][0] <= y < B1[i][1]:
            z = y
        else:
            z = B1[i][1]
        C2.append(z + A[i])
    # print(C2)

    return sum(C2) + 1

    # return ans

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

Submission status: Wrong Answer

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

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

maxs = [1]

for i in range(1,n+1):
    nex = maxs[i-1]*2 - a[i]
    maxs.append(nex)

if(maxs[n] < 0):
    print('-1')
    sys.exit()

results = [a[n]]

for i in range(n):
    if(results[i] > maxs[n-i-1]):
        results.append(maxs[n-i-1]+a[n-i-1])
    else:
        results.append(results[i]+a[n-i-1])


print(sum(results))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A[0] == 1:
            print(1)
        else:
            print(-1)
    ans = 2 ** (N + 1) - 1
    # last_leaf = 2 ** N
    actual_last_leaf = A[-1]
    len_list = []
    current_len = 1
    for depth, leafs in enumerate(A):
        ans -= leafs * (2 ** (N - depth + 1) - 2)
        # last_leaf -= leafs * (2 ** (N - depth))
        len_list.append(current_len - leafs)
        current_len = (current_len - leafs) * 2
    # print(A)
    # print(len_list)
    # print([A[i] + len_list[i] for i in range(N + 1)])
    last_leaf = len_list[-1]
    if last_leaf < 0:
        print(-1)
        return
    must_delete = last_leaf
    # print(must_delete)
    for _depth, x in enumerate(len_list[::-1]):
        depth = N - _depth
        leaf = A[depth]
        if must_delete <= (x+leaf)//2:
            ans -= must_delete
            print(ans)
            return
        ans -= must_delete
        must_delete -= (x+leaf)//2
    print(-1)
    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:
N=int(input())
A=list(map(int,input().split()))
if N>0 and A[0]>0:
    print(-1)
    exit()
b=[1]
for i in range(1,N):
    if b[-1]*2<A[i]:
        print(-1)
        exit()
    b.append(b[-1]*2-A[i])
b.append(0)
c=[]
for i in range(N,-1,-1):
    if i>0 and b[i-1]*2<A[i]+b[i]:
        print(-1)
        exit()
    if i>0 and b[i-1]>A[i]+b[i]:
        b[i-1]=A[i]+b[i]
    t=A[i]+b[i]
    c.append(t)
print(sum(c))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = [0]*(n+1)
y = 1
p = 0
for i in range(n+1):
    if(y-a[i] > 0):
        s[i] = y
        y -= a[i]
        y *= 2
    else:
        if(i != n):
            print(i,n)
            p = -1
            break
        elif(y == a[i]):
            s[i] = y
if(p == -1):
    print(-1)
else:
    q = 0
    for i in range(n+1):
        q += a[-1-i]
        if(q <= s[-1-i]):
            p += q
        else:
            p += s[-1-i]
    print(p)

Submission status: Wrong Answer

Solution code:
n = int( input() )
p = [ int( pi ) for pi in input().split() ]

sump = int( 0 )
for pi in p:
    sump += pi

ans = int( 0 )
for i in range( n+1 ):
    if i == 0:
        ans += 1
        px = 1
        if p[ i ] != 0:
            ans = -1
            break
    else:
        if px*2 <= sump:
            ans += px*2
            px = px*2 - p[ i ]
            sump = sump - p[ i ]
        else:
            ans += sump
            px = sump - p[ i ]
            sump = sump - p[ i ]
#        print( px, sump )
        if i != n and px <= 0:
            ans = -1
            break
        elif i == n and sump != 0:
            ans = -1
            break

print( ans )