PreviousNext
Coding/Front-end code

Choose offline lessons that fit a storage budget

Write codeHard40 min

Your task

Your language-learning web app lets people save video lessons for offline use. The app sets aside budget bytes of the browser's storage for them. Each lesson has a size and a score for how likely the learner is to open it soon, and the app picks the set to download.

Write best_offline_score(sizes, scores, budget) that returns the largest total score of lessons that fit.

Input and output:

  • sizes: up to 36 lesson sizes in bytes, integers from 1 to 1,000,000,000.
  • scores: the score of each lesson, integers from 0 to 1,000,000,000.
  • budget: an integer from 0 to 40,000,000,000.
  • Returns an integer.

Rules:

  • A lesson is downloaded whole or not at all, and at most once.
  • The sizes of the downloaded lessons add up to at most budget.
  • Return the largest total score of such a set, or 0 when no lesson fits.

Examples

best_offline_score(sizes: list[int], scores: list[int], budget: int) -> int
Example 1
Inputbest_offline_score([400000000, 300000000, 300000000], [50, 40, 40], 600000000)
Output80
Example 2
Inputbest_offline_score([700000000, 200000000, 500000000, 100000000], [9, 3, 7, 1], 800000000)
Output11
Example 3
Inputbest_offline_score([1200, 3000], [5, 8], 1000)
Output0