Untitled
unknown
python
3 years ago
1.6 kB
5
Indexable
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)
Editor is loading...