Show problems as
Classic problem #1298HardArrayBreadth-First SearchGraph Theory

Maximum Candies You Can Get from Boxes

Real-world version: Ration Packs From Nested Crates
Tracked in this browser only
Read Maximum Candies You Can Get from Boxes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A relief depot holds n crates labelled 0 through n - 1. For crate i:

  • unlocked[i] is 1 when its clasp is already free and 0 when the clasp is sealed;
  • rations[i] is how many ration packs are inside it;
  • keycards[i] lists the labels of the crates whose clasps the keycards inside crate i will free;
  • nested[i] lists the labels of the crates packed inside crate i.

You arrive holding exactly the crates listed in startCrates. You may open a crate you are holding when its clasp is free, either because it started that way or because you have picked up a keycard for it. Opening a crate hands you all of its ration packs, all of its keycards and all of the crates packed inside it, and those crates are then in your hands too.

A keycard is never used up: once you hold the keycard for a crate, that crate's clasp counts as free from then on, including for a crate that has been sitting in your hands unopened. You may open crates in any order you like and you take nothing out of a crate you never open.

Return the largest number of ration packs you can end up with.

Examples

Example 1

Input
unlocked = [0, 1, 0], rations = [5, 2, 9], keycards = [[], [0], []], nested = [[], [], []], startCrates = [0, 1]
Output
7

Crate 1 arrives with a free clasp, so opening it banks 2 packs and hands over a keycard for crate 0. Crate 0 is already in hand, and with its clasp now free it opens for 5 more packs. Crate 2 is never in hand, so its 9 packs stay in the depot.

Example 2

Input
unlocked = [1, 0, 1, 1], rations = [1, 2, 4, 8], keycards = [[], [], [], []], nested = [[1], [2], [3], []], startCrates = [0]
Output
1

Crate 0 opens for 1 pack and yields crate 1, whose clasp is sealed and for which no keycard exists anywhere, so crate 1 is never opened and crates 2 and 3 packed below it are never in hand.

Example 3

Input
unlocked = [1], rations = [7], keycards = [[]], nested = [[]], startCrates = []
Output
0

You arrive holding no crates at all, so there is nothing to open and no packs to collect.

Constraints

  • 1 <= unlocked.length <= 1000
  • rations.length == unlocked.length
  • keycards.length == unlocked.length
  • nested.length == unlocked.length
  • 0 <= unlocked[i] <= 1
  • 1 <= rations[i] <= 1000
  • 0 <= keycards[i].length <= 1000
  • 0 <= keycards[i][j] <= 999
  • 0 <= nested[i].length <= 1000
  • 0 <= nested[i][j] <= 999
  • 0 <= startCrates.length <= 1000
  • 0 <= startCrates[i] <= 999
  • Every label listed in keycards[i], in nested[i] and in startCrates is a valid crate label, and no label is repeated inside any one of those lists.
  • No crate is packed inside more than one crate, and no crate is packed inside itself either directly or through a chain of crates.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_rations(unlocked: list[int], rations: list[int], keycards: list[list[int]], nested: list[list[int]], startCrates: list[int]) -> int:
Java
public int maxRations(int[] unlocked, int[] rations, int[][] keycards, int[][] nested, int[] startCrates)

More on the same topics