Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
1.6 kB
0
Indexable
Never
import sys
input = sys.stdin.readline

# 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())))

# Input read
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)