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:
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a_li = list(map(int, input().split()))
sum_li = []
tmp = 0
for a in reversed(a_li):
    tmp += a
    sum_li.append(tmp)

if a_li[0]>0 and n>0:
    print(-1)
else:
    cnt = 1
    node = 1
    for i in range(1, n+1):
        node = min(node*2-a_li[i], sum_li[n-i-1])
        if (node < 0) or (node <= 0 and i!=n):
            print(-1)
            break
        if i!=n:
            tmp = node + a_li[i]
        else:
            tmp = a_li[i]
        # if tmp <= 2**i:
        cnt += tmp
        # else:
        #     print(-1)
        #     break      
    else:
        print(cnt)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
'''
if n == 0 and a[0] == 1:
    print(1)
elif n == 0:
    print(-1)
    exit()
'''
d = [-1 for _ in range(n + 1)]
s = [0 for _ in range(n + 2)]
for i in reversed(range(n + 1)):
    s[i] = s[i + 1] + a[i]
d[0] = 1
for i in range(1, n + 1):
    d[i] = min((d[i - 1] - a[i - 1]) * 2, s[i])
    if d[i] <= 0:
        print(-1)
        exit()
print(sum(d))

Submission status: Wrong Answer

Solution code:
import sys

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

#n=4
#a="0 0 1 0 2"

#n=10
#a="0 0 1 1 2 3 5 8 13 21 34"
#a=list(map(int,a.split()))

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

b=[0]*(n+1)
b[0]=1
yn=""
for i in range(n):
    b[i+1]=b[i]*2-a[i+1]
    if b[i+1]<0:
        yn="no"
        break
if yn=="no":
    print(-1)
else:    
    b[n-1]=a[n]

    b[n]=0
    c=[0]*(n+1)
    c[n]=0
#    c[n-1]=a[n]

    for i in range(n,0,-1):
        c[i-1]=min(a[n]+a[i],b[i-1])    
#        print("i-1",i-1,"c[i-1]",c[i-1],"a[n]",a[n],"c[i]",c[i],"b[i-1]",b[i-1])
    
#print(a)
#print(b)
#print(c)
    print(sum(a)+sum(c))

Submission status: Wrong Answer

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

leaves = list(map(int, input().split()))
points = list(range(n+1))
lines  = list(range(n+1))

for i in lines:
  lines[i] = sum(leaves[i:n+1])

lines[0] = 1
points[0] = 1

for i in range(n-1):
  if 2*(points[i] - leaves[i]) < leaves[i+1] +1:
    print(-1)
    a = -1
    break
  else:
    points[i+1] = min(2*(points[i]-leaves[i]), lines[i+1])

if 2*(points[n-1] - leaves[n-1]) < leaves[n] and a != -1:
  print(-1)
  a = -1
else:
  points[n] = min(2*(points[n-1]-leaves[n-1]), lines[n])

if a != -1:
  print(sum(points[0:n+1]))

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
if n == 0 and a[0] == 1:
    print(1)
elif n == 0:
    print(-1)
    exit()
d = [-1 for _ in range(n + 1)]
s = [0 for _ in range(n + 2)]
for i in reversed(range(n + 1)):
    s[i] = s[i + 1] + a[i]
d[0] = 1
for i in range(1, n + 1):
    d[i] = min((d[i - 1] - a[i - 1]) * 2, s[i])
    if d[i] <= 0:
        print(-1)
        exit()
print(sum(d))

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
from collections import defaultdict

import time

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq

n = readInt()
a = readInts()

tar = []
for i in range(len(a)):
	tar.append(2**i-a[i])
tar[-1] = 0

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

while 1:
	changed = 0
	for i in range(len(tar)-1):
		if tar[i]*2<tar[i+1]+a[i]:
			changed = 1
			tar[i+1] = tar[i]*2-a[i+1]
		if tar[i]<0:
			print(-1)
			exit()


	for i in range(len(tar)-1,0,-1):
		if tar[i]+a[i]<tar[i-1]:
			changed = 1
			tar[i-1] = tar[i]+a[i]
		if tar[i]<0:
			print(-1)
			exit()

	if changed==0:
		break


print(sum(a)+sum(tar))

Submission status: Wrong Answer

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

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


#!  方針
#!    1．葉の枚数が可能であるかチェック
#!    2．節の最大数、上から降りて、下から上がる



Fushi=[1]
for i in range(N+1):
  if i==0: continue
  f = Fushi[i-1]
  h = Ha[i]
  pw = pow(2,i)

  if pw-h<=0:
    print(-1)
    exit(0)

  Fushi.append( min(pw-h, f*2-h) )


Fushi[N]=0

p("H, ",Ha)
p("F, ", Fushi)


#for f in reversed(Fushi[:-1]):
#  print(f)

for i in reversed(range(N)):
  #print(i)

  h = Ha[i+1]
  f = Fushi[i+1]

  Fushi[i] = min(Fushi[i], h+f)



p("F, ", Fushi)
p("sumH" , sum(Ha))
p("sumF", sum(Fushi))


ans = sum(Ha) + sum(Fushi)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int,input().split()))
ans = [0]*(n+1)
ans[0] = 1
c_sum = [0]*(n+1)
c_sum[0] = arr[0]
for i in range(1,n+1):
    c_sum[i] = c_sum[i-1] + arr[i]
root = [0]*(n+1)
root[0] = arr[0]
for d in range(n+1):
    if d==0:
        ans[d] = min(1-arr[0],c_sum[-1])
    else:
        ans[d] = min(root[d-1]*2,(c_sum[-1] - c_sum[d-1]))
    if ans[d] < 0:
        print(-1)
        exit()
    root[d] = ans[d] - arr[d]
print(sum(ans))

Submission status: Wrong Answer

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

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

sita_maxi = [0 for i in range(n+1)]
sita_maxi[n] = a[n]
for i in range(n-1, -1, -1):
    sita_maxi[i] = sita_maxi[i+1] + a[i]

lst = [1]
for i in range(1, n+1):
    lst.append(min((lst[i-1]-a[i-1])*2, sita_maxi[i]))
    if lst[-1] < a[i]:
        print(-1)
        exit()

print(sum(lst))

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
if n == 0 and a[0] == 1:
    print(1)
else:
    print(-1)
d = [-1 for _ in range(n + 1)]
s = [0 for _ in range(n + 2)]
for i in reversed(range(n + 1)):
    s[i] = s[i + 1] + a[i]
d[0] = 1
for i in range(1, n + 1):
    d[i] = min((d[i - 1] - a[i - 1]) * 2, s[i])
    if d[i] <= 0:
        print(-1)
        exit()
print(sum(d))

Submission status: Wrong Answer

Solution code:
import sys
import math
N = int(input())
A = list(map(int, input().split()))
node = [0]*(N+1)
node[0] = 1
for n in range(0,N):
    node[n] = node[n-1]*2-A[n]
    if node[n] > 2**n:
        print(-1)
        sys.exit()
for n in range(N,0,-1):
    if node[n]+A[n] > 2*node[n-1]:
        print(-1)
        sys.exit()
    elif node[n]+A[n] > node[n-1]:
        node[n] += A[n]
    else:
        node[n] = node[n]+A[n]
        node[n-1] = node[n]
print(sum(node))

Submission status: Wrong Answer

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

    final_leave_num = A[N]

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

    next_node_w_children = 1
    next_leaf_num = 0
    next_node_num = 1
    node_in_the_dept = 0
    
    for i in range(N):
        node_in_the_dept = next_node_num
        node_w_children = next_node_w_children      
        next_leaf_num = A[i+1]

        if(i == N-1):
            next_node_w_children = 0
            if(node_w_children > next_leaf_num):
                print(-1)
                return
            else:
                node_num += next_leaf_num
                print(node_num)
        else:
            all_leave_num -=A[i]
            next_node_num = min(2 * node_w_children, all_leave_num)
            next_node_w_children = next_node_num - next_leaf_num
            if(next_node_num > node_w_children * 2 or next_node_w_children <= 0):
                print(-1)
                return
            node_num += next_node_num
    
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cusum = [0 for i in range(N+1)]
cusum[N] = A[N]


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

# print(cusum)
pre_node = 1
ans = 1
for i in range(1, N+1):
    node = (pre_node - A[i-1]) * 2
    if node < A[i]:
        ans = -1
        break
    pre_node = min(node, cusum[i])
    ans += pre_node
print(ans)

Submission status: Wrong Answer

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

if A[0] >= 1:
  print(-1)
  exit()
 
ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
node = 1
leaf = 1
for i in range(1, N+1):
        leaf = min((leaf - A[i - 1]) * 2, sum(A[i:]))
        if leaf <= 0 :
            print(-1)
            break;
        node += leaf
else :
    print(node)

Submission status: Wrong Answer

Solution code:
n= int(input())

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

#print(a)

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

if n == 0:
    print(-1)
    exit(0)

b=1
count=1
asum =sum(a)
alim = asum

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

        count += b



print(count+ asum)

Submission status: Wrong Answer

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

ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)
 
if bottom == 0 or A[0] >= 1:
  print(-1)
  exit()
 
ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

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


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

INF = 2**62-1


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


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


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


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


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


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

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


def mt(f):
    import time

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

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

    return wrap


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

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




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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
last = A[-1]
count = last
root = 1
for i in range(N):
  if i+1 == N and root-A[i] > A[i+1]:
    root = last + A[i]
  elif root-A[i] > (last + A[i+1]):
    root = (last + A[i+1]) + A[i]
  count+=root
  root = (root-A[i])*2
  if root < A[i+1]:
    print(-1)
    break
else:
  print(count)

Submission status: Wrong Answer

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


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

INF = 2**62-1


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


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


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


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


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


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

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


def mt(f):
    import time

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

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

    return wrap


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

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




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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n= int(input())

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

#print(a)

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

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

b=1
count=1
asum =sum(a)
alim = asum

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

        count += b



print(count+ asum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)
 
if bottom <= 0:
  print(-1)
  exit()
 
ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
if n ==0 :
    if a[0] == 2:
        print(2)
    else:
        print(-1)
    sys.exit()
    
back = [0 for _ in range(n+1)]
back[n] = a[n]
for i in range(n-1, -1, -1):
	back[i] = back[i+1] + a[i]

v = [1]
for i in range(n):
    #print(v[-1],a[i])
    k = min((v[-1]-a[i])*2,back[i+1])
    if k<=0:
        print(-1)
        sys.exit()
    v.append(k)
print(sum(v))

Submission status: Wrong Answer

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

ans = 0
prev = 1
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 = 0
    for i in range(N, -1, -1):
        if L[i] == "inf":
            num += A[i]
        elif num <= L[i]:
            num += A[i]
        else:
            num = L[i]+A[i]
        ans += num
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)
 
if bottom <= 0 or A[0] >= 1:
  print(-1)
  exit()
 
ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

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

#leaves = input()
leaves = list(map(int, input().split()))
points = list(range(n+1))
lines  = list(range(n+1))

for i in lines:
  lines[i] = sum(leaves[i:n+1])

lines[0] = 1
points[0] = 1

for i in range(n-1):
  if 2*(points[i] - leaves[i]) < leaves[i+1] +1:
    print(-1)
    a = -1
    break
  else:
    points[i+1] = min(2*(points[i]-leaves[i]), lines[i+1])

if 2*(points[n-1] - leaves[n-1]) < leaves[n] and a != -1:
  print(-1)
  a = -1
else:
  points[n] = min(2*(points[n-1]-leaves[n-1]), lines[n])

if a != -1:
  print(sum(points[0:n+1]))

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
if n == 1:
    if a == 2:
        print(2)
    else:
        print(-1)
    sys.exit()
    
back = [0 for _ in range(n+1)]
back[n] = a[n]
for i in range(n-1, -1, -1):
	back[i] = back[i+1] + a[i]

v = [1]
for i in range(n):
    #print(v[-1],a[i])
    k = min((v[-1]-a[i])*2,back[i+1])
    if k<=0:
        print(-1)
        sys.exit()
    v.append(k)
print(sum(v))

Submission status: Wrong Answer

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


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

INF = 2**62-1


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


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


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


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


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


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

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


def mt(f):
    import time

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

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

    return wrap


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

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




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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

    if n  == 0:
        if A[0] == 1:
            return 1
        else:
            return -1
    elif A[0] != 0:
        return -1
    
    nodes = 0
    bound = list(accumulate(A[::-1]))
    bound.reverse()
    # print('bound: ', bound)
    
    above = [0] * (n+1)
    above[0] = 1
    B = [0] * (n+1)
    for i, a in enumerate(A):
        if i == 0:
            B[0] = 1
        else:
            above[i] = (above[i-1] - A[i-1]) * 2
            if above[i] < 0:
                return -1
            B[i] = min(above[i], bound[i])
    # print('above: ', above)
    # print('B: ', B)
    return sum(B)

print(main())

Submission status: Wrong Answer

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

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


start = 1
way = sum(A)

for i in range(1,n+1):
    start *= 2

    if start < A[i]:
        print(-1)
        exit()
    if start > way:
        start = way

    ans += start
    #print(start, start-A[i])
    start -= A[i]
    way -= A[i]
#print()
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a_li = list(map(int, input().split()))
sum_li = []
tmp = 0
for a in reversed(a_li):
    tmp += a
    sum_li.append(tmp)

if a_li[0]>0 and n>0:
    print(-1)
else:
    cnt = 1
    node = 1
    for i in range(1, n+1):
        node = min(node*2-a_li[i], sum_li[n-i-1])
        if node < 0:
            print(-1)
            break
        if i!=n:
            tmp = node + a_li[i]
        else:
            tmp = a_li[i]
        if tmp <= 2**i:
            cnt += tmp
        else:
            print(-1)
            break      
    else:
        print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
 
if n == 0:
  if a[0] == 1:
    print(1)
  else:
    print(-1)
else:
  accum = [0]*(n+1)
  new_list = list(reversed(a))
  accum[0] = new_list[0]
  for i in range(n):
      accum[i+1] = accum[i] + new_list[i+1]
  hat = list(reversed(accum))
  #print(hat)
 
  b = [1]*(n+1)
  flag = 0
  cand = 0
 
  for i in range(1,n+1):
    cand = (b[i-1]-a[i-1])*2
    if cand < 1:
      flag = 1
      break
    if cand > hat[i]:
      b[i] = hat[i]
    else:
      b[i] = cand
 
  #print(b)
  if flag != 1:
    print(sum(b))
  else:
    print(-1)

Submission status: Wrong Answer

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

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


start = 1
way = sum(A)

for i in range(1,n+1):
    start *= 2

    if start < A[i]:
        print(-1)
        exit()
    if start > way:
        start = way

    ans += start
    #print(start, start-A[i])
    start -= A[i]
    way -= A[i]
#print()
print(ans+1)

Submission status: Wrong Answer

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

v = [1]
for i in range(n):
    #print(v[-1],a[i])
    k = min((v[-1]-a[i])*2,back[i+1])
    if k<=0:
        print(-1)
        sys.exit()
    v.append(k)
print(sum(v))

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from itertools import *
n,*a=map(int,open(0).read().split())
b=list(accumulate(a[::-1]))
b=b[::-1]
c=[1]*(n+1)
if a[0]!=0:
    print(-1)
    exit()
for i in range(1,n+1):
    c[i]=min((c[i-1]-a[i-1])*2,b[i])
    if (c[i-1]-a[i-1])*2<0:
        print(-1)
        exit()
print(sum(c))

Submission status: Wrong Answer

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


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

INF = 2**62-1


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


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


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


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


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


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

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


def mt(f):
    import time

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

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

    return wrap


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

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




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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N == 0:
    print(1)
else:
    saidaiA =[]
    oya = 1
    flag = True
    for i in range(len(A)):
        if oya >= 5*10**13:
            ko = 10**14
        else:
            ko = oya *2
        if i == 0:
            ko = 1
        oya = ko - A[i]
        saidaiA.append(ko)
        if oya < 0:
            flag = False
    ans = 0
    # print(saidaiA)
    motikosi = 0
    for i in range(len(A)):
        if A[-i] + motikosi >= saidaiA[-i]:
            ans += saidaiA[-i]
            motikosi = saidaiA[-i]
        else:
            ans += A[-i] + motikosi
            motikosi = A[-i] + motikosi
    if flag == True:
        print(ans+1)
    else:
        print(-1)