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())
ha = list(map(int,input().split()))

if ha[0] != 0:
    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()))
if a[0] != 0:
    print(-1)
    exit()
acc = [0 for i in range(n+1)]
acc[-1] = a[-1]
for i in range(n, 0,-1):
    acc[i-1] = acc[i] + a[i-1]
ans = count = 1
for i in range(1,n+1):
    count *= 2
    if count > acc[i] - a[i]:
        count = (acc[i] - a[i])
        ans += a[i]
    ans += count
    count -= a[i]
if count != a[-1] * (-1):
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
#len(A)=N+1
ak=1-A[0]
a=[ak]
for k in range(N):
    ak=2*ak-A[k+1]
    if ak<0:
        print(-1)
        exit()
    if ak>=10**8:
        #以降に関わらず構成可能
        break
    a.append(ak)
M=len(a)
for k in range(N,0,-1):
    if k-1<M:
        A[k-1]+=min(A[k],a[k-1])
    else:
        A[k-1]+=A[k]
        continue
print(sum(A))

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
a = sum(A)

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

B = [0]*(N+1)  #深さiの頂点数のmax
B[0] = 1

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

ans = A[N]

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

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

right=1
for i,x in enumerate(A):
    if x>right:
        print(-1)
        exit()
    right-=x
    right*=2
    right=min(right,10**10)

ans=1
tmp=0
M=[1]

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

for i,x in enumerate(A[1:],1):
    if i>=65:
        n=2**65
    else:
        n=2**i
    M.append(min(n-x,M[i-1]*2-x))
    if (i!=N and M[i]<=0) or (i==N and M[i]<0):
        print(-1)
        exit()
for i,(x,y) in enumerate(zip(A[1:][::-1],M[1:][::-1])):
    tmp+=x
    tmp=min(tmp,n,y+x)
    ans+=tmp
if A[0]+M[0]>1:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

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

ok = True
max_l =[1-A[0]]

for i in range(1,N+1):
    max_l.append(min(max_l[i-1] * 2 - A[i], 1e10))
    if max_l[i] < 0 :
        ok=False

ans = A[N]
now = A[N]

for i in reversed(range(N)):
    now_l = min(now,max_l[i])
    now = now_l + A[i]
    ans += now

if ok == False:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

if N == 0:
    if A_list[0] == 1:
        print(0)
    else:
        print(-1)
elif A_list[0] != 0:
    print(-1)
elif N == 1:
    if A_list[1] == 1 or A_list[1] == 2:
        print(A_list[1] + 1)
    else:
        print(-1)
else:
    ans = 1
    deathable_node = 1
    sum_rest_A = sum(A_list)
    for i in range(1, N + 1):
        now_A = A_list[i]
        deathable_node = min(sum_rest_A, deathable_node * 2) - now_A

        if deathable_node < 0:
            print(-1)
            break

        sum_rest_A -= now_A
        ans += deathable_node + now_A
#         print(i, now_A, sum_rest_A, deathable_node, ans)
        if deathable_node == 0 and i != N:
            print(-1)
            break
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    suma = sum(a)
    ans = a[0]
    can = 1
    for i,ai in enumerate(a):
        if ai > can:
            print(-1)
            exit()
        suma -= ai
        ans += can
        if (can-ai)*2 >= suma:
            can = suma
        else:
            can = (can-ai)*2

    print(ans)




    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
# step 1 後ろからの累積
cum = [0] * (n + 1)
cum[n] = a[n]
for i in range(n):
    cum[n - 1 - i] = cum[n - i] + a[n - 1 - i]
# step2 dpを更新する
# dp はその深さに存在する頂点の数
dp = [0] * (n + 1)
dp[0] = 1
ans = dp[0]
ng = 0
for i in range(n):
    dp[i + 1] = min(2 * (dp[i] - a[i]), cum[i + 1])
    if dp[i + 1] <= 0:
        ng = 1
    ans += dp[i + 1]
if n == 0:
    if a[0] == 1:
        print(1)
    else:
        print(-1)
elif ng:
    print(-1)
else:
    print(ans)
# -1 ではないケースで落ちてる

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*(n+1)
c=[0]*(n+1)
flg=True
ans=0
if a[n]>2**n:
  print(-1)
else:
  b[n]=a[n]
  c[0]=1
  for i in range(n-1,-1,-1):
    b[i]=b[i+1]+a[i]
  for i in range(1,n+1):
    
    c[i]=2*(c[i-1]-a[i-1])
  
  for i in range(n+1):
    if c[i]<=0:
      flg=False
  
  
  for i in range(n+1):
    ans+=min(b[i],c[i])
  if flg:
    
    print(ans)
  else:
    print(-1)

Submission status: Wrong Answer

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

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

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

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

# print(tree)
tree[-1] = a_l[-1]
for i in range(2,n+2):
    # print(i, tree[-i], tree[-(i-1)] + a_l[-i])
    if tree[-i] == tree[-(i-1)] + a_l[-i]:
        break
    else:
        tree[-i] = min(tree[-i], tree[-(i-1)] + a_l[-i])
    # print(tree)
# print(tree)

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = 10**9


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

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

    # 利用可能頂点をメモ
    available = [0]*(N+1)
    available[0] = 1
    for i in range(1, N+1):
        available[i] = available[i-1]*2-A[i]
    # print(available)

    ans = 0
    # 後ろから見ていく
    for i in range(N, 0, -1):
        # print(A[i])
        if A[i] <= available[i-1]:
            # 独立型
            ans += A[i]
            A[i-1] += A[i]
        elif A[i] <= 2*available[i-1]:
            ans += A[i]
            A[i-1] += available[i-1]
        else:
            print(-1)
            return
    print(ans+1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

if N != 0:

    if A[0] != 0:
        flag = -1
    if A[-1] == 0:
        flag = -1

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

    M = [-1]*N
    M[0] = 2
    for i in range(1,N):
        M[i] = (M[i-1]-A[i])*2
        if M[i] < 0:
            flag = -1
    #print(S,M)

    if flag != -1:
        V = [-1]*N
        for i in range(N):
            if S[i] > M[i]:
                V[i] = M[i]
            else:
                V[i] = S[i]
        ans = sum(V)+1
        #print(V)
        print(ans)
    else:
        print(-1)

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

Submission status: Wrong Answer

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



S = 1
OK = 0
Sum = 0

for i in range(N+1):

  
  Sum += A[i]+2**(-(-A[i] // 2)) -1
  
  if A[i] > S:
    break
  S = S - A[i]
  S = S*2
  
  if i == N-1:
    OK = 1
 

  
if OK == 0:
  print(-1)
else:
  print(Sum)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

if N == 0:
    if A_list[0] == 1:
        print(0)
    else:
        print(-1)
elif A_list[0] != 0:
    print(-1)
elif N == 1:
    if A_list[1] == 1 or A_list[1] == 2:
        print(A_list[1] + 1)
    else:
        print(-1)
else:
    ans = 1
    deathable_node = 1
    sum_rest_A = sum(A_list)
    for i in range(1, N + 1):
        now_A = A_list[i]
        deathable_node = min(sum_rest_A, deathable_node * 2) - now_A

        if deathable_node < 0:
            print(-1)
            break

        sum_rest_A -= now_A
        ans += deathable_node + now_A
        print(i, now_A, sum_rest_A, deathable_node, ans)
        if deathable_node == 0 and i != N:
            print(-1)
            break
    else:
        print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main(N, A):
    num = 1
    ans = 1
    for i in range(N+1):
        num -= A[i]
        if i < N:
            num *= 2
            ans += num
        if num <= 0 and i < N:
            return -1
    eda = 0
    for i in range(N+1):
        ans -= num
        eda += A[N-i]
        num -= eda
        num = num//2
        if num <= 0:

            break
    return ans


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

print(main(N, A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a2 = [0] * (n + 1)
d = [1] * (n + 1)
ans = 1
for i in range(n + 1):
    a2[i] = sum(a[(i + 1):])
for i in range(n):
    if d[i] - a[i] <= 0:
        ans = -1000000000000
    if (d[i] - a[i]) * 2 >= a2[i]:
        d[i + 1] = a2[i]
    else:
        d[i + 1] = (d[i] - a[i]) * 2

if ans < 0:
    ans = -1
else:
    ans = sum(d)
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import unittest


def solve(n, leafs):
    if leafs[0] == 1:
        if n == 0:
            return 1
        else:
            return -1
    left_nodes = 1
    total_node_count = 0
    usable_nodes = [1]*(n+1)
    for i in range(n):
        if leafs[i] <= left_nodes:
            total_node_count += left_nodes
            left_nodes -= leafs[i]
            left_nodes *= 2
            usable_nodes[i+1] = left_nodes
        else:
            return - 1
    # 末端のレベルは
    if leafs[-1] > left_nodes:
        return -1
    total_node_count += left_nodes
    if left_nodes + leafs[-1] > 2 ** n:
        return - 1

    max_node = [0 for i in range(n + 1)]
    max_node[n] = leafs[n]
    for i in range(n - 1, -1, -1):
        if i > 27:
            max_node[i] = min(usable_nodes[i], leafs[i]+max_node[i+1])
        else:
            max_node[i] = min(2 ** i, usable_nodes[i], leafs[i]+max_node[i+1])

    return sum(max_node)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    result = solve(n, a)
    print(result)


class Test(unittest.TestCase):
    def test_solve_1(self):
        n = 3
        a = [0, 1, 1, 2]
        actual = solve(n, a)
        expected = 7
        self.assertEqual(actual, expected)

    def test_solve_2(self):
        n = 4
        a = [0, 0, 1, 0, 2]
        actual = solve(n, a)
        expected = 10
        self.assertEqual(actual, expected)

    def test_solve_3(self):
        n = 2
        a = [0, 3, 1]
        actual = solve(n, a)
        expected = -1
        self.assertEqual(actual, expected)

    def test_solve_4(self):
        n = 1
        a = [1, 1]
        actual = solve(n, a)
        expected = -1
        self.assertEqual(actual, expected)

    def test_solve_5(self):
        n = 10
        a = [0, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
        actual = solve(n, a)
        expected = 264
        self.assertEqual(actual, expected)

    def test_solve_6(self):
        n = 5
        a = [0, 1, 1, 1, 1, 1]
        actual = solve(n, a)
        expected = 10
        self.assertEqual(actual, expected)

    def test_solve_7(self):
        n = 3
        a = [0, 1, 2, 4]
        actual = solve(n, a)
        expected = -1
        self.assertEqual(actual, expected)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


def main():

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

max_nood = sum(A)
count_nood = 0
corrent_nood = 0
ans = True

for i in range(N+1):
    if i == 0:
        corrent_nood = 1-A[i]
        count_nood += corrent_nood
        max_nood -= A[i]
    else:
        corrent_nood = min(2*(corrent_nood-A[i-1]), max_nood)
        max_nood -= A[i]
        count_nood += corrent_nood
    if count_nood <= 0 or A[i] > corrent_nood:
        ans = False
        break
        # print(i)
    # print(corrent_nood)


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

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if n == 0:
        return '1' if A[0] == 1 else '-1'

    ret = 0
    R = [0]*(n+1)
    R[0] = 1-A[0]

    for i in range(1, n+1):
        R[i] = 2*R[i-1]
        for _ in range(A[i]):
            j = i
            if R[j] <= 0:
                return '-1'

            while 0 < R[j]:
                R[j] -= 1
                ret += 1
                j -= 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
def main(N, A):
    num = 1
    ans = 1
    if A[N] == 0:
        return -1
    for i in range(N+1):
        num -= A[i]
        if i < N:
            num *= 2
            ans += num
        if num <= 0 and i < N:
            return -1
    eda = 0
    for i in range(N+1):
        ans -= num
        eda += A[N-i]
        num -= eda
        num = num//2
        if num <= 0:

            break
    return ans


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

print(main(N, A))

Submission status: Wrong Answer

Solution code:
n = input()
alist = [int(s) for s in input().split(" ")]

def check(alist):
  r = 1
  n = 1
  for i, a in enumerate(alist):
    if a > r:
      return -1
    if a == r and len(alist) - 1 != i:
      return -1
    r = 2 ** (r - a)
    if len(alist) - 1 != i:
      n += r
  return n

print(check(alist))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
sum_A=sum(A)
if A[0]!=0:print(-1);exit()
if A[0]==1 and len(A)==1:print(1);exit()

flag=0
ans,point=[1],1
for i in range(1,n+1):
    if flag==0:
        point *=2
    if point>=sum_A:
        point=sum_A
        flag=1
    ans.append(point)
    if point<=0:print(-1);exit()
    point -=A[i]
    sum_A -=A[i]
print(sum(ans))

Submission status: Wrong Answer

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

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, -1, -1):
    node_d[i] = min(node_d[i], node_d[i + 1] + a[i])

print(sum(node_d))

Submission status: Wrong Answer

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

if a[0]==1:
    print(-1)
    exit()
    
x = [0]*(n+1)
x[0] = 1
for i in range(n-1):
    x[i+1] = 2*(x[i]-a[i])
x[-1] = a[-1]
for i in range(n-1,0,-1):
    if a[i]>x[i]:
        print(-1)
        exit()
    x[i] = min(x[i],x[i+1]+a[i])
print(sum(x))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(reversed(list(map(int,input().split()))))
ans=[]
ans2=[1]
flg=0
for i in range(n+1):
  if i != 0 and sum(a[:i])//2 >= 2**(n-i-1):
    pass
  if sum(a[:i+1]) <= 2**(n-i):
    ans.append(sum(a[:i+1]))
  else:
    ans.append(2**(n-i))
a=list(reversed(a))
ans=list(reversed(ans))

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

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
if n==0:
    if a[0]==0:
        print(0)
    else:
        print(1)
    quit()
if a[0]==1:
    if n!=0:
        print(-1)
        quit()

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

sita=0
ans=0
for i in range(n+1)[::-1]: 
    # now=pow(2,i)
    # print(now)

    if i==n:
        if (a[i]+1)//2>maxnode[-1]:
            print(-1)
            quit()
        else:
            maxnode[-1]=min(a[i],maxnode[-1])
            ans+=a[i]
    else:
        if maxnode[i]+a[i]>maxnode[i-1]*2:
            print(-1)
            quit()
        else:
            maxnode[i-1]=min(maxnode[i]+a[i],maxnode[i-1])
            ans+=maxnode[i]+a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    A = list( map( int, input().split()))
    root = 1
    if A[0] == 1:
        if N == 0:
            print(1)
        else:
            print(-1)
    B = A[::-1]
    low = high = B[0]
    # Low = []
    Hight = [high]
    
    for b in B[1:]:
        low = max(1, (low+1)//2) + b
        high = high + b
        Hight.append(high)
    if low > 1:
        print(-1)
        return
    ans = 1
    now = 1
    BHight = Hight[::-1]
    for i in range(1,N+1):
        if now == 0:
            print(-1)
            return
        h = BHight[i]
        leaf = A[i]
        # print("h",h)
        now = min(h, now*2)
        ans += now
        now -= leaf
        if now < 0:
            print(-1)
        # print(now)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()


def main():
    l, r = [None] * (N + 1), [None] * (N + 1)
    l[0], r[0] = 1, 1
    l[-1], r[-1] = A[-1], A[-1]
    for i in range(N - 1, 0, -1):
        l[i] = (l[i + 1] + 1) // 2 + A[i]
        r[i] = r[i + 1] + A[i]
    
    ans = 1
    x = 1
    for i in range(1, N + 1):
        x -= A[i - 1]
        if x < 0:
            print(-1)
            return
        s = max(x, l[i])
        t = min(2 * x, r[i])
        if s > t:
            print(-1)
            return
        x = t
        ans += t
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

INF = 10**15

cond = [1]
m = INF
for a in A[1:]:
    c = min(INF, cond[-1]*2-a)
    if c<0:
        print(-1)
        exit()
    cond.append(c)

ans = 0
node = 0
for n in range(N, -1, -1):
    n1 = A[n]
    n2 = min(cond[n], node)
    node = n1 + n2
    ans += node

print(ans)

Submission status: Wrong Answer

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

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

INF = 1e18
B = [1]*(N+1)
for i,a in enumerate(A[1:],1):
    B[i] = min(INF,B[i-1]*2 - a)

ans = 0
p = 0
for i,a in enumerate(A[::-1]):
    i = N - i
    m = B[i]
    if p>2*m:
        ans = -1
        break
    p = min(m,p)+a
    ans += p

print(ans)

Submission status: Wrong Answer

Solution code:
import math
#3
#0 1 1 2

N = int(input())+1
leaves = list(map(int, input().split()))

nod = 0
total = 0

maxx = [0]*(N+1)
#toward
maxx[0] = 1
for i in range(1, N):
    notleave = maxx[i-1] - leaves[i-1]
    if notleave < 0:
        total = -1
        break
    maxx[i] = notleave*2
    if maxx[i] < leaves[i]:
        total = -1
        break

if total >= 0:
    #backward
    for i in range(1, N+1):
        ii = N-i
        #at least need newnod nodes
        newnod = int((nod+1)/2) + leaves[ii]
        if newnod > 0 and (math.log(newnod, 2) > ii):
            total = -1
            break
        #maximum is?
        newnod = nod + leaves[ii]
        if newnod > maxx[ii]: newnod = maxx[ii]
        total += newnod
        nod = newnod

if total <= 0: total = -1
print(total)

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] * 2:
        print(-1)
        sys.exit(0)
    if v[i] + nd > lim[i]:
        nd = lim[i] - v[i]

    nd += v[i]
    ans += nd

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

if N == 0:
    if A_list[0] == 1:
        print(0)
    else:
        print(-1)
elif A_list[0] != 0:
    print(-1)
else:
    ans = 1
    deathable_node = 1
    sum_rest_A = sum(A_list)
    for i in range(1, N + 1):
        now_A = A_list[i]
        deathable_node = min(sum_rest_A, deathable_node * 2) - now_A

        if deathable_node < 0:
            print(-1)
            break

        sum_rest_A -= now_A
        ans += deathable_node + now_A
        # print(i, now_A, sum_rest_A, deathable_node, ans)
        if deathable_node == 0 and i != N:
            print(-1)
            break
    else:
        print(ans)

Submission status: Wrong Answer

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

cap = [1]*(N+1)#0-N

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

for i in range(1,N+1,1):#1-N
    cap[i]=min(cap[i-1]*2 - A[i],10**9)
    if cap[i] < 0 or (cap[i]==0 and i!=N):
        print(-1)
        exit()

T = [0]*(N+1)
T[N]=A[N]#ここのキャパオーバーは上ではじけるはず
for i in range(N-1,-1,-1):
    T[i]=A[i]+min(T[i+1],cap[i])

print(sum(T))

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]!=0:
	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()
		elif i == n:
			if cnt * 2 - target < 0:
				print(-1)
				exit()
			else:
				cnt = min(cnt*2, a[n])
				ans += cnt
		else:
			if cnt*2-a[i] < ruisekiwa[i]:
				ans += cnt*2
				cnt = cnt*2-a[i]
			else:
				ans += ruisekiwa[i]
				cnt = ruisekiwa[i]
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))
n=n_in()
A=l_in()

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


if A[0] != 0:
    print(-1)
    exit()
    
B=[0]*(n+1)
B[0] = 1

upper = max(A)

S=[0]*(n+1)
S[0] = A[0]

for i in range(1,n+1):
    S[i] = S[i-1]+A[i]



for i in range(1, n):
    B[i] = min(B[i-1]*2-A[i], S[n]-S[i])
    if B[i] <= 0:
        print(-1)
        exit()

    

print(sum(A)+sum(B))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
sum_A=sum(A)
if A[0]!=0 and len(A)>1:print(-1);exit()
if A[0]!=0 and len(A)==1:print(1);exit()

flag=0
ans,point=[1],1
for i in range(1,n+1):
    if flag==0:
        point *=2
    if point>=sum_A:
        point=sum_A
        flag=1
    ans.append(point)
    if point<=0:print(-1);exit()
    point -=A[i]
    sum_A -=A[i]
print(sum(ans))

Submission status: Wrong Answer

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

b = [0]*n
c = [0]*n

now = 1
for i in range(n):
    b[i] = now
    now -= a[i]
    if now <= 0 and i != n-1:
        print(-1)
        exit()
    now *= 2

a = list(reversed(a))
c[0] = a[0]
now = a[0]
for i in range(1, n):
    now += a[i]
    c[i] = now

c = list(reversed(c))

ans = 0
for i in range(n):
    ans += min(b[i], c[i])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

ans = 0
li = [0]*(n+1)

for i,a in enumerate(a_li):
  ans += (i+1)*a

for i,a in enumerate(a_li[::-1]):
  if i >= 1:
    li[i] = li[i-1]+a
  else:
    li[i] = a

li = li[::-1]

flag = True
ne = 0.5
for i in range(n+1):
  if li[i]  > 2*ne:
    ans -= li[i] -2*ne

  ne = 2*ne - a_li[i]
  if ne <= 0:
    flag = False
if flag:
  print(int(ans))
else:
  print(-1)

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) or x < 0: print(-1); exit()
    if x == s[i]: continue
    if x*2 > s[i+1]: x = s[i+1]
    else: x *= 2

print(-1 if x != 0 else ans)

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 a<=0:
    f+=1
    break
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
if f==0:
  print(sum(g))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=tuple(map(int,input().split()))
ans=1
tmp=0
M=[1]

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

for i,x in enumerate(A[1:],1):
    if i>=65:
        n=2**65
    else:
        n=2**i
    M.append(min(n-x,M[i-1]*2-x))
    if (i!=N and M[i]<=0) or (i==N and M[i]<0):
        print(-1)
        exit()
for i,(x,y) in enumerate(zip(A[1:][::-1],M[1:][::-1])):
    tmp+=x
    tmp=min(tmp,n,y+x)
    ans+=tmp
if A[0]+M[0]>1:
    print(-1)
    exit()
print(ans)