# Untitled

unknown
python
2 years ago
1.6 kB
0
Indexable
Never
```import sys

# Helper function to read input see https://codeforces.com/blog/entry/71884
def inp():
return(int(input()))

def inlt():
return(list(map(int,input().split())))

N = inp()
a = inlt()
K = inp()
recipes = [[]]*N
for _ in range(K):
line = inlt()
L = line[0]
recipes[L-1]=list(map(lambda x : x-1,line[2:]))

def can_make_x_metal(x):
global a,N
requirements = [0]*N
requirements[N-1] = x
can_make_c = True
for i in reversed(range(N)):
# We want to check if can have requirement[i] of metal i
# Substract what we already have from input (max with 0 to avoid negative)
requirements[i]=max(0,requirements[i]-a[i])
# If we still need more metal i we must use the recipes to make it
if requirements[i]>0:
# If we don't have any recipe, so sorry, we can satisfy the requirements
if len(recipes[i])==0:
can_make_c=False
break
else:
# We will use all the ingredients in recipes[i] to make i
# So if we need (for example) requirements[5]=10
# And we ave have recipes[5]=[1,2,4]
# We will add +10 to the requirments[1],requirments[2],requirments[4]
for r in recipes[i]:
requirements[r] += requirements[i]
return can_make_c

#Binary search
x = a[N-1]
y = sum(a)+1
while y-x>1:
c = (x+y)//2
if can_make_x_metal(c):
x = c
else:
y = c

print(x)
```