tobakudan

rod cutting problem

Jan 12th, 2021
792
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. l = int(input())
  2. n = int(input())
  3. ls = {0:0}
  4. for i in range(n):
  5.     length, value = [int(j) for j in input().split()]
  6.     if length <= l and value > 0:
  7.         ls[length] = value
  8.  
  9. c = 1
  10. while c <= l:
  11.     groups = [ls[r]+ls[c-r] for r in range(round(c//2)+1) if r in ls and c-r in ls]
  12.     if groups:
  13.         ls[c] = max(groups)
  14.     c += 1
  15.  
  16. print(max(ls.values()))
  17.  
RAW Paste Data